我在做acm的是有这样个题
给定f1=1,f2=1,f(n)=a*f(n-1)+b*f(n-2),要求输入a,b,n遇到0 0 0是结束并输出结果1<=a,b<=1000;1<=n<=100,000,000
比如输入
1 1 3
1 2 10
0 0 0
则输出
2
5
要求运行时间是1000ms但是我的程序是1015ms
大家帮帮忙看看能不能帮我减少点运行时间啊
或者帮帮忙写个简单点的程序啊
我感觉我写的太长了

#include <stdio.h>
#include <malloc.h>
int cal(int a,int b,long n);/*计算f(n)的值*/
main(){
/*初始化数值，建立链表*/
struct result{
int result;
struct result *next;
};
int a=1;
int b=1;
int c=0;
long n=0;
int i=0;
struct result *p1,*p2,*p;
p=p1=p2=(struct result*)malloc(sizeof(struct result));
scanf("%d%d%ld",&a,&b,&n);
if(a<1||a>1000||b<1||b>1000||n<1||n>100000000)
exit(0);
if(a==0&&b==0&&n==0)
exit(0);
else
p1->result=cal(a,b,n);
/*用链表存放每行数据得出的结果*/
while(a!=0||b!=0||n!=0){
c++;
if(c==1) p=p1;
else p2->next=p1;
p2=p1;
p1=(struct result*)malloc(sizeof(struct result));
scanf("%d%d%ld",&a,&b,&n);
if(a<1||a>1000||b<1||b>1000||n<1||n>100000000)
exit(0);
p1->result=cal(a,b,n);
}
/*输出链表*/
for(i=0;i<c;i++){
printf("%d\n",p->result);
p=p->next;
}
}
/*计算f(n)的值*/
int cal(int a,int b,long n){
int f;
if(n==1)
f=1;
if(n==2)
f=1;
if(n>=3)
f=(a*cal(a,b,n-1)+b*cal(a,b,n-2))%7;
return f;
}

请教:)你的题目是不是错了?
是不是应该这样啊
f1=1,f2=1,f(n)=(a*f(n-1)+b*f(n-2))%7,输入整数a,b,n,求f(n)!

如果是这样的话,就把代码发上来.

这个题目一定要计算周期的,否则就是超时

1<=a,b<=1000;1<=n<=100,000,000

比如输入
1 1 3
1 2 10
0 0 0
则输出
2
5
这个什么意思 顺便顶下

想问下楼主 你的时间耗费是什么算出来的？1015ms

我在做acm的时候编译器告诉我的啊
那个确实是f(n)=(a*f(n-1)+b*f(n-2))%7
笔误啊不好意思

由于考虑到周期较小，所以用动态数组，便于引用！

经过测试一般数据运行耗时基本为0毫秒
代码红色部分考虑的是周期段不一定从第一位开始，故时间复杂度较高
如果认定是从第一位开始，那么红色代码可变为：
if(result[i]==1&&result[i-1]==1)
return *min=0,*max=i-1;
这样显然速度会快一些！但没有理论依据，故选前者！
[CODE]
#include "stdio.h"
#include "alloc.h"
#include "time.h"
#define MAXSIZE 20
#define INCREASESIZE 5
int a,b,*result;
long n;

int Function(int *min,int *max)
{
int i,j, size=MAXSIZE;

result=(int *)malloc(sizeof(int)*size);
if(result==NULL)
exit(-1);
result[0]=result[1]=1;
for(i=2;;i++)
{
if(i>=size)
{
result=(int *)realloc(result,sizeof(int)*(size+INCREASESIZE));
if(result==NULL)
exit(-1);
size+=INCREASESIZE;
}

result[i]=( result[i-1]*a+result[i-2]*b )%7;
for(j=i-1;j>0;j--)
if(result[j]==result[i]&&result[j-1]==result[i-1])
return *min=j-1,*max=i-1;
}
}

int main()
{
int min,max;

while(1)
{
scanf("%d%d%ld",&a,&b,&n);
if(a<1 || a>1000 || b<1 || b>1000 || n<1 || n>100000000)
exit(-1);

Function(&min,&max);
if( n<min )
printf("%d\n\n",result[n-1]);
else
printf("%d\n\n" ,result[(n-1)%(max-min)+min]);
}
free(result);
return 0;
}


[/CODE]