約瑟夫環(huán)問題實(shí)驗(yàn)報(bào)告

約瑟夫環(huán)問題實(shí)驗(yàn)報(bào)告在浩瀚的計(jì)算機(jī)語言中，總有一些算法——雖然碼量很少，但卻能完美又巧妙地解決那些復(fù)雜的問題。接下來，我們要介紹的“約瑟夫環(huán)”問題就是一個(gè)很好的例子。問題背景這個(gè)問題來源于猶太人約瑟夫經(jīng)歷過的故事，在羅馬人占領(lǐng)喬塔帕特后，約瑟夫和他的朋友與39個(gè)猶太人躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第3人時(shí)，該人就必須自殺，然后再由下一個(gè)人重新報(bào)數(shù)，直到所有人都自殺身亡為止。然而約瑟夫和他的朋友并不想遵從這個(gè)規(guī)則，于是，他們想出新的思路：從一個(gè)人開始，越過k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過），并殺掉第k個(gè)人。接著，再越過k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？如果你是約瑟夫，你會(huì)站在什么樣的位置呢？數(shù)數(shù)與大家一起，從運(yùn)用以下兩個(gè)方面來解決這個(gè)問題。模擬法01循環(huán)單鏈表實(shí)現(xiàn)：約瑟夫環(huán)問題的基本形式為：n個(gè)人圍成一圈，從第一個(gè)開始報(bào)數(shù)，每報(bào)到m者將被殺掉，直至只剩一個(gè)人。如：N=6，M=51234

56123

46123

61

23

1

31由此可以很容易想到使用循環(huán)單鏈表來實(shí)現(xiàn)。創(chuàng)建指針p，當(dāng)指針移動(dòng)m-1個(gè)位置后，就該刪除下一個(gè)節(jié)點(diǎn)，由此類推，直至鏈表中只含一個(gè)節(jié)點(diǎn)。02代碼實(shí)現(xiàn)：用數(shù)組也可以實(shí)現(xiàn)暴力模擬約瑟夫環(huán)。但是，用模擬法有一個(gè)很明顯的缺陷——時(shí)間復(fù)雜度高達(dá)O(nm)，所以下面考慮優(yōu)化算法。數(shù)學(xué)法

用遞歸法優(yōu)化到O(n)復(fù)雜度在DonaldE.Knuth的《具體數(shù)學(xué)》中，對(duì)m=2的情況使用了遞歸的解決方法，并推出了一個(gè)常數(shù)表達(dá)式，使得此種情況下，算法的復(fù)雜度為常量。同時(shí)，這種思路也可以應(yīng)用于n>2的情況，但無法得出常數(shù)表達(dá)式，推廣后的遞歸算法具體的思路如下：當(dāng)n個(gè)人圍成一圈并以m為步長第一次報(bào)數(shù)時(shí)，第m個(gè)人出列，此時(shí)就又組成了一個(gè)新的，人數(shù)為n-1的約瑟夫環(huán)，要求n個(gè)人的約瑟夫環(huán)問題的解，就依賴于求n-1個(gè)人的約瑟夫問題的解，要求n-2個(gè)人的約瑟夫問題的解，則依賴于求n-2個(gè)人的約瑟夫換問題的解，依次類推，直至求1個(gè)人的時(shí)候，該問題的解。遞推公式：f(N,M)=f((N-1,M)+M)%N其中，f(N,M)表示N個(gè)人報(bào)數(shù)，每報(bào)到M時(shí)殺掉的那個(gè)人，最終勝利者的編號(hào)推導(dǎo)過程：舉例：11個(gè)人參與游戲，每報(bào)到3的人被殺掉第一輪：從No.1開始報(bào)數(shù)，No.3被殺第二輪：No.4從1開始報(bào)數(shù)，這時(shí)可以認(rèn)為隊(duì)伍的頭是No.4，No.6被殺……第九輪：No.2從1開始報(bào)數(shù)，成為隊(duì)伍的頭，No.8被殺第十輪：No.2從1開始報(bào)數(shù)，……No.2被殺勝利者為No.7假設(shè)1：當(dāng)游戲中剩余11人時(shí)，我們知道勝利者為No.6。那么下一輪剩余10人時(shí)，勝利者為No.6。因?yàn)閯h掉No.3后，之后的人都往前移動(dòng)了3位；假設(shè)2：當(dāng)游戲中剩余10人時(shí)，我們知道勝利者為No.3。那么下一輪剩余11人時(shí)，勝利者的編號(hào)是幾？該問題可以看作假設(shè)1的逆過程，因此：f(11,3)=f(10,3)+3為防止數(shù)組越界，對(duì)當(dāng)前人數(shù)取模：f(11,3)=(f(10,3)+3)%11假設(shè)3：游戲中剩余N人，報(bào)到M者被殺，數(shù)組移動(dòng)情況為：每殺一個(gè)人，下一個(gè)人成為頭，相當(dāng)于把數(shù)組向前移動(dòng)M位。若已知剩余N-1人時(shí)勝利者下標(biāo)為，則N個(gè)人時(shí)，就是往后移動(dòng)M位。因此推導(dǎo)出遞推公式：f(N,M)=(f(N-1,M)+M)%N代碼實(shí)現(xiàn)typedeflonglongLL;LLkill(LLn,LLm){

LLi,p=0;

if(m==1)returnn;

else{for(i=2;i<=n;i++){p=(p+m)%i;}returnp+1;}}優(yōu)化遞推：復(fù)雜度降至O(m)

觀察以上代碼中的p,p=(p+m)%i當(dāng)i比較大時(shí)，m遠(yuǎn)遠(yuǎn)小于i。因此隊(duì)伍每次不止可以移動(dòng)一個(gè)m位，可以一次移動(dòng)x*m位來跳過x個(gè)i。當(dāng)m遠(yuǎn)遠(yuǎn)小于n時(shí)，效率會(huì)更高。

對(duì)于當(dāng)前的p1，設(shè)：p1+x*m=i，當(dāng)i+x>=n時(shí)，表示這次移動(dòng)位數(shù)已經(jīng)超過了n。令更新后的p2=p1+(n-i)*m，并且i=n來跳出本次循環(huán)。使用以上算法，運(yùn)行速度將與游戲人數(shù)沒有關(guān)系。代碼實(shí)現(xiàn)那么……還可以變得更簡單嗎？我們先來看這道題目問題為約瑟夫環(huán)問題的經(jīng)典形式，故不再翻譯。但要注意到，在n可達(dá)10^12的情況下，再運(yùn)用以上的遞歸法顯然會(huì)超時(shí)。因此我們要重新考慮。假設(shè)初始編號(hào)為1，2，······，n，現(xiàn)在考慮一種新的編號(hào)方式。第一個(gè)人不會(huì)被踢掉，那么他的編號(hào)從n開始往后加1，變成n+1，然后第二個(gè)人編號(hào)變?yōu)閚+2，直到第q個(gè)人，他被踢掉了。然后第q+1個(gè)人編號(hào)繼續(xù)加1，變成了n+q，依次下去?？紤]當(dāng)前踢到的人編號(hào)為kq，那么此時(shí)已經(jīng)踢掉了k個(gè)人，所以接下去的人新的編號(hào)為n+k(q-1)+1……

所以編號(hào)為kq+d的人編號(hào)變成了n+k(q-1)+d，其中1<=d<q。直到最后，可以發(fā)現(xiàn)活下來的人編號(hào)為qn，問題是怎么根據(jù)這個(gè)編號(hào)推出他原來的編號(hào)？以n=10,q=3為例，下圖就是每個(gè)人新的編號(hào)：

令N=n+k(q-1)+d，那么他上一輪的編號(hào)是kq+d=kq+N-n-k(q-1)=k+N-n,因?yàn)閗=(N-n-d)/(q-1)=[(N-n-1)/(q-1)],所以上一次編號(hào)可以寫為[(N-n-1)/(q-1)]+N-n

如果用D=qn+1-N代替N將會(huì)進(jìn)一步簡化算法：算法偽代碼如下：D=1whileD<=(q-1)n:D=kAns=qn+1-D其中k=Dq/(q-1)c++代碼實(shí)現(xiàn)在這樣優(yōu)美而又簡潔的算法下，問題便迎刃而解。