美文网首页
航电oj 1005

航电oj 1005

作者: 欢城深喟 | 来源:发表于2019-02-01 15:53 被阅读0次
    image

    这道题初看可以直接递归解决,但是 n 的取值过大时会发生栈溢出,无法解决这一问题。仔细思考之后发现,输入A、B、n之后,A、B的值就确定了,f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7的值只取决于 f(n - 1) 和 f(n - 2) 的值。

    假如我们知道了A、B的值,那么 f(3) 的值就可以由递推式得出,f(4) 的值也可由 f(2) 和 f(3) 得出,就像多米诺骨牌一样,后面的所有都可以确定了。由此可知,我们知道前面 f(n - 1) 和 f(n - 2) 的值,就可以得出 f(n) 的值了。

    f(n - 1) 和 f(n - 2) 的取值范围均为 0~6 共 7 种情况,两个的组合共 7×7=49 种情况, 也就是 50 次以后,一定会有重复的情况。比如 50 次里出现[0][0]两次,我们就可以断定 f(n) 的值是循环出现的,因为前面两个数一定可以确定第三个数,后面的数也都随之确定,所以再次出现相同的两个数时,下一个数也一定和上一次相等。(例如 f(3)=3,f(4)=4,而确定的 f(5)=5,当 f(35)=3,f(36)=4 的时候,f(37)一定等于5,循环的周期就是 35-3=32)。但是值得注意的是,循环的周期不一定是 49,可能不到 49 就开始循环了,因此我们还是需要找到循环周期是多少。

    还有一点,f(1) 和 f(2) 是人为给出的,可能不在循环之内,因此我选择从 f(3) 开始算循环周期。

    所以代码如下:

    #include<stdio.h>
    
    int main(){
        long a,b,n;
        while(scanf("%ld%ld%ld",&a,&b,&n) != EOF){
            if(a==0 && b==0 && n==0) return 0;
    
            int f[53];
            f[1]=1,f[2]=1;
            int t; //循环周期
    
            for(int i=3;i<53;i++){ //计算f[1]~f[52]的值
                f[i] = (a*f[i-1] + b*f[i-2]) % 7;
            }
    
            for(int j=5;j<53;j++){ //找循环周期t
                if(f[j]==f[3] && f[j+1]==f[4]){
                    t = j-3; //从第三个开始找,要减3得到周期
                    break;
                }
            }
    
            int ans = f[(n-3)%t+3]; //先减3算出在循环周期里的次序,再加3得到对应数组下标次序
            printf("%d\n",ans);
        }
        return 0;
    }
    

    相关文章

      网友评论

          本文标题:航电oj 1005

          本文链接:https://www.haomeiwen.com/subject/iusdsqtx.html