[已解决]类递归

萨西摩尔·槿花

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

我的代码

#include <stdio.h>
        
int a,b;
int fix(int n);
int main()
{
        int n,s[666]={0},i=1;
        scanf("%d %d %d",&a,&b,&n);
        while((a+b+n)!=0)
        {
                s[i]=fix(n);
                scanf("%d %d %d",&a,&b,&n);
                printf("%d\n",s[i]);
                i++;
        }

        return 0;
}
        
int fix(int n)
{
        if(n==2)
                return b;
        else if(n==1)
                return a;
         
        int x = 1;
    int y = 1;
    int temp = 0;
    for (int i = 3; i <= n; i++) 
        {
        temp = (a*y + b*x)%7;
        x = y;
        y = temp;
    }
    return temp;

}

提示超时了
求指点

最佳答案

月排行榜 / 总排行榜

geekac

2023-3-15 08:16:25

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

跳转到最佳答案楼层

basketmn

#include<stdio.h>

int f(int a,int b,int n){
        if(n==1)return a;
        else if (n==2)return b;
        else
        return (a*f(a,b,n-2)+b*f(a,b,n-1))%7;
}
int main(){
        int a,b,n;
        while(scanf("%d%d%d",&a,&b,&n)==3&&a!=0&&b!=0&&n!=0){
        printf("%d\n",f(a,b,n));
        }        
        return 0;
}

萨西摩尔·槿花

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

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

萨西摩尔·槿花

正解：（来自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]与前面数的情况即可。

#include<stdio.h>

int main()
{
     long int a,b,n,T,s[101];
     while(scanf("%ld%ld%ld",&a,&b,&n)&&(a!=0&&b!=0&&n!=0))
     {
        int i,j,T;
        s[0]=1;
        s[1]=1;
        for(i=2;i<101;i++)//第一个循环
                {
            s[i]=(a*s[i-1]+b*s[i-2])%7;
            for(j=1;j<i-1;j++)//第二个循环
            {
                if(s[j-1]==s[i-1]&&s[j]==s[i])
                                {
                    T=i-j;
                    break;
                }
            }
        }
        n = n%T;
        printf("%ld\n",s[n-1]);
     }
     return 0;
}

geekac

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

geekac

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

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