杭电ACM OJ 1005 Number Sequence

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).

超过49个数之后一定会出现和之前的数组合相同的情况,这个我可以了解,但是 为什么最多经过49个数之后一定会出现周期呢?智商太低了,跪求解释

2个回答

这个数组是递推关系得到的,如果连续的2个数与前面某个位置的连续的2个数相同,由递推关系式一定会推出相同的结果,所以就形成循环了。

qq_26793545
Mir.Yang #include<iostream> using namespace std; int re[10000]; int main() { int a,b,n; re[1]=1;re[2]=1; while(cin>>a>>b>>n&&(a||b||n)){ int i; for(i=3;i<10000;i++){ re[i]=(a*re[i-1]+b*re[i-2])%7; if(re[i]==1&&re[i-1]==1) break; } n=n%(i-2); re[0]=re[i-2]; cout<<re[n]<<endl; } return 0; }
5 个月之前 回复
qq_26793545
Mir.Yang 其实可以不需要知道周期的:附上源码:
5 个月之前 回复
u013623867
LinSeanYu 不理解前,看了你的话也还是会不理解,但是我昨晚想明白了,今天看了你的回复,就觉得很有道理,哈哈
4 年多之前 回复

这个题目如果使用数组或者递归都会爆栈,注意到题目中的数都是对7取余,所以相邻的两个数的组合最多有49中,所以最多49次循环就会从头开始循环,这是就可以不用继续执行了,然后将n对i取余,根据余数就可以得到结果。
C++代码:
#include
const int N=55;
int dp[N];
int getRes(int A,int B,int n){
if(n==1||n==2)
r......
答案就在这里:杭电OJ 1005:Number Sequence
----------------------Hi,地球人,我是问答机器人小S,上面的内容就是我狂拽酷炫叼炸天的答案,除了赞同,你还有别的选择吗?

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问