17. 微软面试题：用最快的步骤计算出 Fibonacci数列中的第n项

17. 微软面试题：用最快的方法计算出 Fibonacci数列中的第n项

这题可以参考Zyearn的博客（斐波那契数列的几种计算机解法）：

http://blog.****.net/zyearn/article/details/7878657

使用通项公式的方式，算法复杂度为o(1)，应该是最快的。

先看下Fibonacci数列的定义：

使用通项公式的概念，可以得到：

使用矩阵计算可以得到：

计算详细过程，请参考：http://blog.****.net/zyearn/article/details/7878657

实现过程如下：

#include<iostream>
#include<math.h>
using namespace std;

int fi(int n)
{
        if(n < 0) return -1;
        int res = 1.0/sqrt(5)*(pow((1.0+sqrt(5))/2, n) -pow((1.0-sqrt(5))/2, n));
        return res;     
}


int main()
{
        cout << "fi(5)= " << fi(5) << endl;
        return 0;
}

实现如下：

fi(5)=5

1楼ggcwj52014小时前

这更像是数学考试题了 记得以前刷题的时候是直接算的 因为那个涉及到大数计算 要用字符来处理