题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。
n≤39
示例1
输入
4
返回值
3
思路
使用矩阵快速幂。
斐波那契可以矩阵表示如下：
化简如下：
所以求就是求
的n-1次方，然后取矩阵左上角的数即可。
题解
class Solution {
public:
void Mul(int a[][2],int b[][2]){
int temp[2][2] = {0};
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
temp[i][j]+=a[i][k]*b[k][j];
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
a[i][j]=temp[i][j];
}
int Power(int base[][2], int exponent) {
int ans[2][2] = {{1,1},{1,1}};
while(exponent!=0){
if(exponent&1){
Mul(ans, base);
}
exponent >>= 1;
Mul(base, base);
}
return ans[0][0];
}
int Fibonacci(int n) {
if(n==0) return 0;
if(n==1) return 1;
int a[2][2] = {{1,1},{1,0}};
return Power(a, n-2);
}
};
