張谞晟

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

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

張谞晟

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 復(fù)雜度分析

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

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

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

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

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

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

比如說，發(fā)送者輸入的明文為“helloworld”，輸入密鑰k1為6，k2為4，將字符串分成兩組，分別為“hellow”和“orld”根據(jù)約瑟夫環(huán)算法得到出圈順序?yàn)?, 2, 1, 3, 6, 5，將兩個(gè)分組按出圈順序移位（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ù)組的實(shí)現(xiàn)[J].科技信息，2010（21）：586.

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

[3]潘大志.遞推算法在擴(kuò)展約瑟夫環(huán)問題中的應(yīng)用[J].計(jì)算機(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é)生；研究方向：程序逆向，算法分析。