下面是一个矩阵快速幂求解斐波那契数列第n项对第m项取余的程序,但是总是运行出错,.
来源:学生作业帮 编辑:搜狗做题网作业帮 分类:综合作业 时间:2024/08/06 13:02:39
下面是一个矩阵快速幂求解斐波那契数列第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
![下面是一个矩阵快速幂求解斐波那契数列第n项对第m项取余的程序,但是总是运行出错,.](/uploads/image/z/15641317-37-7.jpg?t=%E4%B8%8B%E9%9D%A2%E6%98%AF%E4%B8%80%E4%B8%AA%E7%9F%A9%E9%98%B5%E5%BF%AB%E9%80%9F%E5%B9%82%E6%B1%82%E8%A7%A3%E6%96%90%E6%B3%A2%E9%82%A3%E5%A5%91%E6%95%B0%E5%88%97%E7%AC%ACn%E9%A1%B9%E5%AF%B9%E7%AC%ACm%E9%A1%B9%E5%8F%96%E4%BD%99%E7%9A%84%E7%A8%8B%E5%BA%8F%2C%E4%BD%86%E6%98%AF%E6%80%BB%E6%98%AF%E8%BF%90%E8%A1%8C%E5%87%BA%E9%94%99%2C.)
按照正常的逻辑是只要求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个数是?