Bài FIBONACI Pascal

Tìm hiểu về dãy số Fibonacci

Võ Công Chương
Qua tìm hiểu và tổng hợp các nghiên cứu của các tác giả về dãy số Fibonacci từ internet, tôi thấy có nhiều thông tin mà theo tôi là hấp dẫn như sự ra đời của số Fibonacci, nhà toán học Fibonacci là ai, các giải thuật để tính số Fibonacci. Tôi xin chia sẻ cùng bạn đọc. 1. Định nghĩa dãy số Fibonacci Trong Toán học, các số Fibonacci là một dãy số, kí hiệu F(n) (n là số nguyên không âm), được định nghĩa một cách đệ quy theo công thức sau:
Dãy bắt đầu từ hai số F(0)=0 và F(1)=1. Như vậy, các số đầu tiên của dãy Fibonacci là: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765. 2. Sự ra đời của số Fibonacci Xuất phát từ bài toán về sự gia tăng số lượng của đàn thỏ, gọi là bài toán đàn thỏ: Bắt đầu từ một cặp thỏ con, sau 12 tháng, ta sẽ có bao nhiêu cặp thỏ trong đàn nếu giả sử: - Tháng đầu tiên, chỉ có một cặp thỏ vừa mới sinh (nói vui là thỏ Adam và Eve), - Các cặp thỏ vừa mới sinh trở thành các cặp có khả năng sinh sản sau hai tháng, - Mỗi tháng, mọi cặp thỏ trên hai tháng tuổi đều sinh ra một cặp mới, và - Những con thỏ không bao giờ chết. Điều giả sử cuối cùng là hơi vô lí nhưng nó đã làm cho bài toán trở nên đơn giản hơn, có một số tài liệu đã thay đổi giả sử này thành `các cặp thỏ sẽ chết sau k tháng nào đó`, nhưng bản chất của bài toán cơ bản là không thay đổi nhiều. Một số giả sử khác là hiển nhiên nên không nêu ra như thỏ không chạy trốn khỏi đàn và không bị vô sinh. Theo giả sử, mỗi cặp thỏ trên hai tháng tuổi đều cho ra đời một cặp thỏ con mỗi tháng, điều đó có nghĩa rằng, tất cả `á cặp thỏ đang sống ở tháng thứ n sẽ cho ra đời `á cặp thỏ con khác ở tháng thứ n+2. Điều đó lí giải tại sao ta tính số cặp thỏ ở tháng thứ n+2 chính là số cặp thỏ ở tháng thứ n+1 (có `b` cặp) cộng thêm số cặp thỏ ở tháng thứ n (có `á cặp). Ta biểu diễn số cặp thỏ trong đàn như một hàm theo thời gian, F(n) (n là số tháng): F(1) = 1 - ta bắt đầu với một cặp thỏ mới sinh, F(2) = 1 - chúng còn nhỏ nên chưa thể có con sau một tháng, F(3) = 2 - đến tháng thứ ba, chúng sinh được một cặp thỏ con. F(4) = 3 - đến tháng thứ tư, chúng lại sinh một cặp thỏ con nữa, F(5) = 5 - đến tháng này, ngoài cặp thỏ con, chúng có thêm một cặp thỏ cháu nữa. Tổng quát, F(n) = F(n - 1) + F(n - 2), tức là tất cả các cặp thỏ sống ở tháng trước vẫn còn là F(n - 1) cộng thêm các cặp thỏ con của mỗi cặp thỏ sống ở tháng thứ n-2, tức F(n - 2). Rõ ràng, công thức tính F(n) ở trên áp dụng cho bài toán đàn thỏ. Câu trả lời của bài toán trên đã tạo ra dãy số: 1, 2, 3, 5, 8, 13, 21... mà sau này ta gọi là dãy số Fibonacci. Đến đây, ta sẽ đặt ra câu hỏi là tại sao dãy số lại có tên là dãy Fibonacci? 3. Leonardo là người phát minh ra dãy số Fibonacci? Theo giáo sư D.E.Knuth (trường đại học Stanford, http://www-cs-faculty.stanford.edu) dẫn chứng trong tập sách nổi tiếng The Art of Computer Programming, Volume 1, Fundamental Algorithms , dãy số này lần đầu tiên được tranh luận bởi các nhà Toán học ấn Độ, trong đó có Gopala và Hemachandra, những người đã mô tả một cách chính xác dãy số 1, 2, 3, 5, 8, 13, 21... Còn ở Tây Âu, dãy số này lần đầu tiên được nghiên cứu một cách đầy đủ bởi nhà Toán học Leonardo of Pisa , người có biệt danh là Fibonacci, và cũng từ đó mà dãy số có tên là dãy Fibonacci. Trong cuốn sách Liber Abaci, Fibonacci chủ yếu nghiên cứu về các con số (dạng hình tượng) và việc tính toán số học của người ấn Độ đang được sử dụng ở nhiều quốc gia khắp Địa Trung Hải. Vì vậy, bài toán