Tính tổng các số Fibonacci chẵn…

Problem 2: Even Fibonacci numbers

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Đề bài

Chuỗi Fibonacci được tạo bởi cách tính tổng 2 số liền kề thành số tiếp theo. Khởi đầu của chuỗi là 1 và 2, dưới đây là 10 số đầu tiên: 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, …

Hãy tính tổng các số chẵn trong chuỗi Fibonacci với giá trị lớn của chuỗi không quá 4 triệu.

Phân tích đề bài:

Giả sử chuỗi Fibonacci được biểu diễn: F1, F2, F3, F4, F5,…F(n) F3 = F1 + F2 F4 = F3 + F2 F5 = F4 + F3 …. F(n) = F(n - 1) + F(n - 2)

Yêu cầu thứ nhất của đề bài là F(n) < 4.000.000 (4 triệu) Yêu cầu thứ hai là tính tổng từ F1 –> F(n)

Cách giải “trâu bò”

Đọc đầu bài ta có thể tư duy ra giải một cách “nhanh nhất” đó là tạo một vòng lặp while, rồi lần lượt tính ra F(n) và điều kiện dừng lại là F(n) >= 4000000. Mỗi số được sinh ra sẽ được kiểm tra chẵn/lẽ và cộng dồn lại vào một biến sum_all.

def sum_fibonacci_under_4_million():
    fi_1st = 1
    fi_2nd = 2
    sum_even = fi_2nd
    fi_n = fi_1st + fi_2nd
    while fi_n < 4000000:
        if not fi_n % 2:
            sum_even += fi_n
        fi_1st, fi_2nd = fi_2nd, fi_n
        fi_n = fi_1st + fi_2nd
    return sum_even


if __name__ == "__main__":
    import time
    print("bruteforce fibonacci result:")
    start = time.time()
    print(sum_fibonacci_under_4_million())
    done = time.time()
    elapsed = done - start
    print("elapsed time: {}s".format(elapsed))



Nguyens-MacBook-Pro:PE-002 vinh.nguyenquang$ python bruteforce_pe002.py
bruteforce fibonacci result:
4613732
elapsed time: 3.00407409668e-05s
Nguyens-MacBook-Pro:PE-002 vinh.nguyenquang$ python bruteforce_pe002.py
bruteforce fibonacci result:
4613732
elapsed time: 2.19345092773e-05s
Nguyens-MacBook-Pro:PE-002 vinh.nguyenquang$

Với khoảng thời gian như trên, có thể mọi người đã muốn dừng lại và hài lòng với cách làm đã đưa ra.

Nhưng nên nhớ là chúng ta đang sử dụng Python. Không phải lo nghĩ đến khái niệm “big number”.

Áp dụng toán học vào giải bài toán PE-002:

Chú ý đến đề bài là chỉ tính tổng các số Fibonacii chẵn. Nếu có cách nào đó tính toán bỏ qua việc kiểm tra số chẵn/lẻ sẽ làm bài toán chạy nhanh hơn.

Với một chuỗi số đầu tiên:

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144,…

Sẽ tính tổng 2 + 8 + 34 + 144 + …

Tương đương với Fi(3) + Fi(6) + Fi(9) + Fi(12) + …

Fi(n) 
= Fi(n-1) + Fi(n-2)
= Fi(n-2) + Fi(n-3) + Fi(n-3) + Fi(n-4)      # Do Fi(n-1) =  Fi(n-2) + Fi(n-3) và   Fi(n-2) = Fi(n-3) + Fi(n-4)
= Fi(n-2) + 2 * Fi(n-3) + Fi(n-4)
= Fi(n-3) + Fi(n-4) + 2 * Fi(n-3) + Fi(n-5) + Fi(n-6)
= 3 * Fi(n-3) + Fi(n-4) + Fi(n-5) + Fi(n-6)
= 4 * Fi(n-3) + Fi(n-6)     # Do Fi(n-4) + Fi(n-5) = Fi(n-3)

Như vậy số Fi(n) = 4 * Fi(n-3) + Fi(n-6)

Áp dụng công thức với chuỗi phía trên: n = 9 –> Fi(9) = 4 * Fi(6) + Fi(3) = 4 * 8 + 2 = 34

n = 12 –> Fi(12) = 4 * Fi(9) + Fi(6) = 4 * 34 + 8 = 144

…

def sum_fibonacci_under_4_million():
    fi_n_6 = 2
    fi_n_3 = 8
    sum_even = fi_n_3 + fi_n_6
    fi_n = 4 * fi_n_3 + fi_n_6
    while fi_n < 4000000:
        sum_even += fi_n
        fi_n_3, fi_n_6 = fi_n, fi_n_3
        fi_n = 4 * fi_n_3 + fi_n_6
    return sum_even

Nguyens-MacBook-Pro:PE-002 vinh.nguyenquang$ python math_pe002.py
math fibonacci result:
4613732
elapsed time: 1.31130218506e-05s

Kết luận:

Thời gian chạy 2.19345092773e-05s và 1.31130218506e-05s, xứng đáng để chúng ta thực hiện tối ưu.

Source-code: PE-002