Chương trình Python tìm tổng dãy Fibonacci đến số hạng thứ n

Giả sử chúng ta có một số nguyên n. Nhiệm vụ là tìm tổng của n số hạng đầu tiên trong dãy Fibonacci. Nếu kết quả quá lớn, trả về kết quả modulo 10^8 + 7.

Ví dụ: với n = 8, dãy Fibonacci 8 số hạng đầu là 0, 1, 1, 2, 3, 5, 8, 13. Tổng của chúng là 33.

Thuật toán

Chúng ta sử dụng kỹ thuật đệ quy có nhớ (memoization) để tính toán hiệu quả:

• Khởi tạo m = 10**8 + 7 và một dictionary memo rỗng.
• Định nghĩa hàm solve(n, m):
  • Nếu n đã có trong memo, trả về memo[n].
  • Nếu n < 2, gán memo[n] = n.
  • Ngược lại, memo[n] = (solve(n-1, m) + solve(n-2, m)) % m.
  • Trả về memo[n].
• Từ hàm chính, gọi solve(n, m) để điền đầy đủ memo, sau đó tính tổng n giá trị đầu tiên trong memo.values().

Ví dụ mã nguồn

m = 10**8 + 7
memo = {}

def solve(n, m):
    if n in memo:
        return memo[n]
    memo[n] = n if n < 2 else (solve(n-1, m) + solve(n-2, m)) % m
    return memo[n]

n = 8
solve(n, m)
print(sum(list(memo.values())[:n]))

Đầu vào / Đầu ra

Input:  8
Output: 33