试利用循环队列编写求k阶斐波那契序列中第 n+1项fn的算法。

利用fi+1 = 2fi - fi-k ,队列的容量为k+1
Void fb(int k;int;max)
{ for(i=0;i<=k-2;i++) {f[i]=0; cqelem[i]=0;}
cqelem[k-1]= cqelem[k]= 1;
cqrear=k; n=k+1; f[k-1]=f[k]=1;
while(cqelem[cq rear]<max)
{j= (cq rear+1) % (k+1);
f[n]= cqelem[cq rear]2- cqelem[j];
cqelem[j]=f[n]; cqrear=j; n++;
}
if(cqelem[cqrear]>max) n=n-2; else n=n-1;
if (max==1) {n=k;f[k]=1;}
if (max==0) n=k-2;
}

通项公式为：(1/√5){[(1+√5)/2]^n - [(1-√5)/2]^n}√5表示根号5 #include<stdioh>

void Fdt(long F1,long F2,int N);//递推

void Fdg(long F1,long F2,int N);//递归

main()

{

int n=20;

long f1,f2;

f1=f2=1;

Fdt(f1,f2,n);

printf("\n\n");

Fdg(f1,f2,n);

}

void Fdt(long F1,long F2,int N)//递推

{

for(int i=1;i<=N;i++)

{

printf("%12ld %12ld",F1,F2);

if(i%2==0)

printf("\n");

F1=F1+F2;

F2=F1+F2;

}

}

void Fdg(long F1,long F2,int N)//递归

{

if(N>=1)

{

printf("%12ld %12ld",F1,F2);

if(N%2==0)

printf("\n");

Fdg(F1+F2,F1+F2+F2,N-1);

}

}

扩展资料：

从第二项开始，每个偶数项的平方都比前后两项之积多1，每个奇数项的平方都比前后两项之积少1。如：第二项 1 的平方比它的前一项 1 和它的后一项 2 的积 2 少 1，第三项 2 的平方比它的前一项 1 和它的后一项 3 的积 3 多 1。

（注：奇数项和偶数项是指项数的奇偶，而并不是指数列的数字本身的奇偶，比如从数列第二项 1 开始数，第 4 项 5 是奇数，但它是偶数项，如果认为 5 是奇数项，那就误解题意，怎么都说不通）

参考资料来源：百度百科-斐波那契数列

在第一张图中，画波浪线的部分实际上是斐波那契数列的解法之一，使用递归算法实现斐波那契数列可以得到相应的时间复杂度的公式。
我们将斐波那契数列的递归算法的时间复杂度记作T(n)。在斐波那契数列的递归算法中，每次递归都需要进行两次递归调用，而且每次递归需要对前两项进行加法运算，因此，在计算第 n 个斐波那契数列值时，共需要递归调用 2n − 1 次（其中n为第n个斐波那契数），每次递归调用需要进行一次加法运算，所以时间复杂度为O(2^n)。
需要注意的是，由于斐波那契数列递归算法的指数级时间复杂度，算出非常大的值会需要很长的时间，甚至会引起栈溢出。因此，在实际应用中，需要使用其他的算法来实现斐波那契数列的计算。

---