Thuật toán in dãy số Fibonacci đã được trình bày trong phần thuật toán số học. Tuy nhiên, đây cũng là bài toán có thể biểu diễn bằng phương pháp đệ quy, nên trong bài học này chúng ta sẽ biểu diễn lại bài toán này bằng thuật toán đệ quy.
Yêu cầu
Viết chương trình để nhận một số n sau đó in ra chữ số thứ n trong dãy Fibonacci.
Phân tích và tìm cách giải
- Đầu vào: nhập vào giá trị n
- Đầu ra: In ra n số Fabonacci đầu tiên
- Cơ sở lý thuyết:
- – Dãy fibonacci: 1,1,2,3,5,8,13,21,34,55…
- – Bước cơ sở: f(0) =1, f(1) = 1
- – Bước đệ qui: f(n)= f(n-1) + f(n-2)
Cách biểu diễn thuật toán in dã số Fibonacci
Trong trường hợp này, tôi sử dụng ngôn ngữ giả.
Declare int n
Input n
If n<0
Print ‘n phai lon hon hoac bang 0 ’
Else
Print Fibonacci (n)
Fibonacci (n){
If n=0 or n=1
Return 1
Else
Return Fibonacci (n-1) + Fibonacci (n-2)
}
