剑指offer——面试题10：斐波那契数列

个人答案：

 1 #include"iostream"
 2 #include"stdio.h"
 3 #include"string.h"
 4 using namespace std;
 5 typedef long long ll;
 6 const int MAXN=10000;
 7 
 8 ll fib[MAXN];
 9 ll Fibonacci(int n)
10 {
11     if(fib[n]!=-1)
12         return fib[n];
13     return fib[n]=Fibonacci(n-1)+Fibonacci(n-2);
14 }
15 
16 int main()
17 {
18     int n;
19     memset(fib,-1,sizeof(fib));
20     fib[0]=0;
21     fib[1]=1;
22     while(cin>>n)
23     {
24         cout<<Fibonacci(n)<<endl;
25     }
26     return 0;
27 }

View Code

官方答案：

  1 // 面试题10：斐波那契数列
  2 // 题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。
  3 
  4 #include <cstdio>
  5 
  6 // ====================方法1：递归====================
  7 long long Fibonacci_Solution1(unsigned int n)
  8 {
  9     if(n <= 0)
 10         return 0;
 11 
 12     if(n == 1)
 13         return 1;
 14 
 15     return Fibonacci_Solution1(n - 1) + Fibonacci_Solution1(n - 2);
 16 }
 17 
 18 // ====================方法2：循环====================
 19 long long Fibonacci_Solution2(unsigned n)
 20 {
 21     int result[2] = {0, 1};
 22     if(n < 2)
 23         return result[n];
 24 
 25     long long  fibNMinusOne = 1;
 26     long long  fibNMinusTwo = 0;
 27     long long  fibN = 0;
 28     for(unsigned int i = 2; i <= n; ++ i)
 29     {
 30         fibN = fibNMinusOne + fibNMinusTwo;
 31 
 32         fibNMinusTwo = fibNMinusOne;
 33         fibNMinusOne = fibN;
 34     }
 35 
 36      return fibN;
 37 }
 38 
 39 // ====================方法3：基于矩阵乘法====================
 40 #include <cassert>
 41 
 42 struct Matrix2By2
 43 {
 44     Matrix2By2
 45     (
 46         long long m00 = 0, 
 47         long long m01 = 0, 
 48         long long m10 = 0, 
 49         long long m11 = 0
 50     )
 51     :m_00(m00), m_01(m01), m_10(m10), m_11(m11) 
 52     {
 53     }
 54 
 55     long long m_00;
 56     long long m_01;
 57     long long m_10;
 58     long long m_11;
 59 };
 60 
 61 Matrix2By2 MatrixMultiply
 62 (
 63     const Matrix2By2& matrix1, 
 64     const Matrix2By2& matrix2
 65 )
 66 {
 67     return Matrix2By2(
 68         matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
 69         matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
 70         matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
 71         matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
 72 }
 73 
 74 Matrix2By2 MatrixPower(unsigned int n)
 75 {
 76     assert(n > 0);
 77 
 78     Matrix2By2 matrix;
 79     if(n == 1)
 80     {
 81         matrix = Matrix2By2(1, 1, 1, 0);
 82     }
 83     else if(n % 2 == 0)
 84     {
 85         matrix = MatrixPower(n / 2);
 86         matrix = MatrixMultiply(matrix, matrix);
 87     }
 88     else if(n % 2 == 1)
 89     {
 90         matrix = MatrixPower((n - 1) / 2);
 91         matrix = MatrixMultiply(matrix, matrix);
 92         matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
 93     }
 94 
 95     return matrix;
 96 }
 97 
 98 long long Fibonacci_Solution3(unsigned int n)
 99 {
100     int result[2] = {0, 1};
101     if(n < 2)
102         return result[n];
103 
104     Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
105     return PowerNMinus2.m_00;
106 }
107 
108 // ====================测试代码====================
109 void Test(int n, int expected)
110 {
111     if(Fibonacci_Solution1(n) == expected)
112         printf("Test for %d in solution1 passed.\n", n);
113     else
114         printf("Test for %d in solution1 failed.\n", n);
115 
116     if(Fibonacci_Solution2(n) == expected)
117         printf("Test for %d in solution2 passed.\n", n);
118     else
119         printf("Test for %d in solution2 failed.\n", n);
120 
121     if(Fibonacci_Solution3(n) == expected)
122         printf("Test for %d in solution3 passed.\n", n);
123     else
124         printf("Test for %d in solution3 failed.\n", n);
125 }
126 
127 int main(int argc, char* argv[])
128 {
129     Test(0, 0);
130     Test(1, 1);
131     Test(2, 1);
132     Test(3, 2);
133     Test(4, 3);
134     Test(5, 5);
135     Test(6, 8);
136     Test(7, 13);
137     Test(8, 21);
138     Test(9, 34);
139     Test(10, 55);
140 
141     Test(40, 102334155);
142 
143     return 0;
144 }