[已解决]类递归

萨西摩尔·槿花

Time Limit : 1000ms (C)   Memory Limit : 32768K (C)
Title:数字序列的定义如下：f（1）=1，f（2）=1，f（n）=（A*f（n-1）+B*f（n-2））mod 7。<br><br>给定A、B和n，您需要计算f（n）的值
输入:由多个测试用例组成。每个测试用例在单行上包含3个整数A、B和n（1<=A，B<=1000，1<=n<=100000000）。三个零表示输入结束，不处理此测试用例。
输出:对于每个测试用例，在单行上打印f（n）的值。
Sample Input
1 1 3
1 2 10
0 0 0
Sample Output
2
5

我的代码

1. 
   
2. #include <stdio.h>
   
3.        
   
4. int a,b;
   
5. int fix(int n);
   
6. int main()
   
7. {
   
8.         int n,s[666]={0},i=1;
   
9.         scanf("%d %d %d",&a,&b,&n);
   
10.         while((a+b+n)!=0)
    
11.         {
    
12.                 s[i]=fix(n);
    
13.                 scanf("%d %d %d",&a,&b,&n);
    
14.                 printf("%d\n",s[i]);
    
15.                 i++;
    
16.         }
    
17. 
    
18.         return 0;
    
19. }
    
20.        
    
21. int fix(int n)
    
22. {
    
23.         if(n==2)
    
24.                 return b;
    
25.         else if(n==1)
    
26.                 return a;
    
27.          
    
28.         int x = 1;
    
29.     int y = 1;
    
30.     int temp = 0;
    
31.     for (int i = 3; i <= n; i++)
    
32.         {
    
33.         temp = (a*y + b*x)%7;
    
34.         x = y;
    
35.         y = temp;
    
36.     }
    
37.     return temp;
    
38. 
    
39. }
    

复制代码

提示超时了
求指点

最佳答案

月排行榜 / 总排行榜

geekac

2023-3-15 08:16:25

这题的关键是考察mod  从这里入手 找一下规矩试试

跳转到最佳答案楼层

basketmn

1. #include<stdio.h>
   
2. 
   
3. int f(int a,int b,int n){
   
4.         if(n==1)return a;
   
5.         else if (n==2)return b;
   
6.         else
   
7.         return (a*f(a,b,n-2)+b*f(a,b,n-1))%7;
   
8. }
   
9. int main(){
   
10.         int a,b,n;
    
11.         while(scanf("%d%d%d",&a,&b,&n)==3&&a!=0&&b!=0&&n!=0){
    
12.         printf("%d\n",f(a,b,n));
    
13.         }       
    
14.         return 0;
    
15. }
    

复制代码

萨西摩尔·槿花

basketmn 发表于 2023-3-12 13:09

超内存了

basketmn

萨西摩尔·槿花 发表于 2023-3-12 14:07
超内存了

链接发过来

萨西摩尔·槿花

basketmn 发表于 2023-3-12 14:16
链接发过来

http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1004&ojid=0&cid=14387&hide=0

basketmn

萨西摩尔·槿花 发表于 2023-3-12 14:22
http://acm.hdu.edu.cn/webcontest/contest_showproblem.php?pid=1004&ojid=0&cid=14387&hide=0

你这不会是内网吧！
我打不开

jhq999

1. s[1]=1;s[2]=1;
   
2.     for(int i=3;i<=n;i+=1)
   
3.     {
   
4.         s[i]=(A*s[i-1]+B*s[i-2])%7;
   
5.         printf("%d ",s[i]);
   
6.         
   
7.     }

复制代码

萨西摩尔·槿花

正解：（来自CSDN）
思路：

因为循环的条件就是有2个数m和n

f[m-1] = f[n-1], f[m] = f[n]

这样就会开始循环了。

即f[n-1], f[n]与之前的[m-1],f[m]分别对应

而 0 <= f[n-1],f[n] < 7

所以f[n-1]f[n]连着的情况有7*7的情况。

只需每次求出一个f[n]，然后比较f[n-1]f[n]与前面数的情况即可。

1. 
   
2. #include<stdio.h>
   
3. 
   
4. int main()
   
5. {
   
6.      long int a,b,n,T,s[101];
   
7.      while(scanf("%ld%ld%ld",&a,&b,&n)&&(a!=0&&b!=0&&n!=0))
   
8.      {
   
9.         int i,j,T;
   
10.         s[0]=1;
    
11.         s[1]=1;
    
12.         for(i=2;i<101;i++)//第一个循环
    
13.                 {
    
14.             s[i]=(a*s[i-1]+b*s[i-2])%7;
    
15.             for(j=1;j<i-1;j++)//第二个循环
    
16.             {
    
17.                 if(s[j-1]==s[i-1]&&s[j]==s[i])
    
18.                                 {
    
19.                     T=i-j;
    
20.                     break;
    
21.                 }
    
22.             }
    
23.         }
    
24.         n = n%T;
    
25.         printf("%ld\n",s[n-1]);
    
26.      }
    
27.      return 0;
    
28. }

复制代码

geekac

这题的关键是考察mod  从这里入手 找一下规矩试试

geekac

basketmn 发表于 2023-3-12 13:09

n等于1或者2都是返回1呀