抽殺問題 約瑟夫問題

1、[閱讀材料]世界名題與小升初之：抽殺問題（抽殺問題（約瑟夫問題）約瑟夫問題）馬到成功老師在各類競賽中，各類小升初考試中相關(guān)的世界名題出現(xiàn)的概率極高，這是由小升初與數(shù)學(xué)競賽的特點決定，這特點便是：知識性，趣味性，思想性相結(jié)合。先給大家介紹這一問題的由來。先給大家介紹這一問題的由來。據(jù)說著名猶太歷史學(xué)家Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特後，39個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被

2、人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。解法解法約瑟夫問題可用代數(shù)分析來求解，將這個問題擴(kuò)大好了，假設(shè)現(xiàn)在您與m個朋友不幸參與了這個游戲，您要如何保護(hù)您的朋友？只要畫兩個圓圈就可

3、以讓自己與朋友免于死亡游戲，這兩個圓內(nèi)圈是排列順序，而外圈是自殺順序，如下圖所示：使用程式來求解的話，只要將陣列當(dāng)作環(huán)狀來處理就可以了，在陳列中由計數(shù)1開始，每找到三個無資料區(qū)就填入一個計數(shù)，直接計數(shù)來求解的話，只要將陣列當(dāng)作環(huán)狀來處理就可以了，在陣列中由計數(shù)1開始，每找到三個無資料區(qū)就填入一個計數(shù)，直而計數(shù)達(dá)41為止，然后將陣列由索引1開始列出，就可以得知每個位置的自殺順序，這就是約瑟夫排列，41個人報數(shù)3的約瑟夫排列如下所示：143

4、6138152243031634425175403161826737198352792032104121112839122233132923例3：有100張的一摞卡片，玲玲拿著它們，從最上面的一張開始按如下的順序進(jìn)行操作：把最上面的第一張卡片舍去，把下一張卡片放在這一摞卡片的最下面。再把原來的第三張卡片舍去，把下一張卡片放在最下面。反復(fù)這樣做，直到手中只剩下一張卡片，那么剩下的這張卡片是原來那一摞卡片的第幾張？分析與解：這100張卡片如

5、果用線串起來，其實還是一個圍成一圈的約瑟夫問題。如果上面幾題的解法看不太懂，可學(xué)學(xué)這題，從最簡單的情況開始找規(guī)律。下面從簡單的不失題目性質(zhì)的問題入手，尋找規(guī)律。列表如下：設(shè)這一摞卡片的張數(shù)為N，觀察上表可知：（1）當(dāng)N=2a（a=0，1，2，3，…）時，剩下的這張卡片是原來那一摞卡片的最后一張，即第2a張；（2）當(dāng)N=2am（m＜2a）時，剩下的這張卡片是原來那一摞卡片的第2m張。取N=100，因為100=2636，236=72，所以剩

6、下這張卡片是原來那一摞卡片的第72張。總結(jié)上題及例1例2：可歸納為兩種情況：1、留1，殺2類：剩下號＝（總數(shù)－小于總數(shù)最大的2的次方數(shù)）2＋12、殺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上面

7、的51264都是小于總數(shù)的最大的2的次方數(shù)。再看一道經(jīng)變化的逆推題：再看一道經(jīng)變化的逆推題：例4：如下左圖七枚棋子圍成一個圓圈從①開始每隔一個取一個依次取走①、③、⑤、⑦、④、②最后剩下⑥.二十枚棋子圍成一個圓圈(如右圖)從開始每隔一個取一個最后將只剩下一枚棋子是⑥.實際上例就是抽殺問題的“殺1留2類”，右圖可假設(shè)先從1開始取起，那根據(jù)規(guī)律留下的為：（20－16）2＝8號，想留下6號得逆時針倒推2枚棋子。則最后結(jié)果為19號開始。①③②④