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

Thanks You 

No comments:

Post a Comment

THANKS FOR UR GREAT COMMENT

Blogger Widgets