Tính tổng các số Fibonacci từ 1 tới 4 triệu

Cuối tuần này có nói chuyện với bác @haond về một đề tài khá là thú vị, đó là bài toán: Tính tổng các số Fibonacci từ 1 tới 4 triệu

Giải pháp đơn giản

Để tính một số Fibonacci thì cực kì đơn giản, chỉ cần làm theo công thức:

$F_{n}=F_{n-1}+F_{n-2}$

Code thì khá là đơn giản bằng cách dùng đệ quy:

func Fibonacci(n: Int) -> Int { if n <= 2 { return 1 } return Fibonacci(n - 1) + Fibonacci(n - 2)
}

Hoặc dùng vòng lặp để khử đệ quy:

func Fibonacci(n: Int) -> Int { var a = 0 var b = 1 var next = 0 for i in 0..<n { if i <= 1 { next = i } else { next = a + b a = b b = next } } return next
}

Quay lại bài toán tính tổng các số Fibonacci, ta có thể implement một hàm tính tổng đơn giản như sau:

func Sum(n: Int) -> Int { var sum = 0 for i in 0..<n { sum += Fibonacci(n) } return sum
}

Tuy nhiên thì với thuật toán như vậy, chúng ta có gặp phải vấn đề gì không?

Câu trả lời là có, vấn đề rất lớn!

Đầu tiên hãy nhìn vào đồ thị biểu diễn thời gian cần để tính Fibonacci dưới đây: