nyist 148 fibonacci数列的矩阵解法
用二分幂进行矩阵乘法运算。
#include <iostream>
using namespace std;
int f(int n)
{
if(n==0||n==1) return n;
int a2=1,a1=1,a0=0,f2=1,f1=0,f0=1,p2,p1,p0; n--;
if(n==1) return a2;
while(n)
{
if(n%2)
{
p2=f2*a2+f1*a1,p1=f2*a1+f1*a0,p0=f1*a1+f0*a0;
f2=p2%10000,f1=p1%10000,f0=p0%10000;
}
p2=a2*a2+a1*a1; p1=a2*a1+a1*a0; p0=a1*a1+a0*a0;
a2=p2%10000,a1=p1%10000,a0=p0%10000;
n/=2;
}
return f2;
}
int main(int argc, char *argv[])
{
int n;
while(cin>>n&&(n!=-1))
{
cout<<f(n)<<endl;
}
return 0;
}
- 上一篇：真正完美解决Win7乱码问题
- 下一篇：Oracle表空间常用操作
相关文章
图文推荐
- 文章
- 推荐
- 热门新闻