趙天玉，王安平 (長江大學信息與數(shù)學學院，湖北 荊州 434023)

嚴 政 長江大學信息與數(shù)學學院，湖北 荊州 434023 應用數(shù)學湖北省重點實驗室(湖北大學)，湖北 武漢 430062

含多個參數(shù)的Josephus問題遞歸關(guān)系研究

趙天玉，王安平 (長江大學信息與數(shù)學學院，湖北 荊州 434023)

嚴 政 長江大學信息與數(shù)學學院，湖北 荊州 434023 應用數(shù)學湖北省重點實驗室(湖北大學)，湖北 武漢 430062

Josephus問題是一個古老的問題，對Josephus問題進行變形，可以得到一類遞歸關(guān)系。對這類遞歸關(guān)系進行了推廣，得到一類含多個參數(shù)的遞歸關(guān)系模型，討論了這類遞歸關(guān)系模型的求解方法，并采用d-進制記數(shù)法給出了這類遞歸關(guān)系模型的解。

Josephus問題；遞歸關(guān)系；模型；d-進制記數(shù)法

1 Josephus問題

Josephus問題[1]是一個古老的問題，在組合數(shù)學、題庫組卷及數(shù)列生成[2,3]中都涉及此問題。它是以1世紀著名歷史學家Flavius Josephus命名的。據(jù)傳說，在猶太人和古羅馬人戰(zhàn)爭期間，Josephus是陷入羅馬人陷阱的41個猶太反抗者之一。反抗者寧死不做俘虜，他們決定圍成一個圓圈，且環(huán)繞圓圈來進行，殺死所有第3個剩下的人，直到最后一個人自殺為止。但是Josephus和一個不告發(fā)的同謀者感到自殺是愚蠢的行為，所以他以自己的數(shù)學才能，快速計算出在此惡性循環(huán)中他和他的朋友該站的地方，活著逃出了陷阱。若Josephus是最后一位幸存者，他應該站的地方編號J(41)是多少？

文獻[2]給出了一般的Josephus問題及其算法，文獻[3]對幾種求解此問題的算法進行了比較，文獻[1]對Josephus問題進行了變形，從圍著一個圓的編號為1到n的n個人開始，排除所有第2個剩下的人，直到最后僅僅剩下1個幸存者為止，得到下列遞歸關(guān)系模型：

J(1)=1J(2n)=2J(n)-1(n≥1)J(2n+1)=2J(n)+1(n≥1)

(1)

并給出了模型(1)的解。若自然數(shù)n用二進制表示為n=(bm,bm-1,…,b1,b0)2，這里bm=1，則：

J(n)=J((bm,bm-1,…,b1,b0)2)=(bm-1,bm-2,b1,b0,bm)2

下面，筆者對遞歸關(guān)系模型(1)進行了推廣，得到一類含多個參數(shù)的遞歸關(guān)系，并討論了這類遞歸關(guān)系的求解方法*應用數(shù)學湖北省重點實驗室開放基金資助項目。。

2 Josephus問題遞歸關(guān)系的推廣

對Josephus問題進行變形所得模型(1)進行推廣，得到一般遞歸關(guān)系模型：

J(j)=αj(1≤jlt;d)

(2)

J(dn+j)=cJ(n)+γjn+βj(0≤jlt;d,n≥1)

(3)

式中，c,d,αj(j=1,2,…,d-1),βj,γj(j=0,1,…,d-1)都是常數(shù)，其中c,d是正整數(shù)，且c≥1,d≥2。

3 含多個參數(shù)的遞推關(guān)系的求解

傳統(tǒng)的求解遞歸關(guān)系的方法是特征根法[4]、母函數(shù)法與差分法[5]、迭代法與歸納法[6]。但針對遞歸關(guān)系模型的特殊性，筆者采用數(shù)的廣義d進制表示方法求解模型。

設：

n=(bm,bm-1,…,b1,b0)d=bmdm+bm-1dm-1+…+b1d+b0bm≠0

稱為n的廣義d進制表示。特別地，當0≤bilt;d(i=0,1,2,…,m)時，實際上就是n的d進制表示。

利用n的d進制表示遞歸模型式(2)、式(3)可得：

=cmαbm+cm-1βbm-1+cm-2βbm-2+…+cβb1+βb0+cm-1γbm-1(bmd0)+cm-2γbm-2(bmd+bm-1d0)

+…+cγb1(bmdm-2+bm-1dm-3+…+b2d0)+γb0(bmdm-1+bm-1dm-2+…+b1d0)

即:

(5)

下面對參數(shù)取值的情況進行討論。

(Ⅰ)當βj=γj=0(j=0,1,…,d-1)時，從式(4)可知遞歸模型的解為：

(Ⅱ)當γj=0(j=0,1,…,d-1)時，從式(4)可知遞歸模型的解為：

(Ⅳ)當c=d,γj=γ≠0(j=0,1,…,d-1)時，從式(5)可知遞歸模型的解為：

(Ⅴ)當c≠d,γj=γ≠0(j=0,1,…,d-1)時，從式(5)可知遞歸模型的解為：

(Ⅵ) 一般情況。采用(Ⅲ)的記號，從式(5)可知遞歸模型的解為：

J(n) =J((bm,bm-1,…,b1,b0)d)

4 解的另一種表示方法

設:

其中，n=(bm,bm-1,…,b1,b0)d(其中bm≠0)是n的d進制表示。那么系數(shù)Ai(n)(i=1,2,…,d-1)和Bi(n),Ci(n)(i=0,1,…,d-1)的表達式如何？

很顯然，從式(5)可知，當i≠bm時，Ai(n)=0；Abm(n)=cm。

即：

故：

J(n) =J((bm,bm-1,…,b1,b0)d)

[1]格雷厄姆 R L，克努特 D E，帕塔希尼克 O.具體數(shù)學[M].莊心谷 譯.西安：西安電子科技大學出版社，1992.7～14.

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

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

[4]盧開澄，盧華明.組合數(shù)學[M].第3版.北京：清華大學出版社，2002.126～150.

[5]楊振生.組合數(shù)學及其算法[M].合肥：中國科學技術(shù)大學出版社，1997.106～135.

[6]孫世新，張先迪.組合原理及其應用[M].北京：國防工業(yè)出版社，2006.157～161.

[編輯] 洪云飛

O157

A

1673-1409(2009)02-N001-03

2009-02-12

趙天玉(1958-)，男，1981年大學畢業(yè)，碩士，教授，現(xiàn)主要從事組合數(shù)學方面的教學與研究工作。