Bài toán: Họ hàng nhà thỏ và số Fibonaci

Bài toán sau đây được đặt bởi Fibonaci vào thế kỷ thứ 13 trong tác phẩm của ông mang tên Liber abaci

Một cặp thỏ mới sinh ( một đực và một cái ) được thả lên một hòn đảo. Giả sử rằng cặp thỏ chưa sinh sản trước khi đầy 2 tháng. Từ khi chúng chưa đầy 2 tháng tuổi, mỗi tháng chúng sinh được 1 đôi thỏ ( đực  và cái). Tìm công thức truy hồi tính số cặp thỏ trên đảo sau n tháng với giả thiết thỏ trường thọ

Giải:

Giả sử fn là số cặp thỏ sau n tháng.

Ta thấy cuối tháng thứ nhất số cặp thỏ trên đảo là f1.

Vì số cặp thỏ vẫn chưa sinh sản được ở tháng tiếp theo nên f2 =1.

Để tìm số thỏ hiện tại ta cộng cặp thỏ tháng trước và số thỏ vừa mới sinh ra trong tháng này.

Vì số cặp thỏ mới sinh ra bằng với số thỏ ít nhất 2 tháng tuổi, nên số này bằng f(n-2)

f(n) = f(n-1) + f( n-2 )

// Tinh so tho tai tháng thu n
#include<iostream>
#include<iomanip.h>

using namespace std;


long double so_tho( int n)
{
    if (n < 3) return 1 ;// chua day 2 thang tuoi tra ve 1 cap tho
    else return ( so_tho( n-1) + so_tho( n-2));
}

int main()
{
    int n; cin >> n;
    cout<< setiosflags(ios::showpoint|ios::fixed) << setprecision(0);
    cout<< "\nSo tho: " << so_tho(n)<< endl;
    system("pause");
    return 0;
}