"Một đôi thỏ (gồm một thỏ đực và một thỏ cái) cứ mỗi tháng đẻ được một đôi thỏ con (cũng gồm một thỏ đực và thỏ cái); một đôi thỏ con, khi tròn 2 tháng tuổi, sau mỗi tháng đẻ ra một đôi thỏ con, và quá trình sinh nở cứ thế tiếp diễn. Hỏi sau n tháng có bao nhiêu đôi thỏ, nếu đầu năm (tháng Giêng) có một đôi thỏ sơ sinh
Trong hình vẽ trên, ta quy ước:
Cặp thỏ nâu là cặp thỏ có độ tuổi 1 tháng.
Cặp thỏ được đánh dấu (màu đỏ và màu xanh) là cặp thỏ có khả năng sinh sản.
Nhìn vào hình vẽ trên ta nhận thấy:
Tháng Giêng và tháng Hai: Chỉ có 1 đôi thỏ.
Tháng Ba: đôi thỏ này sẽ đẻ ra một đôi thỏ con, do đó trong tháng này có 2 đôi thỏ.
Tháng Tư: chỉ có đôi thỏ ban đầu sinh con nên đến thời điểm này có 3 đôi thỏ.
Tháng Năm: có hai đôi thỏ (đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Ba) cùng sinh con nên ở tháng này có 2 + 3 = 5 đôi thỏ.
Tháng Sáu: có ba đôi thỏ (2 đôi thỏ đầu và đôi thỏ được sinh ra ở tháng Tư) cùng sinh con ở thời điểm này nên đến đây có 3 + 5 = 8 đôi thỏ.
Khái quát, nếu nn là số tự nhiên khác 0, gọi f(n)f(n) là số đôi thỏ có ở tháng thứ nn, ta có:
Với n=1n=1 ta được f(1)=1.f(1)=1.
Với n=2n=2 ta được f(2)=1.f(2)=1.
Với n=3n=3 ta được f(3)=2.f(3)=2.
Do đó với n>2n>2 ta được: f(n)=f(n−1)+f(n−2)f(n)=f(n−1)+f(n−2).
Nguồn: wikipedia
Dãy số trên gọi là dãy số FibonacciFibonacci và được định nghĩa như sau:
F1=F2=1;F1=F2=1;
……
Fn=Fn−2+Fn−1Fn=Fn−2+Fn−1
Hãy viết chương trình in nn số FibonacciFibonacci đầu tiên:
Dữ liệu vào:
Chứa duy nhất số nn (n≤90n≤90)
Kết quả:
Chỉ một dòng ghi nn số Fibonaci đầu tiên
Ví dụ:
Input
10
Output
1 1 2 3 5 8 13 21 34 55
#include <iostream>
#include <vector>
using namespace std;
class dynamic_prog {
public:
dynamic_prog(int n){
vector<long long> ans(n + 1);
ans[0] = 0;
ans[1] = 1;
for(int i = 2; i <= n; ++i){
ans[i] = ans[i - 1] + ans[i - 2];
}
for(int i = 1; i <= n; ++i){
cout << ans[i] << ' '
}
}
~dynamic_prog(){}
};
int main(){
int n;
cin >> n;
dynamic_prog obj(n);
}
bài mình làm, chúc bạn may mắn :)
