grade lớp 11 level chuyên để difficulty easy updated 04/10/2026

Dãy Fibonacci

Tóm lược nội dung

Bài này trình bày bài toán dãy Fibonacci bằng kỹ thuật đệ quy.

Bài toán

Dãy số Fibonacci được định nghĩa như sau:

• \(F_0 = 0\)
• \(F_1 = 1\)
• \(F_n = F_{n - 1} + F_{n - 2} \quad \text{với } n \ge 2\)

Yêu cầu:
Sử dụng kỹ thuật đệ quy, viết chương trình xác định giá trị của số Fibonacci thứ \(n\).

Input:
Số nguyên không âm \(n\).

Output:
Giá trị của số Fibonacci thứ \(n\).

Test case:

STT	Input	Output
1	0	0
2	1	1
3	2	1
4	3	2
5	4	3
6	5	5
7	10	55
8	30	832040

---

Bài giải đề xuất

Ý tưởng chính

1. Trường hợp cơ sở:

   Bài toán này có hai trường hợp cơ sở:

   • Khi \(n = 0\): trả về 0.
   • Khi \(n = 1\): trả về 1.

2. Trường hợp đệ quy:

   Khi \(n \ge 2\): trả về \(F_n = F_{n - 1} + F_{n - 2}\).

Ví dụ:
Sơ đồ dưới đây minh họa quá trình tính \(\text{fibonacci}(4)\):

%%{
init: {
    'theme': 'default',
    'look': 'classic',
    'flowchart': { 'padding': 15 }
}
}%%
flowchart TD
    F4["fibonacci(4)"] --> F3["fibonacci(3)"]
    F4 --> F2_1["fibonacci(2)"]

    F3 --> F2_2["fibonacci(2)"]
    F3 --> F1_1["fibonacci(1) = 1"]

    F2_1 --> F1_2["fibonacci(1) = 1"]
    F2_1 --> F0_1["fibonacci(0) = 0"]

    F2_2 --> F1_3["fibonacci(1) = 1"]
    F2_2 --> F0_2["fibonacci(0) = 0"]

    classDef root fill:#e0f2fe,stroke:#0284c7,color:#0369a1,rx:1.5rem,ry:1.5rem
    classDef base1 fill:#fef3c7,stroke:#d97706,color:#92400e,rx:1.5rem,ry:1.5rem
    classDef base0 fill:#fce7f3,stroke:#db2777,color:#9d174d,rx:1.5rem,ry:1.5rem

    class F4,F3,F2_1,F2_2 root
    class F1_1,F1_2,F1_3 base1
    class F0_1,F0_2 base0

Viết chương trình

1. Viết hàm fibonacci().

Hàm gồm có một tham số là n và giá trị trả về là số Fibonacci thứ n.

def fibonacci(n):
    # Trường hợp cơ sở
    if n == 0:
        return 0

    if n == 1:
        return 1

    # Trường hợp đệ quy
    return fibonacci(n - 1) + fibonacci(n - 2)

2. Viết chương trình chính:

• Cho người dùng nhập vào một số nguyên không âm, lưu vào biến number.
• Gọi hàm fibonacci() ra thực hiện, lưu kết quả vào biến result.
• In ra kết quả.

if __name__ == '__main__':
    number = int(input('Nhập số nguyên không âm: '))

    result = fibonacci(number)
    print(f'Fibonacci[{number}] = {result}')

3. Chạy chương trình, nhập vào 10, kết quả như sau:

Nhập số nguyên không âm: 10
Fibonacci[10] = 55

---

Mã nguồn

Code đầy đủ được đặt tại:

• Google Colab
• GitHub