下面是一个矩阵快速幂求解斐波那契数列第n项对第m项取余的程序,但是总是运行出错,.
来源:学生作业帮 编辑:搜搜做题作业网作业帮 分类:综合作业 时间:2024/07/31 13:24:46
下面是一个矩阵快速幂求解斐波那契数列第n项对第m项取余的程序,但是总是运行出错,.
#include
int a[2][2]={1,1,1,0},b[2][2]={1,1,1,0};//使用两个二维数组表示快速幂算法要用到的矩阵
int main()
{
int n,m,i,j,t,u;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(m==-1 && n==-1)//当输入的m.n值为-1时结束整个算法
return 0;
/*以下是对于第n项斐波那契数的计算*/
if(n==0)
a[0][0]=0;
else if(n==1 || n==2)
a[0][0]=1;
else
{
for(i=3;i
#include
int a[2][2]={1,1,1,0},b[2][2]={1,1,1,0};//使用两个二维数组表示快速幂算法要用到的矩阵
int main()
{
int n,m,i,j,t,u;
while(scanf("%d %d",&n,&m)!=EOF)
{
if(m==-1 && n==-1)//当输入的m.n值为-1时结束整个算法
return 0;
/*以下是对于第n项斐波那契数的计算*/
if(n==0)
a[0][0]=0;
else if(n==1 || n==2)
a[0][0]=1;
else
{
for(i=3;i
按照正常的逻辑是只要求a[2][2]={1,1,1,0}这个矩阵的n次方就可以得到斐波那契数列的第n项(即a[0][1])的值.但是你忽略了一点,就是你在求a[0][1],a[1][0],a[1][1]的值的时候你的a[0][0]的值其实已经改变了,导致你求得的a[0][1]的值不正确,继而影响到a[1][0]和a[1][1]的值.因此,我们在遍历这四个值的时候是不能改变其中任何一个的,只有改完之后才能去改变它的值.所以我们可以用几个变量先将求得的新矩阵各值存起来,如下:#include<stdio.h>int a[2][2]={1,1,1,0},b[2][2]={1,1,1,0};//使用两个二维数组表示快速幂算法要用到的矩阵int main(){ int n,m,i,j,t,u; int a1,a2,a3,a4; while(scanf("%d %d",&n,&m)!=EOF) { if(m==-1 && n==-1)//当输入的m.n值为-1时结束整个算法 return 0; /*以下是对于第n项斐波那契数的计算*/ if(n==0) a[0][0]=0; else if(n==1 || n==2) a[0][0]=1; else { for(i=3;i<=n;i++) { a1=a[0][0]*b[0][0]+a[0][1]*b[1][0]; a2=a[0][0]*b[0][1]+a[0][1]*b[1][1]; a3=a[1][0]*b[0][0]+a[1][1]*b[1][0]; a4=a[1][0]*b[0][1]+a[1][1]*b[1][1]; a[0][0]=a1; a[0][1]=a2; a[1][0]=a3; a[1][1]=a4; } } t=a[0][0]; a[0][0]=1;//重置矩阵 a[0][1]=1; a[1][0]=1; a[1][1]=0; if(m==0) a[0][0]=0; else if(m==1 || m==2) a[0][0]=1; else { for(j=3;j<=m;j++) { a1=a[0][0]*b[0][0]+a[0][1]*b[1][0]; a2=a[0][0]*b[0][1]+a[0][1]*b[1][1]; a3=a[1][0]*b[0][0]+a[1][1]*b[1][0]; a4=a[1][0]*b[0][1]+a[1][1]*b[1][1]; a[0][0]=a1; a[0][1]=a2; a[1][0]=a3; a[1][1]=a4; } } u=a[0][0]; a[0][0]=1;//重置矩阵 a[0][1]=1; a[1][0]=1; a[1][1]=0; t=t%u; printf("%d\n",t); } return 0;} 还有一点,就是你的矩阵相乘后两项写错了,自己对比一下改过来吧. 这样就能得到你想要的结果了.
不理解矩阵快速幂如何用于求斐波那契数列第n项%m的余数,
VB:斐波那契数列第一项是1,第二项是1,用递归算法编写一个程序,求数列前N项的和
求斐波那契数列的第N项VFP程序
C语言程序设计,编写一个函数实现求解斐波那契数列的第n项以及前n项之和,包括(递归和非递归版本).并编写主函数进行测试.
二、 编写一个递归函数,计算并返回斐波那契数列中第n项的值,斐波那契数列定义如下:
c语言中,.编写程序求斐波那契数列的第n项和前n项之和.大家看好是【第】n项的值和前n项的合= =.
C程,输出m到n之间的斐波那契数列,要求调用函数fib(n)求第n项
输入斐波那契数列的第N项的位置PASCAL
pascal高精度的斐波那契数列的第n项?
用递归法计算斐波那契数列的第n项
求Fibonacci数列的第n项的VB程序
斐波那契数列的第11个数是?