题目链接:杭电OJ 1005
超时代码如下(而且开辟的数组空间大小不够):
#include <stdio.h>
int m[100000];
int f(int n,int a,int b)
{
m[1] = 1;
m[2] = 1;
for (int i = 3; i <= n; i++)
{
m[i] = (a * m[i - 1] + b * m[i - 2]) % 7;
}
return m[n];
}
int main()
{
int n, a, b;
while (scanf_s("%d%d%d", &a, &b, &n) != EOF)
{
if (n == 0 || a == 0 || b == 0) break;
printf("%d\n",f(n,a,b));
}
return 0;
}
最后是对7取余数,所以,f(n-1),f(n-2)最多各有七种情况(0、1、2、3、4、5、6),所以f(n)最多有7*7=49种情况,所以从一开始到49可能不尽相同,但是从50开始则开始循环,f(50)=f(50%49)=f(1)。这是解决超时和内存不够的办法。
改进之后:
#include <stdio.h>
int m[50];
int main()
{
int n, a, b;
while (scanf_s("%d%d%d", &a, &b, &n) != EOF)
{
if (n == 0 || a == 0 || b == 0) break;
m[1] = 1;
m[2] = 1;
for (int i = 3; i <= 49; i++)
{
m[i] = (m[i - 1] * a + m[i - 2] * b) % 7;
}
printf("%d\n", m[n % 49]);
}
return 0;
}