首页 > 代码库 > HDOJ 1005 Number Sequence
HDOJ 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).
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
这个题目要求计算指定的数列,开始计算时直接for循环来计算要求的数据,但是提交上去后发现超时了。
后来发现这个题目的数列肯定是有周期的,只要求出这个周期即可解决这个问题....但是其周期也是从第3项开始,如果从第一项计算时提交上去出现WA,网上查找资料后发现,这个数列的周期要从第3项开始。如果从第一项开始时,7、7、10时,其周期是1、1、0、0、0.......这样不可能计算出周期,所以应该从第3项开始计算其周期。
1 #include <iostream> 2 using namespace std; 3 #define Max 100 4 int main() 5 { 6 unsigned int A,B,n,result,fn[Max]={0}; 7 int i=0; 8 unsigned int f1,f2; 9 cin>>A>>B>>n; 10 while(A||B||n) 11 { 12 f1=1; 13 f2=1; 14 fn[0]=(A*f1+B*f2)%7; 15 fn[1]=(A*fn[0]+B*f2)%7; 16 for(i=2;i<=n;i++) 17 { 18 fn[i]=(A*fn[i-1]+B*fn[i-2])%7; 19 if(fn[i-1]==fn[0]&&fn[i]==fn[1]) 20 { 21 result=fn[(n-3)%(i-1)];//求出周期 22 break; 23 } 24 } 25 if(n==1||n==2) 26 { 27 cout<<f1<<endl; 28 } 29 else 30 cout<<fn[(n-3)%(i-1)]<<endl; 31 cin>>A>>B>>n; 32 } 33 return 0; 34 }
心得:计算这种数列时,必须要对其周期进行计算,这样能够节省大量时间....
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。