Fibo đầu tiên

Xem PDF
Tất cả bài nộp
Các bài nộp tốt nhất
Thời gian:
Scratch 5.0s
Bộ nhớ:
Scratch 256M
Tác giả:
admin
Dạng bài
Điểm: 200 (p) Thời gian: 1.0s Bộ nhớ: 977M Input: bàn phím Output: màn hình

"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

Bình luận


  • 21
    SPyofgame    5:37 p.m. 3 Tháng 6, 2020 ← chỉnh sửa 2

    Simple implementation:

    void print_fibonacci(int n) 
{ 
    if (n >= 1) cout << 1 << ' '; 
    for (ll a = 0, b = 1; --n; a = (b += a) - a) cout << a + b << ' ';
}

    • 1
      tkvinhtruongquang    4:08 p.m. 14 Tháng 9, 2021

      ủa anh ơi cho em hỏi là cái b+=a đó chỉ cần bỏ vô trong ngoặc là xong anh à, ảo ma vậy , em lúc trước không biết làm cái b+=a đó riêng nên nó dài dòng hơn tí :))

    6 bình luận nữa