Answer to Question #328252 in C for Mominul

Question

Suppose you are given a sequence of numbers as follows I, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144. .Now. you want to find the n number of the sequence i.e.. if you input n-7, program will give you output 13, for n=10, output=55. You MUST use dynamic programming technique to solve this problem and implement your solution in C language. What is the running time of your algorithm (write it in your text file).

Answer 1

The running time of the program is O(n)

#include <stdio.h>
#include <stdlib.h>

int main() {
    int n, i;
    long *fib;

    printf("Enter a number: ");
    scanf("%d", &n);
    fib = (long*) malloc(n*sizeof(long));
    fib[0] = fib[1] = 1;

    for (i=2; i<n; i++) {
        fib[i] = fib[i-1] + fib[i-2];
    }


    printf("The %d-th number in the sequence is %ld", n, fib[n-1]);
    free(fib);

    return 0;
}