猴子選大王問題

《猴子選大王問題》由會員分享，可在線閱讀，更多相關(guān)《猴子選大王問題（17頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

1、這是17世紀(jì)的法國數(shù)學(xué)家加斯帕在《數(shù)目的游戲問題》中講的一個故事：15個教徒和15個非教徒在深海上遇險(xiǎn)，必須將一半的人投入海中，其余的人才能幸免于難，于是想了一個辦法：30個人圍成一圓圈，從第一個人開始依次報(bào)數(shù)，每數(shù)到第九個人就將他扔入大海，如 此循環(huán)進(jìn)行直到僅余 15個人為止。問怎樣排法，才能使每次投入大海的都是非教徒。 題分析 算法設(shè) 約瑟夫問題并不難， 但求解的方法很多；題目的變化形式也很多。這里給出一種實(shí)現(xiàn)方 題目中30個人圍成一圈，因而啟發(fā)我們用一個循環(huán)的鏈來表示?？梢允褂媒Y(jié)構(gòu)數(shù)組來 構(gòu)成一個循環(huán)鏈。結(jié)構(gòu)中有兩個成員，其一為指向下一個人的指針，以構(gòu)成環(huán)形的

2、鏈； 其二 /、* 為該人是否被扔下海的標(biāo)記，為1表示還在船上。從第一個人開始對還未扔下海的人進(jìn)行 計(jì)數(shù)，每數(shù)到 9 時(shí)，將結(jié)構(gòu)中的標(biāo)記改為 0，表示該人已被扔下海了。這樣循環(huán)計(jì)數(shù)直到有 這樣循環(huán)計(jì)數(shù)直到有 約瑟夫問題是個有名的問題： N 個人圍成一圈，從第一個開始報(bào)數(shù)，第 從第一個開始報(bào)數(shù)，第 M 個將被殺掉， 最后剩下一個，其余人都將被殺掉。例如 N=6 ， M=5 ，被殺掉的人的序號為 5， 4 ， 6 ， 2， M ，使得所 有的壞 人在 殺掉 ng int n,m,a [1 01],k,i,j,nu m; -2,

3、 -1, 0, 1, 2, k-2 現(xiàn)在 們把他 號做 假定在圈子里前K個為好人，后K個為壞人，你的任務(wù)是確定這樣的最少 k+1 k+2 >1 >2 k-2 k-1 > n-2 > n-1 變換后就完完全全成為了(n-1)個人報(bào)數(shù)的子問題，假如我們知道這個子問題的解：例 如 x 是最終的勝利者，那么根據(jù)上面這個表把這個 x變回去不剛好就是n個人情況的解 ？??！變回去的公式很簡單，相信大家都可以推出來：x'=(x+k)modn 如何知道(n-1)個人報(bào)數(shù)的問題的解？對，只要知道(n-2)個人的解就行了。(n-2)個人的 解呢？當(dāng)然是先求 (

4、n-3)的情況這顯然就是一個倒推問題！好了，思路出來了，下面寫 令 f 表示 i 個人玩游戲報(bào) m 退出最后勝利者的編號，最后的結(jié)果自然是 f[n] >1) (f+m 有了這個公式，我們要做的就是從 我們要做的就是從 1-n順序算出 f的數(shù)值，最后結(jié)果是 f[n]。 因?yàn)閷?shí)際 生活中編 號總是 開始 我們輸出 于是 逐級遞推 保存 f，程 序也 是異 print for f("N (i 2; "); sc anf "% d", n, &m ); i+ +) )%i;

5、 這個算法的時(shí)間復(fù)雜度為 print va wri 一百萬，一千萬的情況不是問題了。 te 而且往往 約瑟夫 n個人排成一圈。從某個人開始，按順時(shí)針方向依次編號。從編號為 ”報(bào)數(shù)，報(bào)到 個數(shù)是有限的， 輸入 個正整數(shù) 個正 "T ln( 會成 'T wi O(n)，相對于模擬算法已經(jīng)有了很大的提高。算 題1 可見， 倍地 0e1 De nn wi %d s+ 適當(dāng)?shù)剡\(yùn)用數(shù)學(xué)策略，不僅可以讓編程變得簡單， 提高算法執(zhí) scrip 從某個人開始

6、，按順時(shí)針方向依次編號。從編號為 2的人退出圈子。這樣不斷循環(huán)下去，圈子里的人將不斷減少。由于人 n，m等于 行效率 vijios) tion 1的人開始順時(shí)針 此最終會剩下一個人。試問最后剩下的人最開始的編號。 格式 Input For mat n，表示人的個數(shù)。輸入數(shù)據(jù)保證數(shù)字 n不超過 100位。 Output For mat 整數(shù)。它 表示經(jīng)過“ 報(bào)數(shù)后最后 剩下 編號。 例輸 例輸 Sam ple put Sam ple ut put

7、 時(shí)間 Time Limitation 初見這道 我們先拿手來算，可知 有如下規(guī)律：從 素的個 去，再寫過程，又把一些簡單的過程合到主程序中了，所以有點(diǎn)亂，也有點(diǎn)猥瑣。起提供思 能會 想到 數(shù)據(jù)實(shí)在太 大啦??！ n分別為 1，2， 3， 4， 6， 7， 8...時(shí)的結(jié)果是1 1，3， 1， 1到下一個 1為一組，每一組中都是從 1開始遞增的奇數(shù)，且每組元 且每組元 ,c:= 為某 組的元素

8、個數(shù) ③whilec< c{ an 有了思路，再加上高精度就可以了。 路的作用 為現(xiàn)在 所加 數(shù)｝ (b:=b*2,c:=b+c){超過目標(biāo) 時(shí)停 止加數(shù)｝ 到前 算出 組的第 幾個 元素 求出 該元素 我寫的代碼比較猥瑣， 因?yàn)槭窍劝焉厦娴乃悸非眠M(jìn) 還是完全可以 vara,b,c:array[1 105]ofinteger la,lb,lc,i integer trin

9、 p r o c e d u r e i n c c J for fo if c< gi oa ue th fo do b> e n d J p r o c e d u r e d e c c J ifif e n d J

10、 b e g i n fo for i:=105 or ow to do if a>0 to th en j:=i wri rea en a) r la e a =l d e n ln ( h s ( ); g t s ); for i:=la dow nto1 do a:= ord (s[

11、l a+1 -i]) -ord ('0'); b [ 1 ] = 1 ; c [ 1 ] = 1 ; wh i le c xi a o a do b e g i n d o u b l e b ; i n c c ; e n d ; d e c c ; f u a ;

12、 o u t i t ; e n d . [ 編 輯 本 段 ] 約瑟 夫問 題 的另 外 一 個 有 名 的 例 子： [ 編 輯 本 段 ] 猴 子 選 大 王 一 ． 問 題 描 述 ： 一堆猴子都有編號，編號是1，2，3...m,這群猴子（m）按照1-m的順序圍坐一圈， 從第1開始數(shù)，每數(shù)到第N，該猴子就要離開此圈，這樣依次下來，直到圈中

13、只剩下最 后一只猴子，則該猴子為大王。 二．基本要求： （1）輸入數(shù)據(jù)：輸入m,nm,n為整數(shù)，n

14、 1、 or rin ca a1開始報(bào)數(shù)，一圈之后，剩下的人為 (i=2; tf (" Th i+ +) is (s "% %d", ); a( 圈之后，剩下的人為 a1,a2,a4,a5,...a(n-n mod m)% s+ i; ); ), 3-1),a(n-n mod a(n-n 2、若3|n,則最后死的 若nmod3w0Lf(n-[n/3])<=nmod3 若nmod3w0Lf(n-[n/3])>nmod3 mod3),下一輪第一個報(bào)數(shù)的是a(n-nmod 人為新一輪的第F 則最后死的人為新

15、一輪的第 則最后死的人為新一輪的第 3+1) (n-[n/3])個人 n-[n/3]+F(n-[n/3])-(n F(n-[n/3])- nmod3) 3、新一輪第k個人對應(yīng)原來的第3*[(k-1)/2]+(k-1)mod 2+1個人 F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(xiàn) 當(dāng)f(n-[n/3])<=nmod3 當(dāng)f(n-[n/3])>nmod3 (6)=1， 時(shí)k=n-[n/3]+F(n-[n/3])-(nmod3),F(n)=3*[(k-1)/2]+(k-1)mod 時(shí)k=F(n-[n/3])-(nmod3)，F(xiàn)(n)=3*[(

16、k-1)/2]+(k-1)mod2+1 這種算法需要計(jì)算[log(3/2)2009]次這個數(shù)不大于22,可以用筆算了 第二 圈， 殺 死 4 4 6 人， 還 剩 下 8 9 4 人 第三 圈， 殺 死 2 9 8 人， 還 剩 下 5 9 6 人 第四 圈， 殺 死 1 9

17、 8 人， 還 剩 下 3 9 8 人 第五 圈， 殺 死 1 3 2 人， 還 剩 下 2 6 6 人 第六 圈， 殺 死 8 8 人， 還 剩 下 1 7 8 人 第七 圈， 殺 死 5 9 人， 還 剩 下 1 1 9 人 2007，還剩下1340個人， 第八圈 殺死 39人，還剩下 80人 第一圈，將殺死 669 個人，這一圈最后一個被殺死的人是 第九圈 殺死 26 人， 還剩下 54 人 第十圈 殺死 18 人， 還剩 36 人 十一圈 殺死

18、12 人， 還剩 24 人 十二圈 殺死8人 十三圈 殺死5 還 剩 16 人 還剩 11 人 十四圈 殺死3 人 ，還 剩8人 十五 圈，殺死2 人 ，還 剩6人 F(1)=1,F(2)=2,F(3)=2 F(4)=1,F(5)=4， F(6)=1， 然后逆推回 F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130 F(596)=191F(894)=286F(1340)=425F(2009)=634