數(shù)字游戲，如果硬說(shuō)它有算法的話，那也只能說(shuō)去找規(guī)律了。
初看本題的人，會(huì)覺(jué)得這這是一個(gè)簡(jiǎn)單的遞歸題目，其實(shí)我一開(kāi)始也是這么想的，但后來(lái)提交了如下代碼后我才明白。

#include?<iostream>
using?namespace?std;
int?main()
{
????int?a,b,n;
????while(cin>>a>>b>>n?&&?n)
????{
????????int?f1?=?1,f2?=?1,f,t?=?3;
????????while(t?<=?n)
????????{
????????????f?=?(a*f2?+?b*f1)%7;
????????????f1?=?f2;
????????????f2?=?f;
????????????++t;
????????}
????????cout<<f<<endl;
????}
????return?0;
}

??????細(xì)細(xì)看下題目中的條件要求：1 <= n <= 100,000,000，你就應(yīng)該明白本題絕不是簡(jiǎn)單的遞歸就可以解決的，上述代碼的答案是TLE.(后來(lái)加)：其實(shí)看到題目中出現(xiàn)求余運(yùn)算，我就應(yīng)該很快的反應(yīng)過(guò)來(lái)，這道題目絕對(duì)不是簡(jiǎn)單的遞歸運(yùn)算就可以解決問(wèn)題的，因?yàn)榍笥噙\(yùn)算會(huì)有一定的重復(fù)，所以，本題中的數(shù)據(jù)一定會(huì)出現(xiàn)重復(fù)，從重復(fù)中找到規(guī)律，問(wèn)題就可以解決了。

??????其實(shí)解決本題的方法是找出規(guī)律，當(dāng)f1，f2和a b的值確定后，你就可以利用題目中給出的公式往后計(jì)算了，如果我們把所有fn的取值算作一個(gè)隊(duì)列(非數(shù)據(jù)結(jié)構(gòu)中的隊(duì)列)的話，可以肯定的是，這個(gè)隊(duì)列不會(huì)延展太長(zhǎng)，到了一定長(zhǎng)度，肯定會(huì)出現(xiàn)重復(fù)，而我們需要做的就是找出這個(gè)重復(fù)點(diǎn)。
??????什么時(shí)候會(huì)出現(xiàn)重復(fù)呢，如果我們假定隊(duì)列是如下循環(huán)的：

f?=?(a*f2?+?b*f1)%7;
f1?=?f2;
f2?=?f;

那么很簡(jiǎn)單就可以推出：當(dāng)f1 = 1，且f2 = 1時(shí)就會(huì)出現(xiàn)隊(duì)列一開(kāi)始的循環(huán)了。此時(shí)我們就不需要繼續(xù)向下遞歸了。不過(guò)我們需要把出現(xiàn)循環(huán)以前的所有值都保存下來(lái)。相比于時(shí)間復(fù)雜度來(lái)說(shuō)，這點(diǎn)空間復(fù)雜度還是值得的。
這樣寫(xiě)了代碼，結(jié)果卻Memory Limit Exceeded,郁悶，今天太晚了，明天再搞。

#include?<iostream>
#include?<vector>
using?namespace?std;
int?main()
{
????int?a,b,n;
????while(cin>>a>>b>>n?&&?n)
????{
????????vector<int>?ivec;
????????int?f1?=?1,f2?=?1,f,t?=?3,count,num;
????????ivec.push_back(f1);
????????ivec.push_back(f2);
????????while(1)
????????{
????????????f?=?(a*f2?+?b*f1)%7;
????????????f1?=?f2;
????????????f2?=?f;
????????????if(f1?==?1?&&?f2?==?1)
????????????????break;
????????????else
????????????????ivec.push_back(f);
????????????++t;
????????}
????????count?=?t?-?2;
????????num?=?n%count;
????????if(num?==?0)
????????????num?=?count;
????????cout<<ivec.at(num?-?1)<<endl;
????????ivec.clear();
????}
????return?0;
}

??????昨天晚上找了杭電的WSN大牛問(wèn)了下，一開(kāi)始他也不是很清楚，只是讓我把vector<int> ivec;設(shè)置為全局變量試下，這個(gè)我早已經(jīng)試過(guò)，結(jié)果還是Memory limit Exceeded，問(wèn)題應(yīng)該不是出在這里，我初步猜測(cè)應(yīng)該是有一組測(cè)試數(shù)據(jù)，讓vector<int> ivec一直在執(zhí)行push_back()操作，所以才會(huì)出現(xiàn)上述錯(cuò)誤，看了WSN的AC代碼后，他與我想法的區(qū)別在于數(shù)字的重復(fù)不一定是我所想的從頭開(kāi)始的重復(fù)，也可能是在中間部分開(kāi)始重復(fù)的，舉個(gè)簡(jiǎn)單的例子，這里沒(méi)有理由依據(jù)：1 1 2 5 6 5 4 4 8 6 2 5 4....,如果是這樣下去的話，從5 和 4開(kāi)始就是重復(fù)了，并不是從開(kāi)始的1 和1 開(kāi)始重復(fù)的，這樣也有道理。而且也實(shí)際上應(yīng)該這么考慮才對(duì)。

??????后來(lái)，我隨便試了幾組數(shù)據(jù)，就發(fā)現(xiàn)出現(xiàn)了問(wèn)題，當(dāng)我輸入21 56 45這組數(shù)據(jù)時(shí)，上面的程度沒(méi)有輸出，Debug后才知道，其實(shí)不是沒(méi)有輸出，而是程序在while(1)處進(jìn)入了死循環(huán)，這樣就導(dǎo)致我的ivec一直不間斷的進(jìn)行push_back()操作，才會(huì)有了開(kāi)始的Memory Limit Exceeded這種錯(cuò)誤。既然找到了錯(cuò)誤，下面就剩下修改代碼了，我決定采用WSN的想法，在判斷是否開(kāi)始重復(fù)時(shí)多加入一個(gè)條件判斷，修改后AC，代碼及注釋如下：

?

#include?<iostream>
#include?<vector>
using?namespace?std;
vector<int>?ivec;
//布爾數(shù)組元素flag[i][j]如果為true,則說(shuō)明前面已經(jīng)出現(xiàn)了i?和?j兩者的組合
bool?flag[7][7];
void?init(void)
{
????int?i,j;
????for(i?=?0;i?<?7;++i)
????????for(j?=?0;j<?7;++j)
????????????flag[i][j]?=?false;
}
int?main()
{
????int?a,b,n;
????while(cin>>a>>b>>n)
????{
????????if(a?==?0&&b?==?0&&n?==?0)
????????????break;
????????ivec.clear();
????????init();
????????ivec.push_back(1);
????????ivec.push_back(1);
????????flag[1][1]?=?true;
????????int?count?=?1,f;
????????while(1)
????????{
????????????f?=?(a*ivec.at(count)%7?+?b*ivec.at(count?-?1)%7)%7;
????????????ivec.push_back(f);
????????????++count;
????????????//如果flag變量為true，則說(shuō)明前面已經(jīng)出現(xiàn)了這兩者的組合，出現(xiàn)重復(fù)，無(wú)需下一步計(jì)算，直接break退出即可
????????????if(flag[ivec.at(count)][ivec.at(count?-?1)]?==?true)
????????????????break;
????????????else
????????????????flag[ivec.at(count)][ivec.at(count?-?1)]?=?true;
????????}
????????//count中存放的是ivec中出現(xiàn)循環(huán)前的元素總個(gè)數(shù),注意ivec中的下標(biāo)是從0開(kāi)始計(jì)數(shù)的
????????count?=?count?-?1;
????????if(n?<?count)
????????????cout<<ivec.at(n-1)<<endl;
????????else
????????{
????????????int?j;
????????????//for循環(huán)的目的是找出從那個(gè)地方開(kāi)始重復(fù)，此處應(yīng)該是從j處開(kāi)始循環(huán),注意j是從0下標(biāo)開(kāi)始計(jì)數(shù)的
????????????for(j?=?0;;++j)
????????????????if(ivec.at(count)?==?ivec.at(j)?&&?ivec.at(count?+?1)?==?ivec.at(j+1))
????????????????????break;
????????????n?=?(n?-?j)%(count?-?j);
????????????if(n?==?0)
????????????????n?=?count?-?j;
????????????n?+=?j;
????????????cout<<ivec.at(n-1)<<endl;
????????}
????}
????return?0;
}

后記：在我解決我這道題出現(xiàn)問(wèn)題的過(guò)程中，我也在網(wǎng)上搜索了很多，找到了一些代碼去測(cè)試，結(jié)果發(fā)現(xiàn)其實(shí)杭電服務(wù)器上關(guān)于本題的測(cè)試數(shù)據(jù)是不完整的，就拿我剛才那個(gè)測(cè)試數(shù)據(jù)來(lái)說(shuō)：21 56? n來(lái)說(shuō)，其循環(huán)應(yīng)該為：
1 1 0 0 0 0 0 0 0 ...........，而我在網(wǎng)上找到的一些代碼，比如下面這個(gè)代碼：(來(lái)源：http://hi.baidu.com/chenghui2050/blog/item/84c552ad3124ee0f4a36d660.html)

#include<iostream>
using?namespace?std;
int?main()
{
????int?a,b,i;
????long?long?f[55],n;
????while(cin>>a>>b>>n)
????{
????????if(a==0&&b==0&&n==0)break;
????????f[1]=f[2]=1;
????????for(i=3;i<=49;i++)
????????f[i]=(a*f[i-1]+b*f[i-2])%7;
????????cout<<f[n%48]<<endl;
????}
????return?0;
}如果輸入21 56 49時(shí)，正確輸出應(yīng)該是0，而上述代碼卻是1，明顯是錯(cuò)誤的，但卻莫名的AC，希望看到的朋友們注意下。題目中并沒(méi)有明確說(shuō)明不會(huì)出現(xiàn)0 0這種情況，要注意。
按照WSN的思路考慮的話，應(yīng)該是考慮比較全面的了，贊the lord of WSNs，呵呵.
這個(gè)問(wèn)題先告一段落了，殘酷的測(cè)試數(shù)據(jù)，倒。。。

轉(zhuǎn)載于:https://www.cnblogs.com/krisdy/archive/2009/04/12/1434013.html

總結(jié)

以上是生活随笔為你收集整理的[HDOJ]1005. Number Sequence的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。