抽殺問題約瑟夫問題-在線瀏覽
2025-05-12 02:32本頁面
【正文】 然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個(gè)與第31個(gè)位置，于是逃過了這場(chǎng)死亡游戲。小升初常見抽殺考題例舉：例1：把1～999這999個(gè)自然數(shù)按順時(shí)針的方向依次排列在一個(gè)圓圈上（如下圖）。問：最后剩下一個(gè)數(shù)時(shí)，剩下的是哪個(gè)數(shù)？ 馬到成功解析：可通過找規(guī)律得出，如果有2n個(gè)數(shù)，那么轉(zhuǎn)一圈擦去一半，剩下2n1個(gè)數(shù)，起始數(shù)還是1；再轉(zhuǎn)一圈擦去剩下的一半，又剩下2n2個(gè)數(shù)，起始數(shù)還是1……轉(zhuǎn)了n圈后，就剩下一個(gè)數(shù)是1。因?yàn)椴寥サ牡赿個(gè)數(shù)是2d，所以2d+1就是最后剩下的整數(shù)。例2：1000個(gè)學(xué)生坐成一圈，依次編號(hào)為1，2，3，…，1000。問：這個(gè)學(xué)生的編號(hào)是幾號(hào)？分析：這個(gè)問題與上面這題非常相似，只不過本例是報(bào)1的離開報(bào)2的留下，而上題相當(dāng)于報(bào)1的留下報(bào)2的離開，由上題的結(jié)果可以推出本例的答案。因?yàn)槭Ｏ?99人時(shí)，第1人是2號(hào)，所以最后剩下的人的號(hào)碼應(yīng)比上題大1，是975＋1=976（號(hào)）。解：如果有2n個(gè)人，那么報(bào)完第1圈后，剩下的是2的倍數(shù)號(hào)；報(bào)完第2圈后，剩下的是22的倍數(shù)號(hào)……報(bào)完第n圈后，剩下的是2n的倍數(shù)號(hào)，此時(shí)，只剩下一人，是2n號(hào)。因?yàn)橄乱粋€(gè)該退出去的是（2d＋1）號(hào)，所以此時(shí)的第（2d＋1）號(hào)相當(dāng)于2n人時(shí)的第1號(hào)，而2d號(hào)相當(dāng)于2n人時(shí)的第2n號(hào)，所以最后剩下的是第2d號(hào)。例3：有100張的一摞卡片，玲玲拿著它們，從最上面的一張開始按如下的順序進(jìn)行操作：把最上面的第一張卡片舍去，把下一張卡片放在這一摞卡片的最下面。反復(fù)這樣做，直到手中只剩下一張卡片，那么剩下的這張卡片是原來那一摞卡片的第幾張？分析與解：這100張卡片如果用線串起來，其實(shí)還是一個(gè)圍成一圈的約瑟夫問題。下面從簡(jiǎn)單的不失題目性質(zhì)的問題入手，尋找規(guī)律。取N=100，因?yàn)?00=26+36，236=72，所以剩下這張卡片是原來那一摞卡片的第72張。因此可對(duì)照：例1：為“留1”類，可用：（999－512）2＋1＝975
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1