Points:
200 (p)
Time limit:
1.0s
Memory limit:
977M
Input:
stdin
Output:
stdout
"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 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 \(n\) là số tự nhiên khác 0, gọi \(f(n)\) là số đôi thỏ có ở tháng thứ \(n\), ta có:
- Với \(n=1\) ta được \(f(1)=1\).
- Với \(n=2\) ta được \(f(2)=1\).
- với \(n=3\) ta được \(f(3)=2\).
- Do đó với \(n>2\) ta được \(f(n)=f(n-1)+f(n-2)\).
Dãy số trên được gọi là dãy số Fibonacci (Link wikipedia) và được định nghĩa như sau:
- \(F_1=F_2=1\)
- \(F_n=F_{n-2}+F_{n-1}\)
Hãy viết chương trình tính \(n\) số Fibonacci đầu tiên.
Input
- Dòng đầu tiên và duy nhất chứa 1 số nguyên dương \(n\) \((1 \leq n \leq 90)\)
Output
- In \(n\) số Fibonacci đầu tiên trên 1 dòng.
Example
Test 1
Input
10
Output
1 1 2 3 5 8 13 21 34 55
Comments
Fan CR7 đã qua
n = int(input())
a = [1, 1]
c = 2
print(1,end = " ")
print(1,end = " ")
for i in range(n - 2):
a.append((a[i] + a[i + 1]))
c += 1
print(a[c - 1],end = " ")
người sau khi đọc được hết cái đề =))
fan Mu đã đi qua
This comment is hidden due to too much negative feedback. Click here to view it.
ez
ez
Simple implementation: