抽殺問(wèn)題約瑟夫問(wèn)題-wenkub
2023-04-09 02:32:05 本頁(yè)面
【正文】 這999個(gè)自然數(shù)按順時(shí)針的方向依次排列在一個(gè)圓圈上（如下圖）。先給大家介紹這一問(wèn)題的由來(lái)。 據(jù)說(shuō)著名猶太歷史學(xué)家 Josephus有過(guò)以下的故事：在羅馬人占領(lǐng)喬塔帕特後，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被人抓到，于是決定了一個(gè)自殺方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開(kāi)始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須自殺，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都自殺身亡為止。從1開(kāi)始按順時(shí)針的方向，保留1，擦去2；保留3，擦去4……這樣每隔一個(gè)數(shù)擦去一個(gè)數(shù)，轉(zhuǎn)圈擦下去。999=29+487，最后剩下的一個(gè)數(shù)是4872+1=975。本例中編號(hào)為1的學(xué)生離開(kāi)后還剩999人，此時(shí)，如果原來(lái)報(bào)2的全部改報(bào)1并留下，原來(lái)報(bào)1的全部改報(bào)2并離開(kāi)，那么，問(wèn)題就與上面這題完全一樣了。如果有（2n＋d）（1≤d＜2n）人，那么當(dāng)有d人退出圈子后還剩下2n人。再把原來(lái)的第三張卡片舍去，把下一張卡片放在最下面。列表如下： 設(shè)這一摞卡片的張數(shù)為N，觀察上表可知： ?。?）當(dāng)N=2a（a=0，1，2，3，…）時(shí)，剩下的這張卡片是原來(lái)那一摞卡片的最后一張，即第2a張； ?。?）當(dāng)N=2a+m（m＜2a）時(shí)，剩下的這張卡片是原來(lái)那一摞卡片的第2m張。再看一道經(jīng)變化的逆推題：例4：如下左圖,七枚棋子圍成一個(gè)圓圈,從①開(kāi)始,每隔一個(gè)取一個(gè),依次取走①、③、⑤、⑦、④、②,最后剩下⑥.二十枚棋子圍成一個(gè)圓圈(如右圖),從 開(kāi)始,每隔一個(gè)取一個(gè),最后將只剩下一枚棋子是⑥. ①③②④⑤⑥⑦①②③④⑤⑥⑦⑧⑨⑩⑾⑿⒀⒁⒂⒃⒄⒅⒆⒇實(shí)際上例就是抽殺問(wèn)題的“殺1留2類”，右圖可假設(shè)先從1開(kāi)始取起，那根據(jù)規(guī)律留下的為：（20－16）2
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1