求大神关于C++斐波那契数列整除问题

问题描述　　已知四个数：a，b，c，d，判断在第s个Fibonacci数到第t个Fibonacci数之间哪些数既不是a也不是b也不是c也不是d的倍数。输入格式　　第一行两个数，s，t，表示要判断第s个Fibonacci数到第t个Fibonacci数之间（包含第s个和第t个）的Fibonacci数。　　第二行四个数，a，b，c，d，意义如题目描述。输出格式　　一行若干个数，A1,A2,A3...An，从小到大排列，表示第Ai个Fibonacci数既不是a也不是b也不是c也不是d的倍数。　　每两个数之间用空格隔开。样例输入1 52 3 5 7样例输出1 2数据规模和约定　　1<=s<=t<=10000, 1<=a,b,c,d<=10000
这个数列最大要到一万项，如果用long double定义会有如图这种情况怎么办啊？

举报该问题

推荐答案 2013-10-25

用同余的方法:利用一个二维数组f[10001][4]，x[4]存放a,b,c,d四个数,
其中f[i ][4]分别表示第i个非波那切数除以x[j]的余数…j=1或2或3或4，
则现在处理f[i][j]，其实就是处理余数，再利用非波数的性质，
有递推公式f[i][j]=(f[i-1][j]+f[i-2][j])%x[j],因此f[i][j]的最大值都不会超过a、b、c、d这四个数的最大值…
则f[i][j]=0表示能整除x[j],那么f[i][j]全部不等于0则可..

温馨提示：答案为网友推荐，仅供参考

当前网址：http://99.wendadaohang.com/zd/XWtOzBBtXB7vjjeetB.html

其他回答

第1个回答 2013-10-25

你这个……没理解题意啊

先说一句，double，你long double还是long几个double，都是没办法用取余数运算的，因为double是浮点数，你甚至可以理解为是去除了整数的实数，不信您在纸上算出1.5 % 2 的结果告诉我是几？没老师教过吧。你或许会辩驳说，我double里面存的是整数啊，不要欺负计算机小姐……她不笨

t小于等于10000对吧？也就是说最大的数是第t个fibonacci竖列，就是第10000个fibonacci数，你知道是多少嘛。fibonacci竖列的前项和后项数的比是黄金分割0.618，相反后项跟前项比就是1.618，也就是大约一个1.618为公比的等比数列，等比数列会算吧，就算是第5000个fibonacci数，这个数字也达到了至少1后面跟1000个零的数字了，不信可以用纸写一写……看看最大的数是不是你理解的10000。

这道题吧，如果是说只是求判断第i个fibonacci数是否能整除abcd的话，似乎还有可能用一些手段，例如fibonacci的一些定理，不过这个题不仅要求如此，还要求输出第i个fibonacci数，这似乎就必须得硬算了。（个人理解是这样，如果硬算会超时，一方面当然可能是你写的算法有问题，另一方面就可能是这道题真的没办法用硬算，那具体有什么巧法，我还真不知道）

至于到底怎么去弄一个超大的整数（当然你不会认为什么long long long long int能存储1后面跟1000个0的数吧），这种算法还是很多的，可以百度一下“c++ 大整数实现”，去看看别人怎么算法的，我就不再写一个了

第2个回答 2013-10-25

对double不能取余数，你只能把多个int拼起来，然后自己进行数学处理。
如果你只输入15，没必要搞那么大的数组追问

最大的数据是10000啊。。我就是不知道这个取余数该怎么办啊。能讲详细点吗？

第3个回答 2013-10-25

第十行定义改成
long long double q[100000]追问

这样改根本不行啊。编译还是如上图这样。

追答

你数据最大10000，long long double q[10001]就可以了

相似回答

求大神关于C++斐波那契数列整除问题答：整除 x[j],那么f[i][j]全部不等于0则可..

怎么用c++求斐波那契数列的前20项答：在c语言中，以vc为例利用数组求斐波那契数列的前20项的具体步骤如下：1、首先，打开vc；2、点击文件、新建；3、选择win32 console application 并在右侧输入工程的名字和地址，确定；4、选择一个空的工程，完成；5、再次点击文件、新建，6、选择c++ source file 并输入文件名字，确定；7、输入如图所示...

斐波那契数列解题技巧答：第一种解法：递归法。利用C++求解斐波那契数列第N项数字是什么?我们可以用C++算法归法来进行表示,我们知道,斐波那契数列的每一项数字都等于前面两项数字之和,那么用计算机函数来表示，若fun为求斐波那契数列的第N项的函数,那么fun(N)=fun(N-1)+fun(N-2)。第二种解法(记忆化递归/动态规划):第一种...

斐波那契数列c++编程答：点击源文件→添加→新建项→。3、在名称位置，输入源文件名（特别注意：我们编写的是C文件，故后缀改为.c）。4、接下来就是编写程序了，如，求斐波那契数列的前40项，具体代码如下。5、在运行界面的，结果演示如下图（前40项）。斐波那契数列的应用：如，跳台阶问题与斐波那契数列很相像。

用C++求fibonacci数答：斐波那契数列？include<iostream.h> void fibonacci(int); //声明斐波那契函数 void main(){ int a;cout<<"请输入要求前几项："; //输入条件 cin>>a;fibonacci(a); //调用函数 } void fibonacci(int a) //定义函数 { int fab1=1,fab2=1,fabn,m,n;m=a;cout<<fab1<<"...

斐波那契数列c++代码是什么?答：$one;one = $res;} return $res;} 基本循环算法 include<bits/stdc++.h> using namespace std;int main(){ int a=0,b=1,c=1,n;cin>>n;//输入n for(int i=1;i<=n;i++){ a=b;b=c;c=a+b;} cout<<c;//输出最终结果 return 0;} 以上内容参考：百度百科-斐波那契数列 ...

C++编程 斐波那契数列……求大神答：int main(int argc,char *argv[]){ int N,a,b,i;printf("Enter N(int N>0)...\nN=");if(scanf("%d",&N)!=1 && N<1){ printf("Input error, exit...\n");return 0;} for(a=b=1,i=0;i<N;i++){ printf("%d ",a);b+=a,a=b-a;} printf("\n");return 0;...

算法设计(c++):计算斐波那契额数列模1000000007答：在做编程题目的时候经常会遇到“斐波那契数列”相关的题目，尤其在做OJ中。下面说一些方法：(一)递归递归是最慢的会发生重复计算，时间复杂度成指数级。long long fac(int n){if(n==1) return 1;else if(n==2) 　return 2;else 　return fac(n-1)+fac(n-2);} (二)循环利用临时...

C++用递归函数求斐波那契数列的第n项.调用函数内部不能用数组吗?为什么...答：a[1]=1;for(i=2;i<=k;i++){ a[i]=a[i-1]+a[i-2];h=a[i];} cout<<h<<endl;} 其他地不改……1.i<=k;否则当输入为2时，想得到a[2]时，会不执行，直接跳过。2.h是sy函数中的全局变量，作用域是该函数，故h=a[i];然后在for{}外边输出可以正确得到值 3.如果想得到从...