杭電ACM刷題（2）：1005，Number Sequence

Problem Description

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

Input

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

Output

For each test case, print the value of f(n) on a single line.

Sample Input

1 1 3

1 2 10

0 0 0

Sample Output

2

5

上面是題目的簡介。

程式思路：

f(n)是一個遞推式，A、B為兩個輸入的參數，n表示疊代次數。以平常接數學題目時的思維來看，很簡單，直接套公式，疊代n次肯定可以得到結果，下面是c語言實作代碼：

#include "stdio.h"

#pragma warning(disable:4996)

int main()
{
    int a, b;
    long n;
    long i;
    int f[];

    f[] = ;
    f[] = ;

    while (scanf("%d %d %d", &a, &b, &n))
    {
        if (a <  || b >  || n <  || n > )
            return -;

        for (i = ;i < n;i++)
        {
            f[i] = a * f[i - ] + b * f[i - ];
            f[i] = f[i] % ;
        }

        printf("%d\n", f[n-]);
    }

    return ;
}
           

然而，考慮到n的次數很大時，疊代次數也增加到相當大，其運算很明顯會占用大量的時間。是以需要考慮響應的方法減小計算量，加快程式運作速度。

我們可以觀察到公式所有的值都是經過

mod7

運算的，通過對7取餘，我們可以知道遞推結果的數列中每個值的大小都是

0~6

。每位有7種可能情況，遞推公式中有兩個數列的值輸入，是以有

7*7=49

種可能的組合。在所有的組合都出現之後，下一個情況必定是前面出現過的組合中的某一種，一次類推，重複出現，由此可以求到循環的周期。

利用循環周期，就可以很輕松地計算得到第n個對應哪一種情況了。

廢話不多說，直接上代碼吧。

#include "stdio.h"

#pragma warning(disable:4996)

int main()
{
    int a, b, n;
    int f[] = { ,, };
    int pos;

    while (scanf("%d %d %d", &a, &b, &n) != EOF)
    {       
        if (a <  || b >  || n <  || n > )
            return -;

        for (int i = ;i < ;i++)
        {
            f[i] = (a * f[i - ] + b * f[i - ]) % ;

            //printf("%d ", f[i]);

            if (i > )
            {
                if (f[i - ] == f[] && f[i] == f[])
                {
                    pos = i - ;
                    break;
                }
            }
        }
        //printf("\n");


        if (n > )
            printf("%d\n", f[(n-) % pos+]);
        else
            printf("1\n");

    }

    return ;
}
           

補充：

1. 為計算友善，從數組下标為1的元素對應數列第一個數，舍棄下标為0的那個元素；
2. 關于循環，網上很多程式都是檢測到前後兩個分别為1、1的情況時就認為開始下一輪循環了；然而這種方法是錯誤的，因為如果取特例a=7、b=7時，輸出序列為：1、1、0、0、0。。。。後面全部是0，這樣程式會持續運作下去，因為不可能再檢測到1、1了；是以檢測循環時從第3個和第4個開始，檢測是否重複：

if (f[i - ] == f[] && f[i] == f[])
{
    pos = i - ;
    break;
}
           

運作結果：