Dãy Fibonacci
Trong bài tập này, bạn sẽ hiện thực hóa dãy Fibonacci, một dãy số xuất hiện rất nhiều trong tự nhiên. Dãy số trông như thế này: "0, 1, 1, 2, 3, 5, 8…". Bạn sẽ tạo một thuật toán đệ quy để sinh ra dãy số này.
Hai số đầu tiên là 0 và 1, các số tiếp theo bằng tổng của hai số liền trước.
Ta có thể định nghĩa đệ quy dãy này như sau: \(fib(n)=fib(n-1)+fib(n-2)\), với \(fib(0)=0\) và \(fib(1)=1\), trong đó \(n\) là vị trí \(nth\) trong dãy.
Ở bước đầu, bạn sẽ viết Fibonacci bằng đệ quy. Ở bước thứ hai, bạn sẽ cải thiện bằng lập trình động, lưu lời giải của các bài toán con trong biến cache.
Bài tập này là một phần của khóa học
Cấu trúc dữ liệu và Thuật toán với Python
Bài tập tương tác thực hành trực tiếp
Hãy thử làm bài tập này bằng cách hoàn thành đoạn mã mẫu này.
def fibonacci(n):
# Define the base case
if ____ <= ____:
return n
else:
# Call recursively to fibonacci
____
print(fibonacci(6))