Bài toán 'bước chân của Pi

#1

Bài toán 'bước chân của Pi
Pi là một cậu bé hiếu động. Mỗi buổi sáng, khi tỉnh dậy, cậu đều chạy từ lầu 2 xuống lầu 1, bật nhạc nhảy một điệu nhảy để thức cả nhà dậy.
Khi xuống cầu thang, Pi có thể bước 1 bậc hoặc 2 bậc theo một thứ tự tùy ý.

Nếu cầu thang có tất cả 19 bậc thì cậu bé Pi có tất cả bao nhiêu cách xuống cầu thang? Ví dụ nếu cầu thang chỉ có 4 bậc thì Pi có 5 cách xuống cầu thang: (1, 1, 1, 1); (1, 1, 2); (1, 2, 1); (2, 1, 1); (2, 2).

TS Trần Nam Dũng
ĐH Khoa học Tự nhiên, ĐH Quốc gia TP HCM

2 Likes
#2

khá là lớn, lặp lại hơi bị mệt đây, chắc khoảng ~5000 dùng Fibonaci.

1 Like
#3

Bài này là quy hoạch động với dãy Fibonacy thì phải. Mình chỉ đọc qua thôi.

2 Likes
#4

2015-05-02_12-11-46.jpg527×621 182 KB

4 Likes
#5

Anh ơi, cho em thắc mắc cái, dãy Fibo có liên quan gì ở đây hả anh ?

Em làm bài về nó chứ cũng chẳng biết ứng dụng hay nó để làm gì (em chỉ biết nó liên quan gì đó đến tỉ lệ vàng)

À, theo cách dự đoán quy luật như anh Huy đăng. Cám ơn anh.

#6

Cái này là từ cơ sở Quy Hoạch Động của bài này:

# Gọi F [i] là số cách đi đến  bậc i
F[i] =
       F[i-1]  # nhảy 1 bậc
    +  F[i-2] # nhảy 2 bậc

Khó ở đây là cài số lớn thôi. Cỡ 1000 chữ số :smiley:

2 Likes
#7

chuẩn luôn, như hồi trước tính Fibonaci f(n)=f(n-1)+f(n-2) cũng vậy như là nhảy 1 bậc và nhảy 2 bậc.

trước anh có đọc 1 bài nói số cánh hoa của các loài hoa có liên quan đến dãy fibo, vòng xoắn ốc cũng thế. đâu phải khơi khơi nó trờ thành dãy số nỗi tiếng như thế :smiley:

3 Likes
#8

Bài toán có mô hình như của @Gio đăng thì có thể dùng công thức đệ quy của Fibo :smile:

#9

Đệ quy chắc không thể chạy tới n=30 :smiley: .

#10

công thức tổng quát chứ nhỉ :smiley: hehe

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?