共有回帖数 0 个
-
k 阶斐波那契数列：
┏1，n=k
A[n]＝┃
┗A[n-k] + A[n-k+1] + A[n-k+2] + …… + A[n-1]，nk
#include iostream
#define K 5 //K 阶
#define N 6 //第 N 项
template typename T
struct Fib
{
void intial()
{
memset(num, 0, sizeof(T)*K*K);
num[K-1][0]=1;
for (int i=K-1; i--0; )
num[i+1]=num[0]=1;
}
T num[K][K];
};
template typename T
FibT Mul(const FibT &a, const FibT &b)
{
int i, j, k;
FibT s;
for (i=K; i--0; )
for (j=K; j--0; )
for (s.num[j]=0, k=K; k--0; )
if (b.num[k][j])
s.num[j]+=a.num[k];
return s;
}
template typename T
FibT Sqr(const FibT &a)
{
int i, j, k;
FibT s;
for (i=K; i--0; )
for (j=K; j--0; )
for (s.num[j]=0, k=K; k--0; )
s.num[j]+=a.num[k]*a.num[k][j];
return s;
}
template typename T
T KRankFib(int n)
{
if (n=K)
return 1;
int k=1;
FibT r, s;
r.intial();
s.intial();
n-=K;
while (k=n)
k=1;
k=1;
while (k=1)
{
s=Sqr(s);
if (k & n)
s=Mul(s, r);
}
k=0;
for (int i=K; i--0; )
k+=s.num[0];
return k;
}
int main()
{
std::cout KRankFibint(N);
return 0;
}
n 较小时，该方法效率很低 n 很大时，该方法的优势就显示出来了 KRankFib()是k^3*log2(n)级的
楼主 2016-01-15 18:25 回复
Copyright © 2010~2015 直线网 版权所有,All Rights Reserved.沪ICP备10039589号
意见反馈 |
关于直线 |
版权声明 |
会员须知
