hoj1005题目乍一看比较简单很容易就联想到使用递归来求解(第一次我就是犯了这个错误)，可是看了给出的输入条件1<=n<=100000000，这样用递归则很深。递归实际上是每次计算了都会压入堆栈中，而系统默认分配的堆栈式1M这样递归下去，数据太大就很容易溢出。下面先给出我用递归的错误代码吧。尽管在VC上跑不会提示堆栈溢出，但提交会提示，STACK OVERFLOW.
/*********用递归做是失败的，因为递归太深造成堆栈溢出********/
#include
long int fun(long int n,int A,int B)
{
long int r;
if(n == 1)
r = 1;溢出
else if (n == 2)
r =1;
else{
r = (A*fun(n-1,A,B) + B*fun(n-2,A,B))%7;
}
return r;
}
int main(){
int A,B;
long int n,result;
while(scanf("%d %d %ld",&A,&B,&n) !=EOF || A != 0 || B != 0 || n != 0 ){
result = fun(n,A,B);
printf("%ld\n",result);
}
return 0;
}
不能用递归，这个题目用迭代也不好实现，因为每次都要mod7，但想到mod7只会出现7个不同的余数结果，而这个题目
f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.每一个大于3的值都会由两个余数值来确定，所以一共有7*7种可能结果(理解很重要)，而且是循环。那我们把这49种可能结果全部求出来然后和49求余，然后在这49个数种比对就能计算每一个的结果了。下面给出AC的代码
#include
int * fun(int A,int B)
{
int i;
int a[49];
a[0] = a[1] = 1;
for(i=2; i < 49; i++){
a[i] = (A*a[i-1] + B*a[i-2])%7;
}
return a;
}
int main(){
int * a = new int[51];
int A,B,n;
while(scanf("%d %d %d",&A,&B,&n) != EOF && ((A!=0) || (B!=0) || (n!=0))){
a = fun(A,B);
n = (n-1)%49;
printf("%d\n",a[n]);
}
delete []a;
return 0;
} 此题总结，当递归很小时，出于模块化考虑可以使用函数递归来求解。但是对于递归太深的问题，就转化为循环迭代来处理，如果循环迭代都不能很好的解决，就考虑使用其他的方案。