ulvis.paste.net - pastebin

Paste Search Dynamic
Recent pastes
count
  1. #include<stdio.h>
  2. #include<time.h>
  3.  
  4. #define int             long long
  5. #define NMAX            100
  6. #define time(a, b)      ((double) (b - a)) / CLOCKS_PER_SEC
  7.  
  8. int count;
  9.  
  10. int fib(int n) {
  11.         count++;
  12.         if(n < 3)
  13.                 return 1;
  14.         return fib(n-1) + fib(n-2);
  15. }
  16.  
  17. signed main() {
  18.         int n, f[NMAX];
  19.         f[0] = 1;
  20.  
  21.         clock_t start, end;
  22.  
  23.         // take n = 50 for your analysis
  24.         scanf("%lld", &n);
  25.        
  26.         for(int i = 1;i <= n;i++) {
  27.                 count = 0;
  28.                
  29.                 start = clock();
  30.                 fib(i);
  31.                 end = clock();
  32.                
  33.                 f[i] = count;
  34.                 // Compare this ratio(in printf) with phi (golden ratio)
  35.                 // see how time taken grows with n
  36.                 // is there any pattern in time taken??
  37.                 printf("fib(%lld) = %lld, ratio: %lf, time taken: %lf\n",
  38.                         i, count, (double)f[i]/f[i-1], time(start, end));
  39.         }
  40.         return 0;
  41. }
Parsed in 0.004 seconds