个人答案：
#include"iostream"
#include"stdio.h"
#include"string.h"
using namespace std;
typedef long long ll;
const int MAXN=; ll fib[MAXN];
ll Fibonacci(int n)
{
if(fib[n]!=-)
return fib[n];
return fib[n]=Fibonacci(n-)+Fibonacci(n-);
} int main()
{
int n;
memset(fib,-,sizeof(fib));
fib[]=;
fib[]=;
while(cin>>n)
{
cout<<Fibonacci(n)<<endl;
}
return ;
}
官方答案：
// 面试题10：斐波那契数列
// 题目：写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。 #include <cstdio> // ====================方法1：递归====================
long long Fibonacci_Solution1(unsigned int n)
{
if(n <= )
return ; if(n == )
return ; return Fibonacci_Solution1(n - ) + Fibonacci_Solution1(n - );
} // ====================方法2：循环====================
long long Fibonacci_Solution2(unsigned n)
{
int result[] = {, };
if(n < )
return result[n]; long long fibNMinusOne = ;
long long fibNMinusTwo = ;
long long fibN = ;
for(unsigned int i = ; i <= n; ++ i)
{
fibN = fibNMinusOne + fibNMinusTwo; fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
} return fibN;
} // ====================方法3：基于矩阵乘法====================
#include <cassert> struct Matrix2By2
{
Matrix2By2
(
long long m00 = ,
long long m01 = ,
long long m10 = ,
long long m11 =
)
:m_00(m00), m_01(m01), m_10(m10), m_11(m11)
{
} long long m_00;
long long m_01;
long long m_10;
long long m_11;
}; Matrix2By2 MatrixMultiply
(
const Matrix2By2& matrix1,
const Matrix2By2& matrix2
)
{
return Matrix2By2(
matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
} Matrix2By2 MatrixPower(unsigned int n)
{
assert(n > ); Matrix2By2 matrix;
if(n == )
{
matrix = Matrix2By2(, , , );
}
else if(n % == )
{
matrix = MatrixPower(n / );
matrix = MatrixMultiply(matrix, matrix);
}
else if(n % == )
{
matrix = MatrixPower((n - ) / );
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, Matrix2By2(, , , ));
} return matrix;
} long long Fibonacci_Solution3(unsigned int n)
{
int result[] = {, };
if(n < )
return result[n]; Matrix2By2 PowerNMinus2 = MatrixPower(n - );
return PowerNMinus2.m_00;
} // ====================测试代码====================
void Test(int n, int expected)
{
if(Fibonacci_Solution1(n) == expected)
printf("Test for %d in solution1 passed.\n", n);
else
printf("Test for %d in solution1 failed.\n", n); if(Fibonacci_Solution2(n) == expected)
printf("Test for %d in solution2 passed.\n", n);
else
printf("Test for %d in solution2 failed.\n", n); if(Fibonacci_Solution3(n) == expected)
printf("Test for %d in solution3 passed.\n", n);
else
printf("Test for %d in solution3 failed.\n", n);
} int main(int argc, char* argv[])
{
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, );
Test(, ); Test(, ); return ;
}