advanced code snippet search

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
 
Expand | Embed | Plain Text 
  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.