“約瑟夫問(wèn)題”教學(xué)思路
說(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)典案例。
教材文本
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]}')
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ù)。
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]}')
教材程序通過(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)秀文章：