Question

杭电ACM1005题Runtime error

#include<iostream>
#include<vector>
using namespace std;
int getresult(int number1,int number2,int n)
{
if(n==1)
return 1;
else if(n==2)
return 1;
else
{
return (number1*getresult(number1,number2,n-1)+number2*getresult(number1,number2,n-2))%7;
}
}

int main()
{
int number1,number2,result,n;
vector<int> vec;
vector<int>::iterator iter;
while((cin>>number1>>number2>>n)&&((number1!=0)||(number2!=0)||(n!=0)))
{
result=getresult(number1,number2,n);
vec.push_back(result);
}
for(iter=vec.begin();iter!=vec.end();iter++)
{
cout<<*iter<<endl;
}
}
我想问为什么会溢出？有什么其他好的解决方法？

Answer 1

递归导致爆栈了。由于每次递归都需要保存当前信息，压入栈中，所以当递归次数过多时，栈内存就不够用了。你可以测一下，递归次数在几十次就会爆栈的。
这个题目是数学题。
首先，必然有f(n)∈{0,1,2,3,4,5,6}这个结论。递推式本质就是用两个0到6的数来确定一个值。这两个数，一共有49种组合。所以超过49次递推后，必然面临前面出现过的情形，这样导致递推循环了。
下面的程序用fn来找到第二次出现相邻的两个1时的循环节长度loop，之后的计算就简化了。
#include <stdio.h>
int fn(int A,int B);
int a[100];
int main() {
int A,B,loop;
int n;
while(scanf("%d%d%d",&A,&B,&n)!=EOF&&n!=0)
{
loop=fn(A,B);
n--;
n%=loop;
printf("%dn",a[n]);
}
return 0;
}
int fn(int A,int B) {
int i;
a[0]=a[1]=1;
for(i=2;i<52;i++) {
a[i] = (A*(a[i-1])+B*(a[i-2]))%7;
if(a[i]==1&&a[i-1]==1)
break;
}
return i-1;
}
很多人，直接loop=49就行了，每次不用求循环节。

追问

n--;？？
i
using namespace std;
int a[50];
int main()
{
int A,B,i,n;
a[1]=1;a[2]=1;
while(scanf("%d%d%d",&A,&B,&n)!=EOF &&A&&B&&n)
{
A%=7;B%=7;
for(i=3;i<49;i++)
{
a[i]=(A*a[i-1]+B*a[i-2])%7;
}
cout<<a[n%48]<<endl;
}
}

追答

抱歉，我的少了一条斜线……
改为printf("%d\n",a[n]);

因为这道题有bug，不会出现0，若果A，B均为7的倍数的话，则数列为1,1,0,0,0……上面的程序会出错的。所以该题测试数据的实际循环节没有49那么长……

追问

你的代码通过了，但是我还是不懂
n--;？？
i<52？？2到51不是有50个数吗？不应该是i<51才是49个数吗？
为什么不会出现0？
我后来给你的那个代码中，如果n是48，它最后求a[n%48]，但是a[0]并没有定义，但是提交居然没有报错，这是为什么……

追答

问题一：我的数组从0开始存的，a[0]存了f(1)所以后来需要n--。
问题二：一共49种二元数对，所以是取前50个二元数对才必然会出现重复。i从2到51刚好检查了50个数对。
问题三：不会出现0是题目测试数据的漏洞吧。其实，当A，B两个都不和7互质时，数列不是纯周期数列。这个不是题目给出的条件，只是侥幸没有这种数据罢了。
用程序调试一下数据
7 14 49
7 14 50
7 14 51
7 14 52
7 14 53
就明白了。
问题四：C++中的数组有默认值。全局或static数组，默认值为0。局部数组默认值随机的。这个最好还是赋初值，养成良好习惯，利用编译器的性质难免有时候会搞错。

追问

问题一，你不是有return i-1了吗？
问题二，如果你想要得到重复，但你得到重复的判断是判断 if(a[i]==1&&a[i-1]==1) 你不应该测试到51个数据吗？
问题四，我知道有默认值0，但问题是得到的0是n为48的时候f(n)正确的值吗？

追答

return i-1只是计算的循环节长度，因为i从2开始的。这个跟存储没关系。
50组数据中必然有两组相同的，所以只需要50组。
最后一个，没法回答，答案在我这里是不对的。我觉得这个程序不能AC。除非测试数据中没有mod 48=0的。
另附我的运行结果：
7 7 48
0
7 9 48
0
17 9 48
0
17 29 48
0
17 2239 48
0

Answer 2

递归太深了，正解是矩阵乘法。

追问

能给一下代码不？或是讲一下原理……

追答

这个题目网上有解题报告的。你搜索一下。这儿发不了代码

Answer 3

你没有resize啊 vec.resize(大小)

追问

为什么要resize()?

追答

就是要申请一个大小的空间嘛，就跟数组一样，
vec.push_back(result);这一直存数据，你没有申请那么大的空间，怎么存呢？

追问

我觉得是递归时存放在栈里面的临时数据太多了导致了栈溢出，而不是vector容器的溢出，vector可以存放大量数据，而且可以自动调节容量，况且在提交后它是不会去测试那么多的数据的，但是它可以给一个很大的n……

追答

那就不晓得了，递归那应该没问题吧