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
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