1. Học hỏi
    2. /
  2. Khoa Học
    3. /
  3. Cấu trúc dữ liệu và Thuật toán với Python
Connected

Bài tập

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.

Hướng dẫn 1/2

undefined XP
  • 1
    • Xác định trường hợp cơ sở.
    • Gọi hàm fibonacci() một cách đệ quy.
  • 2
    • Kiểm tra giá trị có tồn tại trong cache hay không.
    • Lưu kết quả vào cache để tránh tính lại về sau.