劉薇，陳文

（福州職業(yè)技術(shù)學(xué)院，福州 350108）

1 約瑟夫問(wèn)題

約瑟夫問(wèn)題是計(jì)算機(jī)算法中的經(jīng)典問(wèn)題，對(duì)約瑟夫問(wèn)題的研究由來(lái)已久[1]，對(duì)約瑟夫問(wèn)題的算法分析對(duì)于計(jì)算機(jī)程序設(shè)計(jì)的教學(xué)具有重要的作用[2]。約瑟夫問(wèn)題的描述方式有多種形式[3]，但其本質(zhì)是一樣的。以下對(duì)約瑟夫問(wèn)題給出一種描述方式：編號(hào)為1到n的n個(gè)人，按編號(hào)順序圍成一圈，即初始狀態(tài)時(shí)，第n個(gè)的下一個(gè)為第1個(gè)。從1開(kāi)始往后報(bào)數(shù)，報(bào)到k的倍數(shù)的人離開(kāi)。如此繼續(xù)，直到只剩最后一人為止。問(wèn)最后留下的是n個(gè)人中的哪一個(gè)。

對(duì)于約瑟夫問(wèn)題，最直觀和最常用的方法便是順序存儲(chǔ)的數(shù)組標(biāo)記法和利用循環(huán)鏈表的結(jié)點(diǎn)刪除法。本文著重介紹除此之外的約瑟夫問(wèn)題的其他解法，包括順推法、逆推法、遞歸法等，進(jìn)一步拓展解決問(wèn)題的思路。并對(duì)各種方法進(jìn)行分析對(duì)比，提高程序設(shè)計(jì)能力。

2 約瑟夫問(wèn)題的解決方法

2.1 數(shù)組標(biāo)記法

數(shù)組標(biāo)記法是較為直觀的一種算法[4]。它的基本思想就是直接用數(shù)組data[1],data[2],…,data[n]標(biāo)記n個(gè)人的狀態(tài)，值為1時(shí)，表示該元素已出局。初始狀態(tài)data[1],data[2],…,data[n]的值均為0。當(dāng)前編號(hào)current=0。從當(dāng)前位置往后找非1元素。找k次后，將當(dāng)前位置的數(shù)組值置為1。如此重n-1次，則，數(shù)組中值為0的下標(biāo)編號(hào)即為所求。算法如下：

（1）從當(dāng)前位置 current處尋找下一個(gè)值為 0位置。

int nextZero（int data[],int n,int current）{

current=current%n+1;//后移一位

while（data[current]!=0）

current=current%n+1;

return current;

}

（2）求解約瑟夫問(wèn)題的主程序?yàn)椋篿nt main（）{

定義變量，輸入n，k;

初始數(shù)組data[1]---data[n];

current=0;

for（kill=1;kill

{

for（i=1;i<=k;i++） //報(bào) k 次

current=nextZero（data,n,current）;

data[current]=1;//當(dāng)前位置出局

}

for（i=1;i<=n;i++）{

if（data[i]==0）{輸出i;break;}

//查找數(shù)據(jù)值為0的數(shù)組下標(biāo)

}

}

2.2 鏈?zhǔn)讲檎曳?/h3>

利用循環(huán)鏈表的方法解決約瑟夫問(wèn)題，也是較為常用的方法之一。有學(xué)者對(duì)此算法的優(yōu)劣做了較為詳細(xì)的分析[5]，也有學(xué)者利用不同的程序設(shè)計(jì)語(yǔ)言進(jìn)行相應(yīng)的描述。本文利用《C語(yǔ)言程序設(shè)計(jì)》給出算法的描述。它的基本思想是：建立如下循環(huán)鏈表。

圖1 循環(huán)鏈表示意圖

當(dāng)前位置current初始狀態(tài)時(shí)為head，則算法描述為：當(dāng)前位置current往后移k-1次后，將current的下一個(gè)元素刪除。如此重復(fù)n-1次，則current的值即為所求。

（1）結(jié)點(diǎn)結(jié)構(gòu)：struct node

{

int data;

struct node*next; //下一結(jié)點(diǎn)的地址

};

typedef struct node Llist;

（2）鏈表創(chuàng)建

Llist*creat（int n）{

Llist*head,*rear,*t;

head=（Llist*）malloc（sizeof（node））;

head->data=n;

rear=head;

int i;

for（i=1;i<=n-1;i++）{

t=（Llist*）malloc（sizeof（node））;

t->data=i;

rear->next=t;

rear=t;

}

rear->next=head;

return head;

}

求解約瑟夫問(wèn)題的主程序?yàn)椋篿nt main（）{

定義參數(shù)，輸入n,k

Llist*h,*t;

h=creat（n）;//創(chuàng)建初始鏈

for（kill=1;kill

for（i=1;i

h=h->next;

t=h->next;//t為第k個(gè)元素位置h->next=t->next;

free（t）;//將第 k 個(gè)元素刪除}

printf（"i=%d ",h->data）;

2.3 順推法

對(duì)于約瑟夫問(wèn)題，從1開(kāi)始往后報(bào)數(shù)。顯然，當(dāng)報(bào)數(shù)報(bào)到（n-1）*k時(shí)，必然有n-1個(gè)人離開(kāi)，所以，最后一人報(bào)數(shù)必然是（n-1）*k+1。因此，約瑟夫問(wèn)題可以描述為：編號(hào)為1到n的n個(gè)人，按順序圍成一圈，從1往后開(kāi)始報(bào)數(shù)，報(bào)k的倍數(shù)的人離開(kāi)。問(wèn)：最后報(bào)數(shù)為（n-1）*k+1的是哪一個(gè)。

順推法的基本思想是，從1到n逐個(gè)分析當(dāng)前報(bào)數(shù)為m時(shí)，最后一次報(bào)數(shù)能否達(dá)到（n-1）*k+1。分析如下：

（1）當(dāng)m為k的倍數(shù)時(shí)，m即為最后一次報(bào)數(shù)。

（2）當(dāng)m不為k的位數(shù)時(shí)，此時(shí)，必有m/k個(gè)人不參與報(bào)數(shù)，即參數(shù)報(bào)數(shù)的人數(shù)為n-m/k個(gè)。所以，下輪的報(bào)數(shù)必然是m+（n-m/k）。于是，當(dāng)前報(bào)數(shù)為m,求最后一次所報(bào)數(shù)的算法如下：

int lastNum（int n,int k,int m）{

while（m%k!=0&&m<（n-1）*k+1）

m=m+n-m/k;

return m;

}

求解約瑟夫問(wèn)題的主程序?yàn)椋?/p>

int main（）{

定義變量，輸入n，k

}

for（i=1;i<=n;i++） //逐個(gè)判斷最后一個(gè)報(bào)數(shù)能否達(dá)到（n-1）*k+1

if（lastNum（n,k,i）>=（n-1）*k+1）

{

輸出i，程序結(jié)束

}

}

2.4 倒推法

約瑟夫問(wèn)題，可歸結(jié)為n個(gè)人，從1開(kāi)始順序報(bào)數(shù)，每報(bào)k的倍數(shù)的離開(kāi)，問(wèn)哪個(gè)數(shù)報(bào)到（n-1）*k+1。倒推法的基本思想是：從（n-1）*k+1倒推到上一輪的報(bào)數(shù)值，繼續(xù)倒推到上一輪的報(bào)數(shù)值，直到報(bào)數(shù)值在1到n的范圍中。

核心問(wèn)題：當(dāng)前報(bào)數(shù)為m，問(wèn)上一輪的報(bào)數(shù)為多少解法一：設(shè)上輪報(bào)數(shù)為x,顯然，x不為k的倍數(shù)，可將x表示為：

此時(shí)，已有p個(gè)人不參與報(bào)數(shù)。所以，

將式（1）代入式（2）可得：

m=p*k+r+n-p，進(jìn)一步可化為：

m-n-1=p*（k-1）+（r-1），其中：r-1:0…（k-2）

于是：p=（m-n-1）/（k-1）;

r=（m-n-1）%（k-1）+1

所以，當(dāng)前報(bào)數(shù)為m，求上輪報(bào)數(shù)值的算法如下：int preNum（int n,int k,int m）{

int x,p,r;

p=（m-n-1）/（k-1）;

r=（m-n-1）%（k-1）+1;

x=p*k+r;

return x;

}

求解約瑟夫問(wèn)題的主程序?yàn)椋?/p>

int main（）{

定義變量，輸入n，k

num=（n-1）*k+1;

while（num>n）

num=preNum（n,k,num）;

輸出num

}

解法二：由式（2）得：

2.5 遞歸法

遞歸法的基本思想是將n個(gè)人的約瑟夫問(wèn)題轉(zhuǎn)化為n-1個(gè)人的約瑟夫問(wèn)題。將n個(gè)人圍成一圈，從1開(kāi)始報(bào)數(shù)，報(bào)k的倍數(shù)的人出局的約瑟夫問(wèn)題記為f（n,k）。遞歸法的基本思想便是尋找f（n,k）與f（n-1,k）之間的關(guān)系。核心問(wèn)題是：n>1時(shí)，已知f（n-1,k）=m求f（n,k）。

對(duì)f（n,k）的求解分析如下，第一個(gè)出局的編號(hào)記為a1。

（1）當(dāng)n>=k時(shí)，a1=k。a1出局后，剩余的n-1個(gè)便形成了n-1個(gè)的約瑟夫問(wèn)題。由于f（n-1,k）=m，所以，f（n,k）的解應(yīng)該是a1往后m個(gè)。由于a1+m的值可能大于n，所以，必須將a1+m通過(guò)取余運(yùn)算轉(zhuǎn)化為1到n的范圍。

于是：f（n,k）=（a1+m-1）%n+1，即：f（n,k）=（k+m-1）%n+1。

（2）當(dāng) n

f（n,k）=（a1+m-1）%n+1=（（k-1）%n+m）%n+1

即：f（n,k）=（k+m-1）%n+1;

綜上可得：無(wú)論n與k的大小關(guān)系如何，均有f（n,k）=（k+m-1）%n+1。

也就是,當(dāng)n>1時(shí)，f（n,k）=（k+f（n-1,k）-1）%n+1;

遞歸法算法如下：

int f（int n,int k）{

if（n==1）return 1;

else

return（k+f（n-1,k）-1）%n+1;

}

求解約瑟夫問(wèn)題的主程序?yàn)椋?/p>

int main（）{

輸入 n，k;

p=n-m+x，代入式（1）得：

x=（n-m+x）*k+r，展開(kāi)得：

x=n*k-m*k+k*x+r

m*k-n*k-1=x*（k-1）+（r-1）

x=（m*k-n*k-1）/（k-1）

于是算法描述為：

int preNum（int n,int k,int m）{

return（m*k-n*k-1）/（k-1）;

}

輸出f（n,k）;

}

3 約瑟夫問(wèn)題解決方法對(duì)比

數(shù)組標(biāo)記法直觀易懂，但運(yùn)行效率低。利用鏈?zhǔn)浇Y(jié)構(gòu)的查找與刪除，在運(yùn)行時(shí)間上略有改進(jìn)。但未有實(shí)質(zhì)性的改進(jìn)與突破。遞歸法雖然代碼簡(jiǎn)單，但其運(yùn)行機(jī)理是借助于棧的存儲(chǔ)，運(yùn)行時(shí)所占用的內(nèi)存資源卻是巨大的。而遞推法尤其倒推法則是解決約瑟夫問(wèn)題較為有效的方法。表1是約瑟夫問(wèn)題不同方法的運(yùn)行時(shí)間對(duì)比（k值取999）。從表1中可以看出。倒推法效率最高。數(shù)組標(biāo)記法效率最低。

表1 約瑟夫問(wèn)題算法運(yùn)行時(shí)間對(duì)比（單位：毫秒）

4 結(jié)語(yǔ)

約瑟夫問(wèn)題是計(jì)算機(jī)算法設(shè)計(jì)中的經(jīng)典問(wèn)題，是訓(xùn)練編程能力較為理想的案例。對(duì)約瑟夫問(wèn)題的歸納總結(jié)有助于強(qiáng)化對(duì)各種算法的理解，提高算法的應(yīng)用能力。