DIR Return Create A Forum - Home
---------------------------------------------------------
techsuns
HTML https://techsuns.createaforum.com
---------------------------------------------------------
*****************************************************
DIR Return to: Programming Questions
*****************************************************
#Post#: 283--------------------------------------------------
fibonacci series...
By: dinesh Date: November 30, 2012, 4:03 am
---------------------------------------------------------
code for finding nth fibonaccci number using dynamic programming
#Post#: 306--------------------------------------------------
Re: fibonacci series...
By: ktnv9 Date: December 3, 2012, 12:03 am
---------------------------------------------------------
1 /**** Program : Code to find nth fibonacci number using
dynamic programming
2 Please post your suggestions as
this may not be the best solution. **********/
3 #include <stdio.h>
4 #include <stdlib.h>
5 #include <ctype.h>
6
7 int fibonacci(int);
8
9 int main(int argc, char *argv[])
10 {
11 if (argc != 2)
12 {
13 printf("Usage: <./a.out><number>\n");
14 exit(1);
15 }
16
17 int num = atoi(argv[1]);
18
19 int fib = fibonacci(num);
20 printf("%d th fibonacci number is %d\n", num, fib);
21 }
22
23 int fibonacci(int num)
24 {
25 int i;
26 int arr[num]; //array which useful to remember the
previous fibonacci numbers
27
28 for (i = 0; i < num ; i++)
29 arr[i] = 0; //intialization
30
31 arr[0] = 1; //first two fibonacci numbers are stored
in arr[0],arr[1]
32 arr[1] = 1;
33
34 for (i = 2; i < num ; i++)
35 arr[i] = arr[i-1]+arr[i-2]; //fibonacci number
calculation
36
37 return arr[num-1];
38 }
#Post#: 307--------------------------------------------------
Re: fibonacci series...
By: dinesh Date: December 3, 2012, 2:23 am
---------------------------------------------------------
The above code is a solution for bottom-up dynamic programming.
Can you think of a top-down dynamic programming solution?
#Post#: 308--------------------------------------------------
Re: fibonacci series...
By: srini Date: December 3, 2012, 2:56 am
---------------------------------------------------------
@ktn: good one. small error: at line 35 , it should be arr[i] =
arr[i-1]+arr[i-2].
Can you give where you have applied dynamic programming?
what is the time and space complexity? ??? ???
*****************************************************