Friday, 16 November 2012

Vài điều thú vị về chuỗi Fibonacci

Bất cứ ai từng học lập trình cũng sẽ 1 lần làm bài toán tính số Fibonacci thứ n. Công việc chẳng có gì khó khăn khi dùng hàm đệ quy hay 1 vòng lặp đơn giản. Vậy nhưng còn nhiều điều dù chẳng phải bí ẩn gì nhưng có thể bạn ... chưa biết :D

Với công thức dưới đây bạn có thể

Tính số Fibonacci thứ n chỉ với các phép tính cộng, trừ, chia, căn:

Trích nguyên từ wiki [1]  

(Chuột phải chọn view image để xem ảnh rõ hơn) 

Closed-form expression

Like every sequence defined by a linear recurrence with constant coefficients, the Fibonacci numbers have a closed-form solution. It has become known as Binet's formula, even though it was already known by Abraham de Moivre:[18]
F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5}
where

\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\cdots\,
is the golden ratio (sequence A001622 in OEIS), and
\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\cdots
Implement nhanh trên python:

https://github.com/hvnsweeting/FAMILUG/blob/master/Python/fib_o1.py

OUTPUT
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13
8 21
9 34
10 55
11 89

 

Dãy Fibonacci là dãy tổng các đường chéo "lệch" của tam giác Pascal



Và cái clip này chắc ai cũng xem rồi:


[1] http://en.wikipedia.org/wiki/Fibonacci_number