Fibo đầu tiên

View as PDF

Submit solution

Points: 100 (partial)
Time limit: 1.0s
Scratch 5.0s
Memory limit: 977M
Scratch 256M
Input: stdin
Output: stdout

Author:
Problem types

"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 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).

Nguồn: wikipedia

Dãy số trên gọi là dãy số Fibonacci 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 in n số Fibonacci đầu tiên:

Dữ liệu vào:

  • Chứa duy nhất số n (n≤90)

Kết quả:

  • Chỉ một dòng ghi n số Fibonaci đầu tiên

Ví dụ:

Input

10

Output

1 1 2 3 5 8 13 21 34 55

View comments (5)

Comments


  • -1
    thanhkhoa123  commented on 4:10 p.m. 4 jun, 2022

    ez


  • -1
    tkvinhtruongquang  commented on 2:57 p.m. 14 sep, 2021

    ez


  • 13
    SPyofgame  commented on 5:37 p.m. 3 jun, 2020 edit 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 << ' ';
    } 
    

    • 0
      tkvinhtruongquang  commented on 4:08 p.m. 14 sep, 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í :))


      • 1
        SPyofgame  commented on 11:32 p.m. 14 sep, 2021

        được