Answer to Question #328289 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

#include <stdio.h>
#include <windows.h>

//------this is for timing--------
long long Freq()
{
    LARGE_INTEGER f;
    QueryPerformanceFrequency(&f);
    return f.QuadPart;
}

long long Time()
{
    static long long freq = 0;
    if (freq == 0) freq = Freq();
    LARGE_INTEGER t;
    QueryPerformanceCounter(&t);
    return (t.QuadPart * 1000000L)/freq;
}
// ------------

int main()
{
  int startIndex, endIndex, middleIndex;
  int n;
  int array[] = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144};
  startIndex = 0;
  endIndex = sizeof(array)/sizeof(array[0]) - 1;
  printf("Array:\n");
  for(int i=0;i<endIndex+1;i++)
      printf("%d ", array[i]);
  printf("\nEnter n: ");    
  scanf("%d", &n);
  getchar();
  printf("\nOutput:");
 
  long long start = Time();

  while (startIndex <= endIndex)
  {
    middleIndex = startIndex + (int)((endIndex - startIndex) / 2);
    // If index is found, break and return index
    if (middleIndex == n)
      break;
    // Which half to choose: left or right one.
    if (middleIndex < n)
      // Go to the right half.
      startIndex = middleIndex + 1;
    else
      // Go to the left half.
      endIndex = middleIndex - 1;
  }
  printf("\n%d", array[middleIndex-1]);

  long long stop = Time();
  printf("\n\nRunning time algorithm: %lld mks\n",(stop-start));
}