- Ebook Giải thuật và lập trình Lê Minh Hoàng
- Các thuật toán sắp xếp trong Pascal

Dãy số Fibonacci và bài toán nuôi thỏ



Dãy số Fibonacci bắt nguồn từ bài toán cổ về việc sinh sản của các cặp thỏ. Bài toán đặt ra như sau:
1) Các con thỏ không bao giờ chết
2) Hai tháng sau khi ra đời, mỗi cặp thỏ mới sẽ sinh ra một cặp thỏ con (một đực, một cái)
3) Khi đã sinh con rồi thì cứ mỗi tháng tiếp theo chúng lại sinh được một cặp con mới
Giả sử từ đầu tháng 1 có một cặp mới ra đời thì đến giữa tháng thứ n sẽ có bao nhiêu cặp.

Ví dụ, n = 5, ta thấy:
Giữa tháng thứ 1: 1 cặp (ab) (cặp ban đầu)
Giữa tháng thứ 2: 1 cặp (ab) (cặp ban đầu vẫn chưa đẻ)
Giữa tháng thứ 3: 2 cặp (AB)(cd) (cặp ban đầu đẻ ra thêm 1 cặp con)
Giữa tháng thứ 4: 3 cặp (AB)(cd)(ef) (cặp ban đầu tiếp tục đẻ)
Giữa tháng thứ 5: 5 cặp (AB)(CD)(ef)(gh)(ik) (cả cặp (AB) và (CD) cùng đẻ)
Bây giờ, ta xét tới việc tính số cặp thỏ ở tháng thứ n: F(n)

Nếu mỗi cặp thỏ ở tháng thứ n – 1 đều sinh ra một cặp thỏ con thì số cặp thỏ ở tháng thứ n sẽ là:
F(n) = 2 * F(n – 1)

Nhưng vấn đề không phải như vậy, trong các cặp thỏ ở tháng thứ n – 1, chỉ có những cặp thỏ đã có ở tháng thứ n – 2 mới sinh con ở tháng thứ n được thôi. Do đó F(n) = F(n – 1) + F(n – 2) (= số cũ + số sinh ra). Vậy có thể tính được F(n) theo công thức sau:
• F(n) = 1 nếu n ≤ 2
• F(n) = F(n – 1) + F(n – 2) nếu n > 2
(Trích: Cấu trúc dữ liệu và giải thuật – Lê Minh Hoàng)

VAR thang,i, tn, tn_1, tn_2:INTEGER;
BEGIN           
    write('Nhap so thang: ');
    readln(thang);
    IF thang>2 THEN
    BEGIN
        tn_2:=1; {Thang dau tien co 1 cap tho}
        tn_1:=1; {Thang thu 2 van co 1 cap tho}
        FOR i:=3 TO thang DO
        BEGIN
            tn:=tn_1 + tn_2;
            tn_2:=tn_1;
            tn_1:=tn;
        END;
    END
    ELSE
        tn:=1;
    writeln('So con tho sau ',thang,' thang la: ',2*tn);
    readln
END.

Lưu ý: hiện nay có một số sai khác về định nghĩa dãy Fibonacci như sau:
• F(n) = 1 nếu n < 2
• F(n) = F(n – 1) + F(n – 2) nếu n >= 2
hoặc theo định nghĩa trên wikipedia:
• F(n) = n nếu n < 2
• F(n) = F(n – 1) + F(n – 2) nếu n >= 2


Nặc danh nói...

Keep this going please, great job!

Feel free to visit my weblog bankruptcy florida


01:57 Ngày 16 tháng 03 năm 2013
viet huy nguyen nói...

bạn ơi cho mình hỏi bài toán này sử dụng giải thuật nào trong các giải thuật sau vậy
-giảm để trị
-quay lui
-vét cạn


22:33 Ngày 03 tháng 03 năm 2014
Pé Trịnh nói...

cho mình hỏi luôn: Cho trước số tự nhiên N, hãy tìm biểu diễn Fibonaci của số N.


20:33 Ngày 23 tháng 06 năm 2014
Nam Võ Tá nói...
Nhận xét này đã bị tác giả xóa.

Đăng nhận xét

Thành viên Blog

Tổng số lượt xem trang

Translate

Return to top of page Copyright © 2012 | Theme by Hack Tutors. Cung cấp bởi Blogger.
Các code pascal trong blog được sưu tầm, lựa chọn sao cho tối ưu nhất. Cảm ơn các tác giả đã viết thuật toán.