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[100];
f[0] = 1;
f[1] = 1;
while (scanf("%d %d %d", &a, &b, &n))
{
if (a < 1 || b > 1000 || n < 1 || n > 100000000)
return -1;
for (i = 2;i < n;i++)
{
f[i] = a * f[i - 1] + b * f[i - 2];
f[i] = f[i] % 7;
}
printf("%d\n", f[n-1]);
}
return 0;
}
然而,考慮到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[54] = { 0,1,1 };
int pos;
while (scanf("%d %d %d", &a, &b, &n) != EOF)
{
if (a < 1 || b > 1000 || n < 1 || n > 100000000)
return -1;
for (int i = 3;i < 54;i++)
{
f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
//printf("%d ", f[i]);
if (i > 5)
{
if (f[i - 1] == f[3] && f[i] == f[4])
{
pos = i - 4;
break;
}
}
}
//printf("\n");
if (n > 2)
printf("%d\n", f[(n-3) % pos+3]);
else
printf("1\n");
}
return 0;
}
補充:
為計算友善,從數組下标為1的元素對應數列第一個數,舍棄下标為0的那個元素;
關于循環,網上很多程式都是檢測到前後兩個分别為1、1的情況時就認為開始下一輪循環了;然而這種方法是錯誤的,因為如果取特例a=7、b=7時,輸出序列為:1、1、0、0、0。。。。後面全部是0,這樣程式會持續運作下去,因為不可能再檢測到1、1了;是以檢測循環時從第3個和第4個開始,檢測是否重複:
if (f[i - 1] == f[3] && f[i] == f[4])
{
pos = i - 4;
break;
}
運作結果:
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLicmbw5SZmZTZ0cDN1YjMhNWYhNmN2QmN2IjM0AjYzkzNkJ2N48CX0JXZ252bj91Ztl2Lc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)