抽殺問題約瑟夫問題(編輯修改稿)
2025-04-21 02:32 本頁面
【文章內(nèi)容簡介】 ）號，所以此時的第（2d＋1）號相當(dāng)于2n人時的第1號，而2d號相當(dāng)于2n人時的第2n號，所以最后剩下的是第2d號。由1000=29＋488知，最后剩下的學(xué)生的編號是4882=976（號）。例3：有100張的一摞卡片，玲玲拿著它們，從最上面的一張開始按如下的順序進(jìn)行操作：把最上面的第一張卡片舍去，把下一張卡片放在這一摞卡片的最下面。再把原來的第三張卡片舍去，把下一張卡片放在最下面。反復(fù)這樣做，直到手中只剩下一張卡片，那么剩下的這張卡片是原來那一摞卡片的第幾張？分析與解：這100張卡片如果用線串起來，其實還是一個圍成一圈的約瑟夫問題。如果上面幾題的解法看不太懂，可學(xué)學(xué)這題，從最簡單的情況開始找規(guī)律。下面從簡單的不失題目性質(zhì)的問題入手，尋找規(guī)律。列表如下： 設(shè)這一摞卡片的張數(shù)為N，觀察上表可知： ?。?）當(dāng)N=2a（a=0，1，2，3，…）時，剩下的這張卡片是原來那一摞卡片的最后一張，即第2a張； ?。?）當(dāng)N=2a+m（m＜2a）時，剩下的這張卡片是原來那一摞卡片的第2m張。取N=100，因為100=26+36，236=72，所以剩下這張卡片是原來那一摞卡片的第72張?？偨Y(jié)上題及例1例2：可歸納為兩種情況： 留1，殺2類：剩下號＝（總數(shù)－小于總數(shù)最大的2的次方數(shù)）2＋1 殺1，留2類：剩下號＝（總數(shù)－小于總數(shù)最大的2的次方數(shù)）2記住留1要加1，殺1不用加1，總發(fā)現(xiàn)有學(xué)生在這點上分辨不清。因此可對照：例1：為“留1”類，可用：（999－512）2＋1＝975例2：為“殺1”類，可用（1000－512）2＝976例3：為“殺1”類，可用（100－64）2＝72上面的512,64都是小于總數(shù)的最大的2的次方數(shù)。再看一道經(jīng)變化的逆推題：例4：如下左圖,七枚棋子圍成一個圓圈,從①開始,每隔一個取一個,依次取走①、③、⑤、⑦、④、②,最后剩下⑥.二十枚棋子圍成一個圓圈(如右圖),從 開始,每隔一個取一個,最后將只剩下一枚棋子
法律信息相關(guān)推薦
鄂ICP備17016276號-1