說(shuō)在前面

(資料圖)

約瑟夫問(wèn)題是一個(gè)經(jīng)典的數(shù)學(xué)應(yīng)用問(wèn)題，它通過(guò)循環(huán)報(bào)數(shù)不斷刪除序列中的元素，直至剩下1個(gè)（或多個(gè)）人為止。編程解決約瑟夫問(wèn)題的算法很多，基本思想都是模擬報(bào)數(shù)過(guò)程，區(qū)別在于數(shù)據(jù)結(jié)構(gòu)不同，刪除元素的方法也不一樣。

約瑟夫問(wèn)題可以考查使用模運(yùn)算實(shí)現(xiàn)循環(huán)報(bào)數(shù)功能，使用循環(huán)鏈表、循環(huán)隊(duì)列等數(shù)據(jù)結(jié)構(gòu)模擬報(bào)數(shù)和刪除元素過(guò)程，變例繁多、算法難度較高、綜合性強(qiáng)，是需要重點(diǎn)掌握的經(jīng)典案例。

教材文本

教材處理教材2.2.1例2“約瑟夫問(wèn)題”采用循環(huán)單鏈表來(lái)存儲(chǔ)數(shù)據(jù)，節(jié)點(diǎn)數(shù)據(jù)域?yàn)閰⑴c人員的編號(hào)。通過(guò)遍歷鏈表來(lái)模擬報(bào)數(shù)過(guò)程，并刪除節(jié)點(diǎn)以實(shí)現(xiàn)淘汰人員功能，直至只剩一個(gè)節(jié)點(diǎn)為止。總體來(lái)說(shuō)，例2程序邏輯清晰，可讀性強(qiáng)，學(xué)生容易理解。但我們不應(yīng)該滿足于單一解法，可在理解例題的基礎(chǔ)上，拓展思考程序改進(jìn)方案和采用不同數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)算法功能。學(xué)生任務(wù)單閱讀教材P49例2“約瑟夫問(wèn)題”，思考如下問(wèn)題：（1）書(shū)中程序節(jié)點(diǎn)的數(shù)據(jù)域和指針域分別存儲(chǔ)了什么內(nèi)容？它是如何構(gòu)造循環(huán)單鏈表的？（2）書(shū)中程序設(shè)置了多個(gè)指向節(jié)點(diǎn)的指針變量，例如head,k和t，它們分別指向哪些節(jié)點(diǎn)？（3）書(shū)中程序是如何實(shí)現(xiàn)刪除節(jié)點(diǎn)功能的？（4）書(shū)中程序使用變量long來(lái)記錄鏈表長(zhǎng)度，并用long>1作為循環(huán)條件，這樣做是必需的吧？能否去除變量long，使用其他方法來(lái)判斷循環(huán)鏈表長(zhǎng)度是否為1？（5）下列程序也能解決約瑟夫問(wèn)題，試比較其與教材程序的異同，并完成填空。

n=int(input("請(qǐng)輸入?yún)⑴c人數(shù)（N）："))

m=int(input("請(qǐng)輸入淘汰數(shù)（M）："))

a = [[i+1,i+1] for i in range(n-1)]

a.append(填空1) # 最后一個(gè)人的下一位是第一個(gè)人

pre = len(a) - 1 # 指向前驅(qū)節(jié)點(diǎn)

while 填空2: # 循環(huán)單鏈表中節(jié)點(diǎn)數(shù)量大于1

for i in range(1, m): # 報(bào)數(shù)[1,m-1]的人留下

pre = 填空3

a[pre][1] = 填空4 # 報(bào)數(shù)m的人離開(kāi)（刪除a[pre][1]）

print(f"幸存者位置為：{a[pre][0]}")

問(wèn)題解析（1）書(shū)中程序節(jié)點(diǎn)的數(shù)據(jù)域存儲(chǔ)的是參與人員的初始編號(hào)，指針域存儲(chǔ)的是后繼節(jié)點(diǎn)的位置（在列表llist中的下標(biāo)）。程序通過(guò)將尾節(jié)點(diǎn)的指針指向頭節(jié)點(diǎn)，構(gòu)成循環(huán)單鏈表。（2）head指向單鏈表的頭節(jié)點(diǎn)；k用來(lái)遍歷鏈表，它指向當(dāng)前節(jié)點(diǎn)；t用來(lái)指向k的后繼節(jié)點(diǎn)，即被刪除的節(jié)點(diǎn)，它只在刪除節(jié)點(diǎn)時(shí)出現(xiàn)。（3）書(shū)中程序使用如下代碼實(shí)現(xiàn)刪除節(jié)點(diǎn)功能：

if i==m: # 報(bào)數(shù)為m時(shí)刪除k的后繼節(jié)點(diǎn)t

t=a[k][1] # 用t指向節(jié)點(diǎn)k的后繼節(jié)點(diǎn)

a[k][1]=a[t][1] # 修改k的后繼指針，以實(shí)現(xiàn)刪除節(jié)點(diǎn)t功能

if t==head: # 刪除頭節(jié)點(diǎn)時(shí)需要修改頭指針

head=a[k][1] # 或者h(yuǎn)ead=a[t][1]

i=1 # 計(jì)數(shù)器歸1

long-=1 # 鏈表長(zhǎng)度減1

程序通過(guò)修改k的后繼指針，實(shí)現(xiàn)刪除其后繼節(jié)點(diǎn)的功能。為了增強(qiáng)代碼的可讀性，程序設(shè)置變量t指向節(jié)點(diǎn)k的后繼節(jié)點(diǎn)，然后修改a[k][1]=a[t][1]，這樣就能實(shí)現(xiàn)刪除節(jié)點(diǎn)t的功能了。為了使head始終指向鏈表的頭節(jié)點(diǎn)，當(dāng)被刪除節(jié)點(diǎn)是頭節(jié)點(diǎn)時(shí)需要修改頭指針head。

刪除某個(gè)節(jié)點(diǎn)后，程序讓計(jì)數(shù)器i歸1，并使記錄鏈表長(zhǎng)度的變量long減1，準(zhǔn)備下一輪報(bào)數(shù)。

（4）書(shū)中程序使用變量long來(lái)記錄鏈表長(zhǎng)度，這不是必需的。可以利用循環(huán)鏈表自身特征來(lái)判斷其長(zhǎng)度是否為1。若t指向當(dāng)前節(jié)點(diǎn)，則當(dāng)a[t][1] == t時(shí)，表示鏈表長(zhǎng)度為1。（5）如下程序直接使用pre指向報(bào)數(shù)人員的前驅(qū)節(jié)點(diǎn)，通過(guò)語(yǔ)句a[pre][1] = a[a[pre][1]][1]，可實(shí)現(xiàn)刪除節(jié)點(diǎn)a[pre][1]的功能；把while循環(huán)條件改成a[pre][1]!= pre，可以判斷循環(huán)單鏈表中節(jié)點(diǎn)數(shù)量是否大于1。這種做法無(wú)需引入變量long，甚至無(wú)需引入頭指針head，代碼較為簡(jiǎn)明。

n=int(input("請(qǐng)輸入?yún)⑴c人數(shù)（N）："))

m=int(input("請(qǐng)輸入淘汰數(shù)（M）："))

a = [[i+1,i+1] for i in range(n-1)]

a.append([n, 0]) # 最后一個(gè)人的下一位是第一個(gè)人

pre = len(a) - 1 # 指向前驅(qū)節(jié)點(diǎn)

while a[pre][1] != pre: # 循環(huán)單鏈表中節(jié)點(diǎn)數(shù)量大于1

for i in range(1, m): # 報(bào)數(shù)[1,m-1]的人留下

pre = a[pre][1]

a[pre][1] = a[a[pre][1]][1] # 報(bào)數(shù)m的人離開(kāi)（刪除a[pre][1]）

print(f"幸存者位置為：{a[pre][0]}")

課后作業(yè)

教材程序通過(guò)遍歷鏈表來(lái)模擬報(bào)數(shù)過(guò)程，并刪除節(jié)點(diǎn)以實(shí)現(xiàn)淘汰人員功能，直至只剩一個(gè)節(jié)點(diǎn)為止。除此之外，你還能想到別的方法來(lái)解決約瑟夫問(wèn)題嗎？例如使用一維數(shù)組和循環(huán)隊(duì)列等數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)數(shù)據(jù)，又該如何編寫(xiě)代碼呢？

需要本文word文檔、源代碼和課后思考答案的，可以加入“Python算法之旅”知識(shí)星球參與討論和下載文件，“Python算法之旅”知識(shí)星球匯集了數(shù)量眾多的同好，更多有趣的話題在這里討論，更多有用的資料在這里分享。

我們專(zhuān)注Python算法，感興趣就一起來(lái)！

相關(guān)優(yōu)秀文章：

閱讀代碼和寫(xiě)更好的代碼

最有效的學(xué)習(xí)方式

Python算法之旅文章分類(lèi)

關(guān)鍵詞： 刪除節(jié)點(diǎn) 數(shù)據(jù)結(jié)構(gòu) 循環(huán)鏈表