Bỏ qua

Dãy Fibonacci

Tóm lược nội dung

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

Bài toán

Yêu cầu:

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

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

Viết chương trình xác định số Fibonacci thứ n.

Đầu vào:

Số nguyên dương n.

Đầu ra:

Số Fibonacci thứ n.

Bộ kiểm thử:

STT Đầu vào Đầu ra
1 0 0
2 1 1
3 2 1
4 3 2
5 4 3
6 5 5
7 10 55
8 30 832040

Cách 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ở:

    • n == 0: trả về giá trị 0.
    • n == 1: trả về giá trị 1.

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

    Hàm đệ quy gọi lại chính nó theo công thức truy hồi \(F_n = F_{n - 1} + F_{n - 2}\).

Viết chương trình

1. Viết hàm fibonacci() dùng để tìm số Fibonacci.

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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 dương, 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ả.
13
14
15
16
17
if __name__ == '__main__':
    number = int(input('Nhập n nguyên dương: '))

    result = fibonacci(num)
    print(f'Số Fibonacci thứ {num} là {result}')

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

Nhập n nguyên dương: 10
Fibonacci[10] = 55

Mã nguồn

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

Bao tôi ly cafe 🧋 nhé!