Posted By

jaircazarin on 10/10/08


Tagged

Algorithms Microsoft-Interview


Versions (?)

Who likes this?

4 people have marked this snippet as a favorite

jaircazarin
sergeizen
medikgt
skammer


Fibonacci


 / Published in: C
 

  1. #include<stdio.h>
  2. #define MAX 200
  3. /*
  4. F0 = 1.
  5. F1 = 1.
  6. Fn = Fn-1 + Fn-2
  7. */
  8.  
  9. int fibonacciRecursive(int n)
  10. {
  11. if(n == 0)
  12. return 0;
  13. if(n == 1)
  14. return 1;
  15. else
  16. return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);
  17. }
  18.  
  19. int fibonacciIterative(int n)
  20. {
  21. int a = 0;
  22. int b = 1;
  23. int fib;
  24. if(n == 0)
  25. return a;
  26. if(n == 1)
  27. return b;
  28. for(int i = 2; i <= n; i++)
  29. {
  30. fib = a + b;
  31. a = b;
  32. b = fib;
  33. }
  34. return fib;
  35. }
  36.  
  37. int fibonaccis[MAX];
  38.  
  39.  
  40. int fibonacciMemoization(int n)
  41. {
  42. if(n == 0)
  43. return 0;
  44. if(n == 1)
  45. return 1;
  46. if(fibonaccis[n])
  47. return fibonaccis[n];
  48. else
  49. {
  50. fibonaccis[n] = fibonacciMemoization(n-1)+ fibonacciMemoization(n-2);
  51. return fibonaccis[n];
  52. }
  53. }
  54.  
  55. int main()
  56. {
  57. for(int i = 0; i < MAX; i++)
  58. fibonaccis[i] = 0;
  59. printf("Fibonacci %d = %d\n", 0, fibonacciMemoization(0));
  60. printf("Fibonacci %d = %d\n", 2, fibonacciMemoization(2));
  61. printf("Fibonacci %d = %d\n", 3, fibonacciMemoization(3));
  62. printf("Fibonacci %d = %d\n", 4, fibonacciMemoization(4));
  63. printf("Fibonacci %d = %d\n", 5, fibonacciMemoization(5));
  64. printf("Fibonacci %d = %d\n", 6, fibonacciMemoization(6));
  65. printf("Fibonacci %d = %d\n", 7, fibonacciMemoization(7));
  66. printf("Fibonacci %d = %d\n", 8, fibonacciMemoization(8));
  67. printf("Fibonacci %d = %d\n", 13, fibonacciMemoization(13));
  68. printf("Fibonacci %d = %d\n", 16, fibonacciMemoization(16));
  69. printf("Fibonacci %d = %d\n", 19, fibonacciMemoization(19));
  70. printf("Fibonacci %d = %d\n", 20, fibonacciMemoization(20));
  71. printf("Fibonacci %d = %d\n", 20, fibonacciMemoization(40));
  72. return 0;
  73. }
  74.  
  75. /*
  76. F0 = 0
  77. F2 = 1
  78. F8 = 21
  79. F13 = 233
  80. F16 = 987
  81. F19 = 4181
  82. F20 = 6765
  83. */

Report this snippet  

You need to login to post a comment.