加载中…矩阵乘法 求斐波那契数列
(2011-08-28 10:42:00)
标签：
矩阵乘法斐波那契数列it |
先简单介绍一下矩阵乘法求斐波那契数列的原理
int a[2][2];
mul2(result,
base);
f(n) 是第n项的值。
f(1)= 1; f(2) =1;
f(n)= f(n-1) + （n-2)
下面的介绍是我从网上查到了，收益匪浅。
分两步推导：
http://s1/middle/6ea2c6a2g778d96789fd0&690 求斐波那契数列" TITLE="矩阵乘法 求斐波那契数列" />
http://s11/middle/6ea2c6a2gab87e12b75da&690求斐波那契数列" TITLE="矩阵乘法 求斐波那契数列" />
问题的求解就变成http://s1/middle/6ea2c6a2gab87e1687010&690 求斐波那契数列" TITLE="矩阵乘法 求斐波那契数列" />的解决，而幂的求可用二分法来求。
http://s11/middle/6ea2c6a2gab87e12b75da&690
二分法可用递归和非递归来求：
下面是代码：
定义矩阵
struct matrix
//定义2*2的矩阵
{
};
void mul(matrix& x,matrix& y)
// 矩阵乘法 x = x*y
{
matrix ans;
ans.a[0][0]=x.a[0][0]*y.a[0][0]+x.a[0][1]*y.a[1][0];
ans.a[0][1]=x.a[0][0]*y.a[0][1]+x.a[0][1]*y.a[1][1];
ans.a[1][0]=x.a[1][0]*y.a[0][0]+x.a[1][1]*y.a[1][0];
ans.a[1][1]=x.a[1][0]*y.a[0][1]+x.a[1][1]*y.a[1][1];
x = ans;
}
//下面这个函数是我从网上查到的
matrix power(matrix x,long e)
{
matrix ans,tmp;
if(e==0)
//指数为0的时候,返回单位矩阵
{
ans.a[0][0]=1;
ans.a[0][1]=0;
ans.a[1][0]=0;
ans.a[1][1]=1;
return ans;
}
if( e==1 )
return x;
tmp=power(x,e>>1);
//X的e/2次方
ans=mul(tmp,tmp);
if( e&1 )
//如果e为奇数,还要再乘以X
ans=mul(ans,x);
return ans;
}
非递归代码：
matrix result = {{1,0,0,1}};
matrix base ={{1,1,1,0}};
if(n&1) result = base;
n>>=1;
while(n)
{
mul2(base, base);
if(n&1)
{
}
n>>=1;
}
<<result.a[0][1]就是第 n项 的值。
喜欢
0
赠金笔
前一篇：一个逆序数引发的“血案”（1）
后一篇：2011年08月28日