## Wednesday, 25 March 2015

### Fibonacci Series

Fibonacci series => 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

I`th number in series is sum of (i-1)th & (i-2)th number in series where first two number in series are 0 & 1 ,these are base case for Fibonacci series.

If Fibonacci(n) represent n`th number in Fibonacci series .
then
Fibonacci(0) = 0
Fibonacci(1) = 1
.
.
.
Fibonacci(n) = Fibonacci(n-1)+Fibonacci(n-2)

Using Iteration you can easily find nth Fibonacci number .

Recursive Method for Finding n`th fibonacci Number .

1. //C Program
2. // Recursive way of finding nth fibonacci number
3. // http://beginer2cs.blogspot.com
4. #include<stdio.h>
5. int fibo_recursion(int n)
6. {
7.    //base case
8.    if(n==0)
9.       return 0;
10.    else if(n==1) //base case
11.            return 1;
12.         else
13.            return (fibo_recursion(n-1)+fibo_recursion(n-2));
14. }
15. main(){
16. int n;
17. printf("Enter n: ");
18. scanf("%d",&n);
19. printf(" %d th Fibonacci number is = %d \n",n,fibo_recursion(n));
20. }
\
This Approach is also called top down approach . this is very inefficient way of calculating n`th Fibonacci number as many calculation is repeated  we can see in this graph
Dynamic Programming Approach reduce calculation Very efficiently . In this approach we store result of each calculation for further use in future & We fallow bottom-top approach instead of top-bottom approach (previous approach).
In bottom-top approach  we first calulate 1st then 2nd ....... then n`th  element .

Now Lets Solve a ProjectEuler question based on This Approach
1. 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:
2.                                        1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
3. By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.
1. //C Program
2. //We gonna Use bottom up approch i.e Dynamic Programming aprroch
3. //http://beginer2cs.blogspot.com
4. //ProjectEuler Q2
5. #include<stdio.h>
6. main(){
7.   long int Even_sum=0;
8.   int arr[10000];
9.   int i;
10.   //base case
11.   arr[0]=1; //requirement of this particuler Question
12.   arr[1]=1;
13.   for(i=2;i<10000;i++){
14.        arr[i]=arr[i-1]+arr[i-2]; //store result in array
15.        if(arr[i]>=4000000)       //i`th index of array represent i`th Fibonacci number
16.              break;
17.        else
18.           if(arr[i]%2==0)
19.              Even_sum =Even_sum+arr[i];
20.    }
21. printf("Sum of Even Fibbo Number bellow 4 million is = %ld\n",Even_sum);
22. }

Output is : Sum of Even Fibbo Number bellow 4 million is = 4613732
HoW number of calculation reduces in this approch