首页 > 代码库 > HDOJ1005 数列

HDOJ1005 数列

2024-07-17 09:57:51   216人阅读

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 #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了

 

这道题给我的提示是，遇到数列题目时要想想里面是不是存在“转圈”现象，发觉里面的规律，之后编程就容易了。


联系
我们