国产精品夜色视频一级区_hh99m福利毛片_国产一区二区成人久久免费影院_伊人久久大香线蕉综合影院75_国产精品久久果冻传媒

您的位置:首頁(yè) >聚焦 >

“約瑟夫問(wèn)題”教學(xué)思路_世界關(guān)注

2022-11-17 10:21:43    來(lái)源:程序員客棧

說(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)鏈表

相關(guān)閱讀