Bài toán con thỏ và bài toán con ong năm 2024

Dãy số Fibonacci được Fibonacci, một nhà toán học người Ý, công bố vào năm 1202 trong cuốn sách Liber Abacci - Sách về toán đồ qua 2 bài toán: Bài toán con thỏ và bài toán số các "cụ tổ" của một ong đực.

Henry Dudeney (1857 - 1930) (là một nhà văn và nhà toán học người Anh) nghiên cứu ở bò sữa, cũng đạt kết quả tương tự.

Thế kỉ XIX, nhà toán học Edouard Lucas xuất bản một bộ sách bốn tập với chủ đề toán học giải trí, ông đã dùng tên Fibonacci để gọi dãy số kết quả của bài toán từ cuốn Liber Abaci -- bài toán đã sinh ra dãy Fibonacci.

Trong các buổi học Algorithm ProPTIT thì bài toán Fibonacci đã quá đơn giản với mọi người cho nên \t{Skynet} đã nâng cấp bài toán Fibonacci cho thêm phần thú vị hơn nhưng vẫn rất đơn giản để mọi người "\t{thừa sức làm được!}". Bản nâng cấp đó là Dãy xâu Fibonacci:

Một dãy xâu ký tự \t{G} chỉ bao gồm các chữ cái \t{A} và \t{B} được gọi là dãy xâu Fibonacci nếu thỏa mãn tính chất:

Caption :

[ DÃY FIBONACCI VÀ NHỮNG BÍ ẨN TRONG TỰ NHIÊN ]

Cuộc sống xung quanh ta luôn tồn tại vô vàn những điều thú vị. Có bao giờ bạn

tự hỏi: “vì sao hoa cúc vạn thọ có 13 cánh, hoa cúc tây có 21 cánh, hoa cúc

thường có 34 hoặc 55 hoặc 89 cánh ?” Phải chăng các con số này đều tuân

theo quy luật của một dãy số nào đó? Đúng là như vậy, các con số này đều là

các số hạng của dãy Fibonacci – một dãy số gắn liền với tên tuổi của nhà toán

học người Ý. Để biết rõ hơn về dãy Fibonacci và những bí ẩn trong tự nhiên,

hãy đồng hành cùng để team chúng tớ trong clip này nhé.

Nội dung:

Đầu tiên chúng ta tìm hiểu về nguồn gốc

Nhà toán học Fibonacci ( 1170-1240), tên đầy đủ của ông là Leonardo Pisano,

được biết đến như một nhà toán học vĩ đại nhất của châu Âu thời trung cổ.

Dãy số Fibonacci được công bố vào năm 1202, được tìm ra qua 2 bài toán kinh

điển: bài toán con thỏ và bài toán số "cụ tổ" của một con ong đực.

Trước hết về b ài toán con thỏ : Bắt đầu với một thỏ đực và một thỏ cái, trong

điều kiện lý tưởng, Finonnaci muốn tính số cặp thỏ có được ở 1 tháng bất kỳ.

Sau khi ông thống kê thì thấy rằng:

Sau một tháng, cặp thỏ ban đầu chưa thuần thục sinh dục và không thể giao

phối.

Nội dung Text: Dãy số Fibonacci và bài toán nuôi thỏ

1. 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)
2. 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) Cài đặt hàm tính Fn băng ngôn ngữ C++ //Cài đặt đệ quy bình thường int F(int n) { if (n
3. if (n
4. Fn_1=Fn; } return Fn; } Cài đặt bài toán nuôi thỏ bằng ngôn ngữ Pascal 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;
5. 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