首页 > 代码库 > HDOJ1005 数列
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).
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 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 5 int myfunction( int A, int B, int n ) 6 { 7 int counts = n-3+1; 8 int first=1,second=1,result; 9 for( int i=0; i<counts; i++ )10 {11 result = (B*first+A*second)%7; //大部分的时间都浪费在了这里12 first = second;13 second = result;14 }15 return result;16 }17 18 int main(void)19 {20 int A,B,n;21 22 while(1)23 {24 cin>>A>>B>>n;25 if( A==0 && B==0 && n==0 )26 break;27 if( n==1 || n==2 )28 cout<<1<<endl;29 else30 {31 cout<<myfunction(A,B,n)<<endl;32 }33 }34 return 0;35 }
其实这个数列是有规律的,只要算出它的一圈数列后,再算出n中有多少圈,之后就知道最终得出圈中哪个数。
例如输入1 2 10000后,数列的前几个数为1 1 3 5 4 0 1 1
它开始转圈了,因此我将程序改成如下所示:
1 #include<iostream> 2 using namespace std; 3 int main() 4 { 5 int a,b,n,i,m,t[100]; 6 t[1]=1; 7 t[2]=1; 8 while(cin>>a>>b>>n) 9 {10 if((a==0)&&(b==0)&&(n==0))11 break;12 a=a%7;13 b=b%7;14 for(i=3; i<100; i++)15 {16 t[i]=(a*t[i-1]+b*t[i-2])%7;17 if((t[i]==1)&&(t[i-1]==1))18 {19 break;20 }21 }22 m=n%(i-2);23 if(m==0)24 cout<<t[i-2]<<endl;25 else26 cout<<t[m]<<endl;27 }28 return 0;29 }
哈哈,AC了
这道题给我的提示是,遇到数列题目时要想想里面是不是存在“转圈”现象,发觉里面的规律,之后编程就容易了。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。