Fibonacci Numbers

One famous question about Fibonacci numbers is about rabbits. Say rabbits are able to mate at the age of one month, and pregnancy takes one month. Thus, at the end of its second month, a female can produce another pair of rabbits. Rabbits never die, and a mating pair always produces one new pair (one male, one female) every month from the second month on. The puzzle that Fibonacci posed was if we start with a new pair from birth, how many pairs will there be in one year ?

To solve this problem we are using the following formula : f(n-1)+f(n-2)=f(n). This can be done in recursive and iterative. I prefer the iterative version because in iterative we can do in O(1) memory and O(n) time.

Here is the C++ code to calcute the fibonnacci numbers to the nth term:

int prev1=1,prev2=1;

for (int i=2; i<n; ++i){

   swap(prev1,prev2);

   prev2=prev1+prev2;

}

cout << prev2;

Another way to calculate Fibonnacci number. If Fn is the nth Fibonacci number then :

This is Binet's formula