Máy tính Fibonacci

Công thức Fibonacci

Dãy Fibonacci được xác định bằng một hệ thức truy hồi đơn giản:

F(1) = 1
F(2) = 1
F(n) = F(n-1) + F(n-2)   với n > 2

Mỗi số hạng là tổng của hai số hạng liền trước. Máy tính này dùng quy ước F(1) = 1, F(2) = 1, nên dãy bắt đầu bằng 1, 1, 2, 3, 5, 8, 13, 21, 34, 55…

Một ví dụ có lời giải

Để tìm F(10), hãy cộng dần từng số hạng:

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

Vậy F(10) = 55. Tổng của mười số hạng đó là 143, và tỷ số của hai số hạng cuối, 55 / 34 ≈ 1,6176, đã gần với tỷ lệ vàng φ ≈ 1,6180339887.

Dãy số, tổng và tỷ lệ vàng

Một đẳng thức đẹp: tổng của n số Fibonacci đầu tiên bằng F(n+2) − 1. Với n = 10, ta có F(12) − 1 = 144 − 1 = 143, khớp với bảng.

Những lỗi thường gặp

• Cách đánh chỉ số khác nhau. Một số sách giáo khoa bắt đầu từ F(0) = 0. Công cụ này dùng F(1) = 1, F(2) = 1, vì vậy hãy dịch chỉ số đi một đơn vị nếu bạn so sánh với bảng dựa trên F(0).
• Tràn số dấu phẩy động. Tính các số Fibonacci lớn bằng số dấu phẩy động thông thường sẽ mất độ chính xác sau khoảng F(78). Máy tính này dùng số học số nguyên lớn chính xác, nên F(200) (một số có 42 chữ số) được trả về đầy đủ.
• Tỷ lệ vàng là một giới hạn, không phải một đẳng thức. F(n) / F(n-1) chỉ tiến gần tới φ; với n hữu hạn nó không bao giờ bằng đúng φ. Với các giá trị n nhỏ, độ lệch thấy rõ.