These days I learned the famous Fibonacci Sequence. Fibonacci Sequence was first discovered by Leonardo Fibonacci(1170 - 1250) to calculate the number of rabbits in a certain circumstance. In mathematics, they are numbers in the following integer sequence:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
And the sequence is related to the Golden ratio. We can see it everywhere in our lives, from architectures like Parthenon, to paintings and designs, as well as in nature.
In the book The Da Vinci Code by Dan Brown, a interesting paragraph is concerned with the Fibonacci Sequence:（And here is a link from Google Books.)
Langdon couldn’t tear his eyes from the glowing purple text scrawled across the parquet floor. Jacques Saunière’s final communication seemed as unlikely a departing message as any Langdon could imagine.
The message read：
13-3-2-21-1-1-8-5
O， Draconian devil！
Oh， lame saint！
Although Langdon had not the slightest idea what it meant， he did understand Fache’s instinct that the pentacle had something to do with devil worship.
It is easy to find out that the sequence of numbers is concerned with Fibonacci Sequence. Besides, Leonardo da vinci, the person why the book is named after, has the same forename as Leonado Finbonacci!
The Fibonacci sequence is widely used in algorithms and data structures. In one cases, it was important in Euclid’s algorithm to determine the greatest common divisor(gcd) of two intergers, where we can prove that the worst case input for this algorithm is a pair of consequtive Fibonacci numbers.
Below is an example of the algorithm:
Input: a nonnegative integers n
Output: Fn
Method:
int f[N]
F(n){
if(f[n] >= 0) return f(n); //The number is stored in memory once calculated, returned when needed.
f[n] = F(n-1) + F(n-2); //Here is the calculation.
return f[n];
}
int main()
{
read n;
f[0] = 0; f[1] = 1;
for (i = 2; i <= n; i++)
f[i] = -1 //It is used to determine if f[n] is calculated.
print f(n)
}–