hdoj1005(循环,找规律)

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

1.看到题目第一反应就是用一个函数,用递归求出结果。但感觉这样做太简单了,想到这是个水题,就这么做了,下面是代码。果不其然,TML!!

#include<stdio.h>
int f(int a1,int b1,int n1){
if(n1==1||n1==2)return 1;
else
return (a1*f(a1,b1,n1-1)+b1*f(a1,b1,n1-2))%7;
}
int main(){
int a,b,n;
while(scanf("%d%d%d",&a,&b,&n)==3&&n) //n为0时结束
printf("%d\n",f(a,b,n));
return 0;
}

2.想了很久,想不明白,就去网上看别人的博客。网上的答案实在是参差不齐,但还是慢慢有了思路。

3.首先,因为题目中的f[n]最后是对7取余,故其结果只可能有7个(0~6),所以这道题应该是让大家找规律,找到循环周期,又因为当a,b确定时,f[n]只由f[n-1],f[n-2]决定,而f[n-1],f[n-2]的取值各只有7个,所以最多有49种情况。故周期大小一定<=49。但还有一个很重要的地方就是要注意可能出现循环起点不一定在f[0],f[1],可能先是一段序列,之后才开始循环(但似乎杭电服务器上关于本题的测试数据是不完整的,所以网上很多人把1,1当作循环起始点时也AC了,还是要注意)。之后就是找到循环起始点以及循环长度了。思路是从i=2开始计算f[i],并令j=i-1;j>0;j++。判断是否f[i]==f[j]&&f[i-1]==f[j-1]?从而找到start,len。然后可将n(>start)对应到区间[start,start+len-1]上来,就可以得到f[n]了。

最后,提醒一下注意n到底是数组下标还是数组中的第n个,题目给的是求第n个。我就在这折腾了一个小时,debug半天才发现......

下面是AC代码:

#include<stdio.h>
int main(){
int a,b,n,start,len; //start为循环起点,len为循环长度
while(scanf("%d%d%d",&a,&b,&n)==3&&(a||b||n)){ //a,b,n同时为0时退出循环
n--; //将n变成数组下标
start=len=0;
int f[51]={1,1}; //保存前51项的数组
for(int i=2;i<51;i++){
f[i]=(a*f[i-1]+b*f[i-2])%7; //计算m[i]
for(int j=i-1;j>0;j--){ //从i-1往前找j,使得m[i]==m[j]&&m[i-1]==m[j-1],从而确定循环起点以及循环长度
if(f[i]==f[j]&&f[i-1]==f[j-1]){
start=j-1;
len=i-j;
break;
}
}
if(len>0) //当第一次找到start,len之后退出循环
break;
}
if(n<start)
printf("%d\n",f[n]);
else
printf("%d\n",f[start+(n-start)%len]);
}
return 0;
}

体会:学到了遇到数列题目时要想想里面是不是存在周期现象,发觉里面的规律,之后解题就容易了。

上一篇:Spire.XLS for Java 共同选择Crack by Xacker


下一篇:设备树(device tree)学习笔记