杭电 ACM 1004Number Sequence

69 阅读 0 评论 46 点赞

我是靠谱客的博主高贵砖头，最近开发中收集的这篇文章主要介绍杭电 ACM 1004Number Sequence，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述




微软招聘信息（主要针对已经有工作经验的） 
Number
Sequence
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 68329    Accepted Submission(s): 15854 

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



 



Author


CHEN, Shunbao


 



Source


ZJCPC2004 


 



Recommend


JGShining

这个题关键就是思路的问题，我刚开始也没有搞懂该怎样算，最后也是看了别人的思路才明白，其实就是一个循环数，可以看得出来f（n）是对7取的模就可得肯定是0-6之间的数，而f(n) = (a *f(n - 1) + b* f(n - 2))%7，所以从当有两个数和前面两个数一样的时候，f(n)的值就开始了循环了，从0-6中任取两个数可以有7*7= 49种组合，所以在第51个之内一定一定会有两个连续的数和前面的某两个连续的数相等，此时循环就开始了，后面的f(n)的值就不用算了，只需要根据循环开始位置和周期就可得出了。


#include <iostream>
using namespace std;
int main()
{
int A,B;
int N;
int f[50];
while(cin>>A>>B>>N)
{
if(A==0&&B==0&&N==0)break;
int n=3;
f[1]=f[2]=1;
for(n=3;n!=50;++n)
{
f[n]=(A*f[n-1]+B*f[n-2])%7;
if(f[n]==1&&f[n-1]==1)break;
}
N=N%(n-2);
if(N==0)cout<<f[(n-2)]<<endl;
else cout<<f[N]<<endl;
}
return 0;
}

这是别人的代码，C++的，

我的源代码：

#include<stdio.h>
int main(void)
{
int i, j, a, b, f[51], k, m;
long n;
while(1)
{
f[1] = 1;
f[2] = 1;
m = 0;
scanf("%d%d%ld", &a, &b, &n);
getchar();
if(a == 0 && b == 0 && n == 0)
break;
for(i = 3;i < 51;i++)
{
f[i] = (a * f[i - 1] + b * f[i - 2]) % 7;
for(j = 2;j < i;j++)
{
if(f[j - 1]==f[i - 1] && f[j]==f[i])
{
m = j - 1;
k = i - j;
break;
}
}
if(m != 0)
break;
}
if(n < m)
printf("%dn", f[n]);
else
printf("%dn", f[(n - m) % k + m]);
}
return 0;
}