Tuesday 17 March 2015

Calculating Fibonacci series using Dynamic Programming

Normally using divide and conquer algorithm using recurrence relation the complexity reaches to O(2^n) i.e. exponentially 
We can reduce the time the time complexity of the same by avoiding doing the necessary work and saving using reusing our previous work using dynamic programming
Here is an example of the same.
#include<stdio.h>
int sdynamicfib(int);
int table[100]={-1};
int main()
{
 int n,i,temp ;
 printf("Calculating fibonnaci series using dynamic programming\n");
 printf("Enter n");
 scanf("%d",&n);
 for(i=0;i<=n;i++)
 {
     table[i]=-1;
 }
 temp=sdynamicfib(n);
 for(i=0;i<n;i++)
 {
     printf("%d",table[i]);
     printf(" ");
 }
    return 0;
}
int sdynamicfib(int n)
{
    if(n==0||n==1)
    {
        table[n]=n;
        return n;
    }
    else
    {
      if(table[n]==-1)
      {
          if(table[n-1]==-1)
            table[n-1]=sdynamicfib(n-1);
            if(table[n-2]==-1)
            table[n-2]=sdynamicfib(n-2);
          table[n]=table[n-1]+table[n-2];
          return table[n];
      }
    }
}
 Output











No comments:

Post a Comment