Question

杭电acm 1005题 有没递归的方法，顺便把正确的方法也贴出来的吧

这是我的代码，超时的了，能解释一下么？解决的好的一定加分的，谢谢的了
#include<stdio.h>
int a,b;
int main()
{
int function(int z );
int n;
while (1)
{
scanf("%d%d%d",&a,&b,&n);
if (0==a && 0==b && 0==n)
break;
printf("%d\n",function(n));
}
return 0;
}
int function(int z)
{
if ( 1==z ||0 ==z || 2 == z)
return 1;
else return (a*function(z-1)+b*function(z-2))%7;
}

Answer 1

#include <iostream>
#include <cstring>
using namespace std;

int happen[7][7]; // 用来计算出现的位置

int main()
{
int A,B,n;
int f1,f2,fn;
while(cin >> A >> B >> n)
{
if(A==0 && B==0 && n==0) break;
memset(happen,0,sizeof(happen)); // 初始化
f1=1;f2=1; // 初始化
if(n==1 || n==2) cout << 1 << endl; // 特殊处理
else
{
for(int i=3;i<=n;i++)
{
if(happen[f1][f2]==0) // 如果f1和f2以前没出现过
{
happen[f1][f2]=i; // 记录第一次出现f1和f2的位置
fn = (A*f2 + B*f1) % 7; // 计算下一个数
//cout << fn << " ";
f1 = f2; // 退一个
f2 = fn; // 退一个
}
else // 如果f1和f2以前已经出现过
{
n=n-i; // 算一下目标与现在的距离
n%=(i-happen[f1][f2]); // 循环距离是 i - 之前记录的记录, 把n缩短到1个循环距离以内, 获得n的循环位置
n+=i; // 加上现在的i, 获得下一个和n具有相同循环位置的下标
fn = (A*f2 + B*f1) % 7; // 计算下一个
f1 = f2; // 退一个
f2 = fn; // 退一个
}
}
cout << fn << endl;
}
}
}

Answer 2

这题递归做是理论正确的。但是规模很大，你算一下他们的运算量就知道，必然会超时，你可以考虑不用递归，可以用递推。还有，你要是真心做acm,不建议在百度上来问。这里不专业。也没有acmer喜欢百度的这几个没价值的分数。

追问

递归和递推有什么区别的么？呵呵，你ACM的队员么？我刚刚接触这个的，不久的哈，是否可以加你的呀？

追答

递归会有许多重复计算。你想递归也可以。但要用记忆化，就是用一个数组来存下结果，每次计算的时候看看以前有没有算过，没算过接着算，算过了直接返回结果。