約瑟夫環(huán)的C語言實現(xiàn)與應(yīng)用

張谞晟

（黑龍江大學(xué)，黑龍江 哈爾濱 150081）

約瑟夫環(huán)的C語言實現(xiàn)與應(yīng)用

張谞晟

（黑龍江大學(xué)，黑龍江 哈爾濱 150081）

通過對約瑟夫環(huán)在數(shù)組，鏈表和遞歸方面算法的研究，文章比較了不同算法對時間復(fù)雜度和空間復(fù)雜度的影響，從而多層次理解約瑟夫環(huán)問題，再將約瑟夫環(huán)的算法運用到文本加密方面。

約瑟夫環(huán)；C語言；遞歸

據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。同樣類似的問題還有很多，比如猴子選大王[1]，耶穌找叛徒這類典型問題都是所謂的約瑟夫環(huán)問題。

1 約瑟夫環(huán)問題描述

現(xiàn)在規(guī)定約瑟夫環(huán)問題中的圈中人數(shù)為n，而喊到m的人就得出圈，按著圓圈的順序一次次出圈，問一開始站在哪個位置才能保證成為最后一個還在圈內(nèi)的人。

2 用數(shù)組來實現(xiàn)約瑟夫環(huán)問題

用數(shù)組處理問題的關(guān)鍵就在于：①如何讓數(shù)組首尾相接；②如何在有人出圈后還保持良好的循環(huán)；③處理方法就是用循環(huán)每次讀一個數(shù)組成員，但用i對n取余得到的值作為讀取的數(shù)組成員的下標(biāo)，從而實現(xiàn)首尾相接；④的處理方法就是初始化數(shù)組時讓每個成員的值為1，代表該人還在圈內(nèi)，當(dāng)循環(huán)到1時，就讓報數(shù)cc加一；當(dāng)循環(huán)到0時，就什么都不做，因為該人已出圈[2]。

還有關(guān)于報數(shù)CC的處理也是用的對m取余來處理。

3 用單向循環(huán)鏈表來實現(xiàn)約瑟夫環(huán)問題

同樣的問題用單向循環(huán)鏈表來實現(xiàn)就不用糾結(jié)首尾相接的解決方案了，因為最后一個節(jié)點的next指向了頭節(jié)點。問題變成了：①在一個節(jié)點出圈（被刪除）后，如何將前一個節(jié)點和后一個節(jié)點相連；②如何判斷圈內(nèi)還有一個人。

①的解決方法就是在指針指向前一個節(jié)點的時候就報下一個節(jié)點的數(shù)，如果該數(shù)為m，就讓前一個節(jié)點的next的next賦值給前一個節(jié)點的next，從而使得上一個節(jié)點的next指向下下個節(jié)點，來實現(xiàn)中間節(jié)點的刪除。

②的解決方法就是在令循環(huán)跳出的條件變成當(dāng)頭節(jié)點next的next指向的就是頭節(jié)點（除頭節(jié)點以外只有一個節(jié)點時結(jié)束循環(huán)）

4 用遞歸來實現(xiàn)約瑟夫環(huán)問題

無論是用數(shù)組還是鏈表的方法，由于每次都得報數(shù)（存儲每次出圈的過程），導(dǎo)致這兩種算法的時間復(fù)雜度一直都處于o（nm）的狀態(tài)，雖然鏈表法略微優(yōu)于數(shù)組法，但依舊無法在n和m都很大時讓算法的效率提高一個維度，這個時候遞歸的思想就該上場了[3]。

假設(shè)在第一次喊到m，其出圈后，接下來的序列如下（序號是從0～n-1）

M，m+1 …… n-1，0…… m-3，m-2

將這個序列從0開始重新初始化，得到的序列如下：0，1，…… n-m-1 n-m …… n-3，n-2

而每一次出圈都可以將其像這樣從0開始初始化，由此，n個人的圈在第一個人出圈后，就可轉(zhuǎn)換成n-1個人的出圈問題了，以此類推，最后遞推到1個人的出圈問題了，此時只能是這一個人出圈，序號為0。

設(shè)未重新初始化的序列為f，初始化后的序列為g比較兩個序列的對應(yīng)位置編號關(guān)系可以得到f=（g+m）%n

由此可以得出遞歸關(guān)系式f[i]=（f[i-1]+m）%×i（i為圈內(nèi)人數(shù)）。

通過遞歸算法，可以清楚地發(fā)現(xiàn)，算法的時間復(fù)雜度降到了o（n），而不再是臃腫的o（nm），但美中不足的就是該方法無法存儲每次出圈的過程，但題目未要求輸出每次出圈之人的編號或時間，這個算法的效率還是很高的。

5 復(fù)雜度分析

時間復(fù)雜度：由于數(shù)組與鏈表的實現(xiàn)算法需要模擬報數(shù)過程，在n人的圈中每次從1報數(shù)到m，所以這兩種算法的時間復(fù)雜度為o（nm），當(dāng)n與m相當(dāng)大的時候程序會執(zhí)行速度會很慢。而當(dāng)采用遞歸算法時，由于不需要模擬報數(shù)過程，算法只需要遞歸n次，所以其時間復(fù)雜度為o（n），在n, m很大時也能較快解出答案。

空間復(fù)雜度：由于數(shù)組與鏈表的需要模擬報數(shù)過程，所以每次必須開辟一個個數(shù)為n的數(shù)組，使得其空間復(fù)雜度為o（n），而對于遞歸算法來說，每次需要開辟一個數(shù)來存儲return的值，使得其空間復(fù)雜度也為o（n）。

由此可見，在相同空間復(fù)雜度的情況下，遞歸算法在時間復(fù)雜度上奪得頭籌。所以有的問題用巧妙的數(shù)學(xué)思想來思考并設(shè)計合適的算法會降低算法的時間復(fù)雜度，但在提高程序效率的同時，可能也會犧牲一些過程數(shù)據(jù)作為代價。

6 約瑟夫環(huán)的應(yīng)用

約瑟夫環(huán)這個經(jīng)典的算法在實際生活中可以用來作為一種加密算法，或者也可以作為一種混淆算法。

文本加密：文本發(fā)送者首先輸入一段明文，然后輸入兩個兩個密鑰k1和k2，k1是代表分組長度（約瑟夫環(huán)中人數(shù)n），k2代表原來的約瑟夫環(huán)中的m。先將明文按照分組長度k1拆分成若干段（最后一段可能小于k1），系統(tǒng)根據(jù)約瑟夫環(huán)的算法計算出出圈順序后，每一個出圈的編號就對應(yīng)一個分組中對應(yīng)位字符的移位個數(shù)。

比如說，發(fā)送者輸入的明文為“helloworld”，輸入密鑰k1為6，k2為4，將字符串分成兩組，分別為“hellow”和“orld”根據(jù)約瑟夫環(huán)算法得到出圈順序為4, 2, 1, 3, 6, 5，將兩個分組按出圈順序移位（h+4-〉l, e+2-〉g, l+1-〉m, l+3-〉o, o+6-〉u, w+5-〉b），得到“l(fā)gmoub”和“stmg”，最后合并得到密文“l(fā)gmoubstmg”。

密文接收者在收到密文和密鑰后，同樣也先按照k1分組，再根據(jù)約瑟夫環(huán)算法同樣算出出圈順序后，反向移位密文后就可解得明文。

[1]劉文鋒.約瑟夫環(huán)的C語言數(shù)組的實現(xiàn)[J].科技信息，2010（21）：586.

[2]崔進平.約瑟夫問題的幾種算法[J].泰安師專學(xué)報，2001（6）：27-29.

[3]潘大志.遞推算法在擴展約瑟夫環(huán)問題中的應(yīng)用[J].計算機工程與應(yīng)用，2010（34）：62-63，106.

Implementation and application of C language in Joseph ring

Zhang Xusheng
（Heilongjiang University, Harbin 150081, China）

Based on the Joseph ring in the array, and the recursive algorithm of the list, the article compares the different algorithms of time complexity and space complexity, and multi-level understanding of Joseph ring problem, then applies the Joseph ring algorithm to text encryption.

Joseph ring; C language; recursion

張谞晟（1996— ），男，江蘇常熟，本科，學(xué)生；研究方向：程序逆向，算法分析。