基于雙端隊列的類Josephus逆問題求解

李勝華,趙晗諾

(湖北大學數(shù)學與計算機科學學院,湖北 武漢 430062)

0 引言

一種撲克牌游戲:取A～K 13張撲克牌疊在一起,從上面拿一張放在最下面,再從上面拿一張出來顯示,重復此操作,要求顯示出來的順序是:A、2、3、4、……、J、Q、K.據(jù)說著名猶太歷史學家Josephus有過以下的故事:在羅馬人占領喬塔帕特后,39個猶太人與Josephus及他的朋友躲到一個洞中,39個猶太人決定寧愿死也不要被敵人抓到,于是決定了一個自殺方式:41個人排成一個圓圈,由第1個人開始報數(shù),每報數(shù)到第3人該人就必須自殺,然后再由下一個重新報數(shù),直到所有人都自殺身亡為止.然而Josephus和他的朋友并不想遵從,Josephus要他的朋友先假裝遵從,他將朋友與自己安排在第16個與第31個位置,于是逃過了這場死亡游戲.后人將此游戲推廣成(n,m,k)-Josephus問題[1]:設有n個人圍成一個圓圈,并依次編號為1,2,…,n.要求從編號為k的那個人開始從1報數(shù),順序報數(shù)到m的人出列,然后從出列的下一個人重新開始從1報數(shù),順序報數(shù)到m的人又出列,此過程重復直到所有的人都出列(或只剩下一個人)為止.對于任意給定的自然數(shù)n,m和k,試給出這n個人的出列次序(或最后出隊者的編號).

對于上述的撲克牌游戲,聰明的看客看了幾遍,或記下初始順序或推理一番也會演示了,但很少從理論上研究.毋庸置疑,參加Josephus游戲的現(xiàn)代人都想做Josephus,使自己最后出局.這其實是Josephus逆問題:已知n、m、k及n個人的出列次序,求原始排列順序.對于Josephus問題,文獻[2-5]對其有較深入的研究,他們主要是基于循環(huán)順序表和循環(huán)鏈表兩大類實現(xiàn)方法.然而,這兩類實現(xiàn)方法對于Josephus逆問題求解不方便.

本文中首先對撲克牌游戲及Josephus逆問題進行推廣得到類Josephus逆問題,然后探討適合此類問題求解的數(shù)據(jù)結構及算法.

1 問題的定義

分析(n,m,k)-Josephus問題,可知是對一批數(shù)據(jù)按照規(guī)定的操作規(guī)則進行刪除,每次刪除一個數(shù)據(jù).實際應用中,可以將其推廣為每次刪除多個數(shù)據(jù).下面給出基于操作的類Josephus問題的定義:

1.1類Josephus問題對類型相同依次排列的n個數(shù)據(jù),先進行k次1個數(shù)據(jù)從前面移至后面的操作,然后重復進行下面兩種操作:

1)m次將1個數(shù)據(jù)從前面移至后面;

2)從前面順序取s個數(shù)據(jù)出列.

直至數(shù)據(jù)全部出列,求這n個數(shù)據(jù)的出列次序.

顯然當s=1時,類Josephus問題即是(n,m,k)-Josephus問題.對于類Josephus問題用文獻[2-5]的方法同樣可求解.引言中的撲克牌游戲及Josephus逆問題本質(zhì)上是一個已知操作過程及操作結果,求初始狀態(tài)的問題,為此定義上述問題的逆問題:

1.2類Josephus逆問題對類型相同依次排列的n個數(shù)據(jù),進行與類Josephus問題相同的操作,已知這n個數(shù)據(jù)的出列次序,求它們的原始順序.

下面列舉一些類Josephus逆問題的實例:

例1 引言中的撲克牌游戲:已知n=13,k=0,m=1,s=1,對A～K 13張牌進行類Josephus問題中的操作,要求出列次序為A、2、3、4、…、J、Q、K,求撲克牌的原始順序.

例2 Josephus考慮的問題:已知n=41,k=0,m=2,s=1,對編號1～n的人進行類Josephus問題中的操作,出列順序要求Josephus和他的朋友在最后兩個,求Josephus和他的朋友的原始號碼.

由類Josephus逆問題也產(chǎn)生了一類撲克牌游戲:

例3 A、3、5、7、9各兩張,2、4、6、8、10各一張共15張撲克牌疊在一起,每次從上面拿牌到下面2次,再從上面出牌2次,要求牌出來的順序為A、A、2、3、3、4、5、5、6、7、7、8、9、9、10.求撲克牌的原始順序.這也是n=15,k=0,m=2,s=2的類Josephus逆問題.

類Josephus逆問題是已知操作過程及操作結果,求操作初態(tài),很容易想到用倒推法求解:在操作結果的基礎上進行逆向操作得出數(shù)據(jù)的初始狀態(tài).為了驗證解的正確性,可以利用類Josephus逆問題的解再做類Josephus問題.用計算機求解問題需要選擇合適的數(shù)據(jù)結構來存儲這些數(shù)據(jù),考慮操作只涉及到前面和后面數(shù)據(jù)的處理,求解過程的逆操作也只是前面和后面數(shù)據(jù)的處理,故隊列應是表示前述問題中的數(shù)據(jù)最合適的數(shù)據(jù)結構.

隊列是一種插入和刪除操作受限的線性表,它的插入和刪除只能在兩端進行.如果只能在一端插入,另一端刪除的隊列稱先進先出隊列;如果刪除按元素的優(yōu)先級來刪除的隊列稱優(yōu)先隊列.這兩種隊列應用較廣泛,討論較多[6-7].上述問題中的操作是在前面刪除,后面插入;求解過程中的逆操作是在下面插入,上面刪除.因而求解類Josephus逆問題及驗證解需要隊列的兩端都能插入和刪除,這種隊列叫雙端隊列.我們將基于雙端隊列的存儲,討論類Josephus逆問題的計算機求解及解的驗證.

2 雙端隊列

圖1 雙端隊列

圖2 鐵道轉軌網(wǎng)

雙端隊列是限定插入和刪除操作在表的兩端進行的線性表,示意圖見圖1,也可用圖2的鐵道轉軌網(wǎng)絡形象描述雙端隊列.本節(jié)中首先給出雙端隊列的抽象數(shù)據(jù)類型定義,然后討論雙端隊列的順序循環(huán)實現(xiàn).

線性表是多個相同類型的數(shù)據(jù)元素的集合,且這些元素間具有線性關系.雙端隊列是只能在兩端進行插入和刪除的線性表,常用的基本操作有插入、刪除、判斷隊列是否為空、判斷隊列是否滿等.由于具體應用中的隊列兩端操作的限制不一樣,它的定義和實現(xiàn)略有區(qū)別.文獻[8-9]中的雙端隊列是基于先進先出隊列及先進后出棧實現(xiàn)的.下面給出隊列兩端都能進行插入和刪除的抽象數(shù)據(jù)類型雙端隊列的定義.

ADT DEQueue{

數(shù)據(jù)對象:D={ai| ai∈ElemSet, i=1, 2, …, n, n≥0}.

數(shù)據(jù)關系:R={| ai∈ D , i=2, …, n}約定a1為端1元素,an為端2元素.

基本操作:

InitDEQueue(&Q); //構造一個空雙端隊列

ClearDEQueue(&Q); //雙端隊列Q存在,清空它

DEQueueEmpty(Q); //雙端隊列Q存在,判斷它是否為空

DEQueueFull(Q); //雙端隊列Q存在,判斷它是否滿

EnDEQueue1(&Q, e); //雙端隊列Q存在,在端1插入元素e

EnDEQueue2(&Q, e); //雙端隊列Q存在,在端2插入元素e

DeDEQueue1(&Q, &e); //雙端隊列Q存在,刪除端1元素,用e返回其值

DeDEQueue2(&Q, &e); //雙端隊列Q存在,刪除端2元素,用e返回其值

Get1(Q, &e); //雙端隊列Q存在,用e返回端1元素的值

Get2(Q, &e); //雙端隊列Q存在,用e返回端2元素的值

OutputDEQueue(Q); //依次輸出雙端隊列中從端1到端2的元素

} ADT DEQueue

雙端隊列的實現(xiàn)一般可分為鏈式和順序兩大類.文獻[10]中的雙端隊列是基于雙鏈表的實現(xiàn).由于隊列操作只在兩端,如果能預估數(shù)據(jù)元素個數(shù)的最大值,用順序存儲可以簡化操作,本文中實現(xiàn)的方式是順序方式.雙端隊列的順序存儲是用一組地址連續(xù)的存儲單元依次存放從端1到端2的元素,同時附設兩個指針end1和end2分別指示端1元素和端2元素的位置.由于隊列兩端可隨時插入、刪除元素,end1和end2會動態(tài)變化,為提高存儲率,元素的存儲空間可當成環(huán)形空間使用,即最后一個單元的下一個存儲單元是第一個單元,此時隊列稱為順序循環(huán)雙端隊列.我們約定:初始化隊列時,申請一個QUEUE_MAX_SIZE(足夠用)大小的空間,end1=end2=0;每當在端1插入、刪除元素,end1對應減1、增1;每當在端2插入、刪除元素,end2對應增1、減1.因此,當雙端隊列非空時,end1總是指向端1元素,end2總是指向端2元素的下一個位置.為了區(qū)分隊空隊、隊滿,本文中還約定存儲空間要空一個單元不用.這樣,當end1= =end2時,雙端隊列為空;當(end2+1) = =end1,雙端隊列為滿.這里的增、減是基于模QUEUE_MAX_SIZE意義上的.假設雙端隊列數(shù)據(jù)元素的類型為ElemType,下面給出順序循環(huán)雙端隊列的存儲結構:

const QUEUE_MAX_SIZE=100; //存儲空間的大小

typedef struct {

ElemType *base; //元素存放首地址

int end1, end2; //指示隊列的兩端

} DESQueue; //順序循環(huán)雙端隊列

typedef DESQueue DEQueue;

抽象數(shù)據(jù)類型雙端隊列定義中的相關操作的實現(xiàn),見附錄.

3 問題的求解、驗證及算法分析

約定第2節(jié)定義中的數(shù)據(jù)用順序循環(huán)隊列存儲,前面為端1,后面為端2.求解類Josephus逆問題的基本思想是借助一個空雙端隊列,用類Josephus逆問題中的元素的出隊序列按逆序進行如下操作:首先重復進行后兩種操作,1)從端1順序插入s個數(shù)據(jù),2)m次將1個數(shù)據(jù)從端2移至端1,最后進行k次1個數(shù)據(jù)從端2移至端1操作.操作結束,雙端隊列從端1到端2的數(shù)據(jù)就是n個數(shù)據(jù)的原始序列,即為類Josephus逆問題的解.利用雙端隊列將此原始序列進行規(guī)定的操作可得到出隊序列,從而模擬和驗證.注意到數(shù)據(jù)元素一共有n個,端1連續(xù)刪除元素s次,當s不整除n時,則最后一次只能連續(xù)刪除n(mods)次.因此,求解過程中操作的第一次從端1插入及演示操作時的最后一次從端1刪除要單獨處理.下面是分別是求解類Josephus逆問題及類Josephus問題的算法.

3.1算法1void ProblemSolving(ElemType A[ ], int n, int m, int k, int s){

// A存放n份數(shù)據(jù)(按出隊順序的逆序),進行類Josephus問題中的逆操作,輸出初始序列

InitDEQueue (Q) //初始化雙端隊列Q

p=0;

//處理特殊的第一組

if(n%s){

for(i=1; i<=n%s; i++)EnDEQueue1(Q, A[p++]); //數(shù)據(jù)依次從端1插入

for(j=1; j<=m; j++){// 從端2刪除一元素,將該元素再從端1插入

DeDEQueue2(Q, temp); EnDEQueue1(Q, temp);

}

}//if

while(p

for(i=1; i<=s; i++) EnDEQueue1(Q, A[p++]);

for(j=1; j<=m; j++){

DeDEQueue2(Q, temp); EnDEQueue1(Q, temp);

}

}//_while

for(i=1; i<=k; i++){//

DeDEQueue2(Q, temp); EnDEQueue1(Q, temp);

}

OutputDEQueue(Q); //輸出隊列各元素,即類Josephus逆問題的解

}//end

3.2算法2void ProblemProving(DEQueue &Q, int n, int m, int k, int s){

//Q中存放類Josephus逆問題的解,進行規(guī)定的操作,輸出出隊序列

for(i=1; i<=k; i++){// 從端1刪除一元素,將該元素再從端2插入

DeDEQueue1(Q, temp); EnDEQueue2(Q, temp);

}

for(i=1; i<=n/s; i++){

for(j=1; j<=m; j++){

DeDEQueue1(Q, temp); EnDEQueue2(Q, temp);

}

for(j=1; j<=s; i++){// 從端1刪除元素

DeDEQueue1(Q, temp); cout<

}

}//_for

// 處理最后一組數(shù)據(jù)

if(n%s){

for(j=1; j<=m; j++){

DeDEQueue1(Q, temp); EnDEQueue2(Q, temp);

}

while(!DEQueueEmpty(Q)){

DeDEQueue1(Q, temp); cout<

}

}//if

}//_end

利用算法1,可求得例1中撲克牌的原始順序從上至下應依次為7、A、Q、2、8、3、J、4、9、5、K、6、10;例2中Josephus和他的朋友的原始號碼為31和16;例3中撲克牌的原始順序從上至下應依次為5、8、A、A、9、6、2、3、7、10、3、4、9、7、5.利用算法2很容易驗證它們的正確性.

下面簡單地分析上述兩個算法的效率.兩個算法中主要的存儲空間是一個隊列,隊列的大小為元素的個數(shù),所以空間復雜性為Ο(n).兩個算法中的主要操作是元素進隊、出隊,操作總次數(shù)相等,用T(n,m,k,s)表示算法1、算法2中進隊、出隊總的操作次數(shù),即時間復雜性.由上述算法易知,

4 結論

本文中定義了類Josephus逆問題,探討了這類問題的求解.實驗表明:雙端隊列是求解類Josephus逆問題及驗證解的正確性的一種很好的數(shù)據(jù)存儲結構.下一階段的工作將探討算法的改進及類Josephus逆問題的應用.

5 附錄:雙端隊列的順序循環(huán)實現(xiàn)

下面給出與本文中有關的雙端隊列順序循環(huán)實現(xiàn)算法,包括雙端隊列的初始化、兩個出隊、兩個入隊及一個輸出算法.

int InitDEQueue(DEQueue Q){

Q.base= new ElemType[QUEUE_MAX_SIZE];

if(!Q.base)return 0; // 空間不夠,返回失敗標志

Q.endl=Q.end2=0;//end1和end2都指示起始位置

return 1; //成功

}

int EnDEQueue1(DEQueue &Q, ElemType e){//從端1入隊

if(DEQueueFull(Q)) return 0; //空間不夠,失敗

Q.end1=(Q.end1+QUEUE_MAX_SIZE-1)%QUEUE_MAX_SIZE;

Q.base[Q.end1]=e;

return 1;

}

int EnDEQueue2(DEQueue &Q, ElemType e){//從端2入隊

if(DEQueueFull(Q)) return 0; //空間不夠,失敗

Q.base[Q.end2]=e;

Q.end2=(Q.end2+1)% QUEUE_MAX_SIZE;

return 1;

}

int DeDEQueue1(DEQueue &Q, ElemType &e){//從端1出隊

if(DEQueueEmpty(Q)) return 0;//空隊列,失敗

e=Q.base[Q.end1];

Q.end1=(Q.end1+1)%QUEUE_MAX_SIZE;

return 1;

}

int DeDEQueue2(DEQueue &Q, ElemType &e){//從端2出隊

if(DEQueueEmpty(Q)) return 0;//空隊列,失敗

Q.end2=(Q.end2+QUEUE_MAX_SIZE-1)%QUEUE_MAX_SIZE;

e=Q.base[Q.end2];

return 1;

}

void OutputDEQueue(DEQueue Q){ //輸出隊列元素,約定從隊頭到隊尾

if(DEQueueEmpty(Q)) {cout<<″空隊列?。。　? return;}

i=Q.end1;

do{

cout<

i=(i+1)% QUEUE_MAX_SIZE;

}while(i!=Q.end2);

}

[1] Graham R L, Knuth D E, Patashnik O.具體數(shù)學[M].莊心谷,譯.西安:西安電子科技大學出版社,1992.

[2] Gregory L W, Christopher L M. An application of Fourier transforms on finite Abelian groups to an enumeration arising from the Josephus problem[J]. Journal of Number Theory,2010,130:815-827.

[3] Ruskey F, Williams A. The feline josephus problem[J]. Theory Comput Syst,2012,50:20-34.

[4] 王永紅.約瑟夫環(huán)經(jīng)典問題的幾種算法比較[J].現(xiàn)代計算機,2008,(1):36-37.

[5] 陳海山,錢鋒,田英,等.Josephus問題的算法設計與應用研究[J].計算機工程與應用,2007,43(1):61-64.

[6] 嚴蔚敏,吳偉民.數(shù)據(jù)結構[M].北京:清華大學出版社,2002.

[7] 王曉東.計算機算法設計與分析[M].第3版.北京:電子工業(yè)出版社,2007.

[8] 陳佳娟,王云鵬,紀壽文.配送實時調(diào)度管理系統(tǒng)中最短路徑的雙隊列算法及其JAVA實現(xiàn)[J].計算機工程與應用,2004,33:227-229,232.

[9] 陳潔,陸鋒.一種基于雙端隊列的交通網(wǎng)絡最短路徑Pallottino優(yōu)化算法[J].中國圖象圖形學報,2006,11(3):419-424

[10] 楊東升,張連法.改進型鎖無關雙端隊列的設計與實現(xiàn)[J].計算機系統(tǒng)應用,2012,21(3):125-129.