抽杀问题 约瑟夫问题

[阅读材料]世界名题与小升初之：抽杀问题（約瑟夫问题）--马到成功老师在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。

先给大家介绍这一问题的由来。

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特後，39 個犹太人与Josephus及他的朋友躲到一個洞中，39個犹太人決定宁愿死也不要被人抓到，于是決定了一个自杀方式，41個人排成一个圆圈，由第1個人开始报数，每报数到第3人该人就必須自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他將朋友与自己安排在第16個与第31個位置，于是逃过了这场死亡游戏。

解法約瑟夫问题可用代数分析來求解，将这个问题扩大好了，假设现在您与m个朋友不幸参与了这个游戏，您要如何保护您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆圈是排列顺序，而外圈是自杀顺序，如下图所示：使用程式来求解的话，只要将阵列当作环状来处理就可以了，在列中由计数1开始，每找到三个无资料区就填入一个计数，直接计数來求解的話，只要將阵列当作环状来处理就可以了，在阵列中由計数1开始，每找到三个无资料区就填入一个計数，直而計数达41为止，然后將阵列由索引1开始列出，就可以得知每个位置的自杀順序，这就是約瑟夫排列，41個人报数3的約瑟夫排列如下所示：14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23由上可知，最后一個自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道約瑟夫与他的朋友并没有遵守游戏规则了。

数据结构与算法分析（1）——约瑟夫问题0 问题描述 据说著名犹太历史学家 Josephus有过以下的故事：在罗马⼈占领乔塔帕特后，39 个犹太⼈与Josephus及他的朋友躲到⼀个洞中，39个犹太⼈决定宁愿死也不要被敌⼈抓到，于是决定了⼀个⾃杀⽅式，41个⼈排成⼀个圆圈，由第1个⼈开始报数，每报数到第3⼈该⼈就必须⾃杀，然后再由下⼀个重新报数，直到所有⼈都⾃杀⾝亡为⽌。

然⽽Josephus 和他的朋友并不想遵从。

⾸先从⼀个⼈开始，越过k-2个⼈（因为第⼀个⼈已经被越过），并杀掉第k个⼈。

接着，再越过k-1个⼈，并杀掉第k个⼈。

这个过程沿着圆圈⼀直进⾏，直到最终只剩下⼀个⼈留下，这个⼈就可以继续活着。

问题是，给定了和，⼀开始要站在什么地⽅才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与⾃⼰安排在第16个与第31个位置，于是逃过了这场死亡游戏。

[1] 简单地说就是n个⼈围成⼀个圈，假设编号为0~n-1，报数范围为1~m。

从第0个⼈开始报数，每报到m，这个⼈就出局。

接着下⼀个⼈从1开始重新报数...直到剩下最后⼀个⼈。

1 问题解法 该问题常⽤解法有链表法和数组法，其他的⽐如公式法和递归法以后补充。

个⼈觉得链表法最容易理解，可能是先⼊为主的⼼理，嘿嘿嘿，下⾯就简单说⼀下。

1.1 链表法 ⾸先建⽴长度为n的循环链表，然后头结点开始报数，每第m个数删除⼀个结点，直到只剩下⼀个结点。

#include <iostream>using namespace std;struct ListNode{int val;struct ListNode* next;};/******创建循环链表******/ListNode* creatCirListNode(int n){//创建头结点ListNode *head,*node,*newnode;node = new ListNode;node->val = 0;node->next = NULL;head = node;//创建链表for (int i = 1; i < n; i++){newnode = new ListNode;newnode->val = i;node->next = newnode;node = newnode;}//将最后⼀个结点指向头结点，形成循环链表node->next = head;return head;}/******约瑟夫问题求解******/int josephSolution(ListNode* head,int m){if (NULL == head){return -1;}ListNode* pNode; //⽤来遍历结点pNode = head;while (pNode->next != pNode) //循环终⽌条件是只剩下⼀个结点{for (int i = 0; i < m-1; i++) //报数{pNode = pNode->next;}cout << pNode->next->val << "->";pNode->next = pNode->next->next; //删除链表结点}return pNode->val;}int main(){int n = 41;int m = 3;int result;ListNode* pHead;pHead = creatCirListNode(n);result = josephSolution(pHead, m);cout << result << endl;system("pause");return0;} 运⾏结果：1.2 数组法 数组法的关键是使⽤求余的⽅法循环遍历数组i=(i+1)%n，其中i是数组下标即每个⼈的标号，n是总⼈数。

抽杀问题-约瑟夫问题[阅读材料]世界名题与小升初之：抽杀问题（約瑟夫问题）--马到成功老师在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。

先给大家介绍这一问题的由来。

据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特後，39 個犹太人与Josephus及他的朋友躲到一個洞中，39個犹太人決定宁愿死也不要被人抓到，于是決定了一个自杀方式，41個人排成一个圆圈，由第1個人开始报数，每报数到第3人该人就必須自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。

然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他將朋友与自己安排在第16個与第31個位置，于是逃过了这场死亡游戏。

解法約瑟夫问题可用代数分析來求解，将这个问题扩大好了，假设现在您与m 个朋友不幸参与了这个游戏，您要如何保护您的朋友？只要画两个圆圈就可以让自己与朋友免于死亡游戏，这两个圆内圈是排列顺序，而外圈是自杀顺序，如下图所示：使用程式来求解的话，只要将阵列当作环状来处理就可以了，在陈列中由计数1开始，每找到三个无资料区就填入一个计数，直接计数來求解的話，只要將阵列当作环状来处理就可以了，在阵列中由計数1开始，每找到三个无资料区就填入一个計数，直而計数达41为止，然后將阵列由索引1开始列出，就可以得知每个位置的自杀順序，这就是約瑟夫排列，41個人报数3的約瑟夫排列如下所示：14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23由上可知，最后一個自杀的是在第31个位置，而倒数第二个自杀的要排在第16个位置，之前的人都死光了，所以他们也就不知道約瑟夫与他的朋友并没有遵守游戏规则了。

约瑟夫斯问题探究学而思培优陈绍伦问题背景据说著名犹太历史学家约瑟夫斯有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与约瑟夫斯及他的朋友躲到一个洞中，他们宁死也不愿被敌人抓到，于是决定了一个自杀方式：41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止．可是约瑟夫斯和他的朋友并不想遵从，他们打算选择合适的位置，留到最后避免处决．于是，他将朋友与自己安排在第16个与第31个位置，逃过了这场死亡游戏．也因此，我们以故事的主人公命名这一系列的“抽杀”问题．情景一：直线型让我们先从比较简单的直线型猫吃老鼠着手研究．【问题1】（隔1吃1）猫将4只老鼠排成一行，先隔1只，再吃1只，再隔1只，再吃1只，……一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．其实这题更像是一个“脑筋急转弯”：第一只老鼠有可能被吃掉吗？答案显而易见！结论：排成一行，隔1吃1，留下的总是第1只．【问题2】（吃1隔1）（1）猫将4只老鼠排成一行，先吃1只，再隔1只，再吃1只，再隔1只，……一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将10只老鼠排成一行，先吃1只，再隔1只，再吃1只，再隔1只，……一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．对于数字比较简单的情况，实际动手操作是得到答案的好方法！（1）4只老鼠时：第一轮猫吃掉1、跳过2、吃掉3、跳过4，留下2、4；第二轮猫吃掉2，因此最后剩下的老鼠是原来的第4只．（2）10只老鼠时：第一轮猫吃掉1、跳过2、吃掉3、跳过4、……，留下2、4、6、8、10；第二轮猫吃掉2，跳过4、吃掉6、跳过8、吃掉10，留下4、8；第三轮猫吃掉4，因此最后剩下的老鼠是原来的第8只．观察每轮留下的老鼠位置，我们发现一个有趣的规律：处于第奇数个位置的老鼠，总会被吃掉；而处于第偶数个位置的老鼠留到下一轮．而且，能留下来的老鼠，在下一轮中位置编号也发生了变化：若前一轮在第2k（k为非0自然数）个位置，下一轮将在第k个位置．换句话说，老鼠编号能分解出几个质因数2，这只老鼠就能挺过前几轮！那么结论就显而易见了：结论：排成一行，吃1隔1，留下的是第2n只．（取范围内最大值）【问题3】（吃2隔1）（1）猫将10只老鼠排成一行，先吃2只，再隔1只，再吃2只，再隔1只，……一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将20只老鼠排成一行，先吃2只，再隔1只，再吃2只，再隔1只，……一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．【问题2】中观察的是因数2的个数，因为“吃1隔1”是以每2只老鼠为一个周期．那么，本题的“吃2隔1”，会不会与因数3的个数有关呢？我们来实际操作一下：（1）10只老鼠时：第一轮猫吃掉1和2、跳过3、吃掉4和5、跳过6，……，留下3、6、9；第二轮猫吃掉3和6，因此最后剩下的老鼠是原来的第9只．还真是！9可以分解出2个因数3，是范围内最多的，它留到了最后．（2）20只老鼠时：第一轮猫吃掉1和2、跳过3、吃掉4和5、跳过6，......，留下3、6、 (18)第二轮猫吃掉3和6、跳过9、吃掉12和15、跳过18，留下9、18；第三轮猫吃掉9、因此最后剩下的老鼠是原来的第18只．这里就有个小问题了：9和18都能分解出2个因数3，为什么留到最后的18呢？重新观察第二轮的结果：9和18都有2个因数3，所以它们都挺过了第2轮．同时，由于都没有第3个因数3，如果猫要继续吃下去的话，它们都无法挺过第3轮！这么看来，18能留到最后的原因，仅仅是因为它的编号比9大而已！于是我们可以得出结论了：结论：排成一行，吃2隔1，留下的是第3n或第23n×只．（取范围内最大值）对于一般情况“排成一行，吃k隔1”，用同样的方法可以得到类似的结论，最终留下的编号是“能分解出因数(1)k+的个数最多且范围内最大的数”．【问题4】（吃1隔1吃1）（1）猫将9只老鼠排成一行，按“吃-隔-吃”的规律吃掉老鼠，一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将27只老鼠排成一行，按“吃-隔-吃”的规律吃掉老鼠，一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．“吃-隔-吃”也是每3只老鼠为一个周期的．因此我们先从总数为3n时探讨规律：（1）9只老鼠时：第一轮猫吃掉1和3、跳过2、吃掉4和6、跳过5，……，留下2、5、8；第二轮猫吃掉2和8，因此最后剩下的老鼠是原来的第5只．（2）27只老鼠时：第一轮猫吃掉1和3、跳过2、吃掉4和6、跳过5，......，留下2、5、 (26)第二轮猫吃掉2和8、跳过5、吃掉11和17、跳过14、……，留下5、14、23；第三轮猫吃掉5和23，因此最后剩下的老鼠是原来的第14只．答案的5和14，与总数9和27存在什么样的联系呢？这一规律，需要些许灵感才能观察出来：5是1~9的中间数，14是1~27的中间数．当然，这并不只是随意猜测，“中间数”的规律是可以解释的：总数为3的时候，显然留下的是正中间的第2只；总数为9的时候，我们将老鼠们分为3组：{1，2，3}、{4，5，6}、{7，8，9}，留到最后的老鼠，它就应该是正中间一组的正中间一个，当然，它也处于所有数的正中间．如此类推，总数为27、81的时候，留下的也是正中间的第14只、第41只老鼠．根据等差数列的知识，我们可以用下列公式将中间数表示出来：结论：3n只，排成一行，“吃-隔-吃”，留下的是第312n+只．也就是说，答案一定在2、5、14、41、……这些数之中．我们得到了一个漂亮的结论！但是，上述结论的前提是“总数为3n只”．如果总数不是3的幂呢？【问题5】（吃1隔1吃1）（1）猫将12只老鼠排成一行，按“吃-隔-吃”的规律吃掉老鼠，一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将16只老鼠排成一行，按“吃-隔-吃”的规律吃掉老鼠，一轮结束后再次重新开始，直到最后剩下1只老鼠，这只老鼠是原来的第________只．（1）12只老鼠时：第一轮猫吃掉1和3、跳过2、吃掉4和6、跳过5，……，留下2、5、8、11；第二轮猫吃掉2和8、跳过5、吃掉11，因此最后剩下的老鼠是原来的第5只．（2）16只老鼠时：第一轮猫吃掉1和3、跳过2、吃掉4和6、跳过5，……，留下2、5、8、11、14；第二轮猫吃掉2和8、跳过5、吃掉11、跳过14、……，留下5、14；第三轮猫吃掉5，因此最后剩下的老鼠是原来的第14只．这些结果，在【问题4】中曾经也出现过，也就是说答案仍是312n+．为什么呢？在这里，我们可以用倒推的方法进行思考：（1）显然，当老鼠数量不超过3，最终将留下2；（2）若这一轮老鼠数量不超过3，那么上一轮的老鼠总数不超过9．此时，这一轮的2在上一轮的编号是5；（3）若这一轮老鼠数量不超过9，那么上一轮的老鼠总数不超过27．此时，这一轮的5在上一轮的编号是14；（４）若这一轮老鼠数量不超过２７，那么上一轮的老鼠总数不超过81．此时，这一轮的5在上一轮的编号是41；……如此递推可知，活到最终轮的老鼠在每一轮的编号，倒过来数依次是2、5、14、41、……换句话说，答案应该是312n+，而且应取范围内数值最大的一个！结论：排成一行，“吃-隔-吃”，留下的是第312n+只．（取范围内最大值）情景二：封闭型如果把“猫吃老鼠”问题放在圆环上研究，又会有怎么样的变化？【问题6】（吃1隔1）（1）猫将4只老鼠围成一圈，先吃1只，再隔1只，再吃1只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将8只老鼠围成一圈，先吃1只，再隔1只，再吃1只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．简单枚举后发现，总数为4时留下的就是第4只；总数为8时留下的就是第8只． 这个结果与直线型的情况完全一致．巧合的是最后一只老鼠总被跳过，所以新的一轮又可以看成是“先吃后隔”的问题，直线型中的“从头开始”，最终结果当然一致．我们还可以用递推的思路理解：“总数为8的隔1吃1问题”，操作一轮后恰好变为“总数为4的隔1吃1问题”．也就是说，最终留下的将是第二轮的第4只，而它也是第一轮的第8只．所以，如果总数为4时留下的是最后一只，那么总数为8时留下的也是最后一只． 同理，总数为16可变为总数为8，总数为32可变为总数为16……因此得出结论：结论：2n 只，围成一圈，吃1隔1，留下的是第2n 只（最后一只）．【问题7】（吃1隔1）猫将9只老鼠围成一圈，先吃1只，再隔1只，再吃1只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．从这里开始，我们要用“化归思想”——将新问题转化为已解决问题——来处理猫吃老鼠问题：总数为2n 的情况我们已经解决过了，那么如果我们考虑让猫吃掉1只，剩下8只时的最后一只，不就是我们要找的答案吗？马上尝试一下：吃掉1、跳过2，此时还有8只老鼠，3是新的起点，那么刚跳过的2就是此时的最后一只了，于是答案为第2只．更一般的情况同样可以归纳出来：（1）总数为M 时，先吃掉一些老鼠使总数变为2n ，也就是要吃掉(2)n M −只． （在这里，为了计算方便，我们希望吃掉的老鼠尽量少，也就意味着2n 要尽量大）（2）找出此时的最后一只老鼠，它正是最后一个“吃-跳”周期中跳过的一只． 由于每2只老鼠为一个“吃-跳”周期，所以最后跳过的是第2(2)n M −只老鼠． 结论：M 只，围成一圈，吃1隔1，留下的是第2(2)n M −只．（n 取范围内最大）【问题8】（隔1吃1）猫将9只老鼠围成一圈，先隔1只，再吃1只，再隔1只，再吃1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．继续用化归思想：“从1开始，先隔再吃”，不就是“从2开始的先吃后隔”吗？于是，我们仍然可以按照【问题7】的方法进行计算，最后编号加1就可以了．也就是说，答案是第 32(92)13−+=只．这里还有一个神奇的二进制方法：将总数改写为二进制形式：29(1001)=，将最高位的1移动到最右边，马上可以得到正确答案(0011)3=了！2这个“数位操作”法的原理是这样的：将最高位的1移走时，相当于原数减去了最大的2n；将1放到最右边时，其余各数全部左移一位，即数值乘2；最低位多了1，相当于给数值加1．这正是结论中的2(2)1nM−+！由于这一方法只需对二进制表达进行位移操作，在编程上很容易实现，所以正是计算机解决约瑟夫斯问题的快速算法．【问题9】（吃2隔1）（1）猫将9只老鼠围成一圈，先吃2只，再隔1只，再吃2只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将18只老鼠围成一圈，先吃2只，再隔1只，再吃2只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．实际操作发现，（1）的答案为9，（2）的答案为18．也就是说，这个结果也是与直线型完全一致的．与【问题6】类似，我们可以得出结论：结论：3n或23n×只（最后一只）．×只，围成一圈，吃2隔1，留下的是第3n或23n【问题10】（吃2隔1）（1）猫将19只老鼠围成一圈，先吃2只，再隔1只，再吃2只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．（2）猫将20只老鼠围成一圈，先吃2只，再隔1只，再吃2只，再隔1只，……直到最后剩下1只老鼠，这只老鼠是原来的第________只．仿照【问题7】的“化归思想”，如果提前吃掉一部分老鼠，把总数变为3n或23n×，问题将迎刃而解．问题是，应该将总数变成哪一种呢？这里的化归，不仅要看到总数，而且要保证余下的老鼠依然是“吃2隔1”的周期．所以，我们先吃掉、跳过的部分，也必须是整数个“吃2隔1”周期．换句话说，提前吃掉的老鼠总数，必须是一个偶数．那么上述两道题的做法应该是这样的：（1）19只老鼠：19是奇数，吃掉偶数只老鼠，结果为奇数，所以应化归为奇数型即9个．先吃掉19910÷=（个）周期．−=（只），每个周期吃2隔1，即进行了1025此时，最后跳过的老鼠是第5315×=（只），因此答案为第15只．（2）20只老鼠：20是偶数，吃掉偶数只老鼠，结果为偶数，所以应化归为偶数型即18个．先吃掉20182÷=（个）周期．−=（只），每个周期吃2隔1，即进行了221此时，最后跳过的老鼠是第133×=（只），因此答案为第3只．那么，一般结论也可以类似归纳出来了：结论：M只，围成一圈，吃2隔1，若M为奇数，留下的是第(3)23nM−÷×只．（n取范围内最大）若M为偶数，留下的是第(23)23nM−×÷×只．（n取范围内最大）当然，我们可以将类似的结论推广至”封闭型的吃k隔1”问题．本文篇幅有限，在此不作赘述．感兴趣的读者可以尝试自证，深入探究！。

课堂分享集锦——宋青平分享一：约瑟夫抽杀问题【题型一】直线型抽杀知识点：直线抽杀（1）杀一个留一个，剩下第2n 个， 并且2n 尽量大 （2）杀两个留一个（若少于3个，则无法操作），剩下3n 的倍数，31n ⨯，32n ⨯ （3）杀三个留一个（若少于4个，则无法操作），剩下4n 的倍数，41n ⨯，42n ⨯，43n ⨯【例题1】（1）艾迪拿出珍藏多年的1000个馒头排成一排准备边玩边吃：从左边第一个开始，先吃一个，然后隔一个吃一个，吃到最右边再回到左边接着吃，仍然是先吃一个，然后隔一个吃一个，最后剩下的一个捏着玩，那么被捏着玩的是左数第几个馒头？（2）艾迪拿出珍藏多年的1000个馒头排成一排准备边玩边吃：从左边第一个开始，吃两个保留一个，吃到最右边再回到左边接着吃，仍然是吃两个保留一个，最后剩下的一个挂起来，那么被挂起来的是左数第几个馒头？（3）艾迪拿出珍藏多年的20个馒头排成一排准备边玩边吃：从左边第一个开始，吃两个保留一个，吃到最右边再回到左边接着吃，仍然是吃两个保留一个，直到个数少于3个不能操作为止，那么最后剩下的是左数第几个馒头？【题型二】围成一圈1、2抽杀知识点：围成一圈，杀一个留一个（1）当2n a =时，剩下第2n 个，也就是第一刀的前一个 （2）当2n a ≠时，剩下第()22n a -个【铺垫】（1）艾迪拿出珍藏多年的64个馒头排成一圈准备边玩边吃：从某一个开始作为第一个，顺时针转，先吃一个，然后隔一个吃一个，最后剩下的一个当球踢，那么被当球踢的是顺时针数第几个馒头？（2）艾迪拿出珍藏多年的20个馒头排成一圈准备边玩边吃：从某一个开始作为第一个，顺时针转，先吃一个，然后隔一个吃一个，最后剩下的一个当球踢，那么被当球踢的是顺时针数第几个馒头？【例题2】（1）1000个学生坐成一个圈，依次编号为1，2，3，，1000．现在进行1，2报数：1号学生报1后立即离开，2号学生报2并留下，3号学生报1后立即离开，4号学生报2并留下学生们依次交替报1或2，凡报1的学生立即离开，报2的学生留下，如此进行下去，直到最后还剩一个人．问：这个学生的编号是几号？（2）如下左图，七枚棋子围成一个圆圈，从①开始，每隔一个取一个，依次取走①、③、⑤、⑦、④、②，最后剩下⑥．二十枚棋子围成一个圆圈（如右图），从__________开始，每隔一个取一个，最后将只剩下一枚棋子是⑥．【练一练】这999个自然数按顺时针的方向依次排列在一个圆圈上．从1开始按顺时针（1）把1999的方向，保留1，擦去2；保留3，擦去4这样每隔一个数擦去一个数，转圈擦下去．问：最后剩下一个数时，剩下的是哪个数？（2）有100张的一摞卡片，玲玲拿着他们，从最上面的一张开始按如下的顺序进行操作：把最上面的第一张卡片舍去，把下一张卡片放在这一摞卡片的最下面．再把原来的第三张卡片舍去，把下一张卡片放在最下面．反复这样做，直到手中只剩下一张卡片，那么剩下的这张卡片是原来那一摞卡片的第几张?（3）有两副扑克牌，每副牌的排列顺序均按头两张是大王、小王，然后是黑桃、红桃、方块、梅花四种花色排列．每种花色的牌又按A ，2，3，，J ，Q ，K 顺序排列．某人把按上述排列的两幅扑克牌上下叠放在一起，然后把第一张丢掉，把第二张放在最底层，再把第三张丢掉，把第四张放在最底层，……如此进行下去，直至最后只剩下一张牌．试问所剩的这张牌是哪一张？【题型三】围成一圈1、2、3抽杀知识点：围成一圈，杀两个留一个（1）当3n a =时，剩下第3n 个，也就是第一刀的前一个；（2）当32n a m =+时，也就是a 为奇数，剩下第()332n a -⨯个； （3）（可忽略）当321n a m =++时，也就是a 为偶数，剩下第332n a -个，3n 尽量接近32a 。

“约瑟夫”问题及若干变种林厚从例1、约瑟夫问题(Josephus)[问题描述]M只猴子要选大王，选举办法如下：所有猴子按1…M编号围坐一圈，从第1号开始按顺序1，2，…，N报数，凡报到N的猴子退出到圈外，再从下一个猴子开始继续1~ N报数，如此循环，直到圈内只剩下一只猴子时，这只猴子就是大王。

M和N由键盘输入，1≤N,M≤10000，打印出最后剩下的那只猴子的编号。

例如，输入8 3，输出：7。

[问题分析1]这个例题是由古罗马著名史学家Josephus提出的问题演变而来的，所以通常称为Josephus(约瑟夫)问题。

在确定程序设计方法之前首先来考虑如何组织数据，由于要记录m只猴子的状态，可利用含m 个元素的数组monkey来实现。

利用元素下标代表猴子的编号，元素的值表示猴子的状态，用monkey[k]=1表示第k只猴子仍在圈中，monkey[k]=0则表示第k只猴子已经出圈。

程序采用模拟选举过程的方法，设变量count表示计数器，开始报数前将count置为0，设变量current表示当前报数的猴子编号，初始时也置为0，设变量out记录出圈猴子数，初始时也置为0。

每次报数都把monkey[current]的值加到count上，这样做的好处是直接避开了已出圈的猴子（因为它们对应的monkey[current]值为0），当count=n时，就对当前报数的猴子作出圈处理，即：monkey[current]：=0，count：=0，out：=out+1。

然后继续往下报数，直到圈中只剩一只猴子为止（即out=m-1）。

参考程序如下：program josephus1a {模拟法，用数组下标表示猴子的编号}const maxm=10000;var m,n,count,current,out,i:integer;monkey:array [1..maxm] of integer;beginwrite('Input m,n:');readln(m,n);for i:=1 to m do monkey[i]:=1;out:=0; count:=0; current:=0;while out<m-1 dobeginwhile count<n dobeginif current<m then current:=current+1 else current:=1;count:=count+monkey[current];end;monkey[current]:=0; out:=out+1; count:=0end;for i:=1 to m doif monkey[i]=1 then writeln('The monkey king is no.',i);readlnend.[运行结果]下划线表示输入Input m，n:8 3The monkey king is no.7 {时间：0秒}Input m，n:10000 1987The monkey king is no.8544 {时间：3秒}[反思]时间复杂度很大O(M*N)，对于极限数据会超时。

阅读材料世界名题与小升初之：抽杀问题约瑟夫问题--马到成功老师在各类竞赛中,各类小升初考试中相关的世界名题出现的概率极高,这是由小升初与数学竞赛的特点决定,这特点便是：知识性,趣味性,思想性相结合;先给大家介绍这一问题的由来;据说着名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特後,39 个犹太人与Josephus及他的朋友躲到一个洞中,39个犹太人决定宁愿死也不要被人抓到,于是决定了一个自杀方式,41个人排成一个圆圈,由第1个人开始报数,每报数到第3人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止;然而Josephus 和他的朋友并不想遵从,Josephus要他的朋友先假装遵从,他将朋友与自己安排在第16个与第31个位置,于是逃过了这场死亡游戏;解法约瑟夫问题可用代数分析来求解,将这个问题扩大好了,假设现在您与m个朋友不幸参与了这个游戏,您要如何保护您的朋友只要画两个圆圈就可以让自己与朋友免于死亡游戏,这两个圆内圈是排列顺序,而外圈是自杀顺序,如下图所示：使用程式来求解的话,只要将阵列当作环状来处理就可以了,在陈列中由计数1开始,每找到三个无资料区就填入一个计数,直接计数来求解的话,只要将阵列当作环状来处理就可以了,在阵列中由计数1开始,每找到三个无资料区就填入一个计数,直而计数达41为止,然后将阵列由索引1开始列出,就可以得知每个位置的自杀顺序,这就是约瑟夫排列,41个人报数3的约瑟夫排列如下所示：14 36 1 38 15 2 24 30 3 16 34 4 25 17 5 40 31 6 18 26 7 37 19 8 35 27 9 20 32 10 41 21 11 28 39 12 22 33 13 29 23由上可知,最后一个自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的人都死光了,所以他们也就不知道约瑟夫与他的朋友并没有遵守游戏规则了;小升初常见抽杀考题例举：例1：把1～999这999个自然数按顺时针的方向依次排列在一个圆圈上如下图;从1开始按顺时针的方向,保留1,擦去2；保留3,擦去4……这样每隔一个数擦去一个数,转圈擦下去;问：最后剩下一个数时,剩下的是哪个数马到成功解析：可通过找规律得出,如果有2n个数,那么转一圈擦去一半,剩下2n-1个数,起始数还是1；再转一圈擦去剩下的一半,又剩下2n-2个数,起始数还是1……转了n圈后,就剩下一个数是1;如果有2n+dd＜2n个数,那么当擦去d个数时,剩下2n个数,此时的第一个数是最后将剩下的数;因为擦去的第d个数是2d,所以2d+1就是最后剩下的整数;999=29+487,最后剩下的一个数是487×2+1=975;例2：1000个学生坐成一圈,依次编号为1,2,3,…,1000;现在进行1,2报数：1号学生报1后立即离开,2号学生报2并留下,3号学生报1后立即离开,4号学生报2并留下……学生们依次交替报1或2,凡报1的学生立即离开,报2的学生留下,如此进行下去,直到最后还剩下一个人;问：这个学生的编号是几号分析：这个问题与上面这题非常相似,只不过本例是报1的离开报2的留下,而上题相当于报1的留下报2的离开,由上题的结果可以推出本例的答案;本例中编号为1的学生离开后还剩999人,此时,如果原来报2的全部改报1并留下,原来报1的全部改报2并离开,那么,问题就与上面这题完全一样了;因为剩下999人时,第1人是2号,所以最后剩下的人的号码应比上题大1,是975＋1=976号;为了加深理解,我们重新解这道题;解：如果有2n个人,那么报完第1圈后,剩下的是2的倍数号；报完第2圈后,剩下的是22的倍数号……报完第n圈后,剩下的是2n的倍数号,此时,只剩下一人,是2n号;如果有2n＋d1≤d＜2n人,那么当有d人退出圈子后还剩下2n人;因为下一个该退出去的是2d＋1号,所以此时的第2d＋1号相当于2n人时的第1号,而2d号相当于2n人时的第2n 号,所以最后剩下的是第2d号;由1000=29＋488知,最后剩下的学生的编号是488×2=976号;例3：有100张的一摞卡片,玲玲拿着它们,从最上面的一张开始按如下的顺序进行操作：把最上面的第一张卡片舍去,把下一张卡片放在这一摞卡片的最下面;再把原来的第三张卡片舍去,把下一张卡片放在最下面;反复这样做,直到手中只剩下一张卡片,那么剩下的这张卡片是原来那一摞卡片的第几张分析与解：这100张卡片如果用线串起来,其实还是一个围成一圈的约瑟夫问题;如果上面几题的解法看不太懂,可学学这题,从最简单的情况开始找规律;下面从简单的不失题目性质的问题入手,寻找规律;列表如下：设这一摞卡片的张数为N,观察上表可知：1当N=2aa=0,1,2,3,…时,剩下的这张卡片是原来那一摞卡片的最后一张,即第2a张；2当N=2a+mm＜2a时,剩下的这张卡片是原来那一摞卡片的第2m张;取N=100,因为100=26+36,2×36=72,所以剩下这张卡片是原来那一摞卡片的第72张;总结上题及例1例2：可归纳为两种情况：1、留1,杀2类：剩下号＝总数－小于总数最大的2的次方数×2＋12、杀1,留2类：剩下号＝总数－小于总数最大的2的次方数×2记住留1要加1,杀1不用加1,总发现有学生在这点上分辨不清;因此可对照：例1：为“留1”类,可用：999－512×2＋1＝975例2：为“杀1”类,可用1000－512×2＝976例3：为“杀1”类,可用100－64×2＝72上面的512,64都是小于总数的最大的2的次方数;再看一道经变化的逆推题：例4：如下左图,七枚棋子围成一个圆圈,从①开始,每隔一个取一个,依次取走①、③、⑤、⑦、④、②,最后剩下⑥.二十枚棋子围成一个圆圈如右图,从开始,每隔一个取一个,最后将只剩下一枚棋子是⑥.实际上例就是抽杀问题的“杀1留2类”,右图可假设先从1开始取起,那根据规律留下的为：20－16×2＝8号,想留下6号得逆时针倒推2枚棋子;则最后结果为19号开始; 试试我们玩的扑克牌：例5：有两副扑克牌,每副牌的排列顺序均按头两张是大王、小王,然后是黑桃、红桃、方块、梅花四种花色排列;每种花色的牌又按1,2,3,…,J,Q,K 顺序排列;某人把按上述排列的两副扑克牌上下叠放在一起,然后把第一张丢掉,把第二张放在最底层,再把第三张丢掉,把第四张放在最底层,…….如此进行下去,直至最后只剩下一张牌;试问所剩的这张牌是哪一张解：注意到：如果手中只有64张牌,按这样规则丢牌,那么后剩下的应该是第64张牌;现在手中有108张牌,多出108－64＝44张,我们只需按此规定丢掉44张后,把88张牌放在手中牌的最底层时,这时手中牌恰为64张;这样,再丢下去,最后留下的就是原牌顺序的第88张,接下来的难点就涉及周期问题了,是哪张牌呢先去掉一副,再去掉黑桃、红桃各十三张,即为88-54-2×26＝6;按照花色排列应为方块6;来个再难点的三个数一组的题：例6：连续自然数1,2,3,…,8899排成一列;从1开始,留1划掉2和3,留4划掉5和6……这么转圈划下去,最后留下的是哪个数可仿例1与例2;这道题留1划2和3,每次留下三分之一,显然与3的N 次方有关了;当有3n 个数时,留下的数是1号;小于8899的形如3n 的数是38=6561,故从1号开始按规则划数,划了8899-6561=2338个数后,还剩下6561个数;这划去的数中的最后一个2338÷2×3=3507,故最后留下6561个数中的第一个就是3508;这道题也可归纳出一个规律：“留1,杀2,3”型留下的这个数为＝总数－小于总数的最大的3的次方数÷2×3＋1考一考：连续自然数1,2,3,…,8899排成一列;从1开始,划掉1和2,留下3,划掉4和5留下6……这么转圈划下去,最后留下的是哪个数这道题可定为“杀1,2留3”型,其中的规律与答案就留给你自己去研究了;另外在最前面约瑟夫的介绍中的类型可说成为“留1、2杀3型”你探索一下这道题有什么规律; 最后见识一下隐形抽杀问题：例7：在纸上写着一列自然数1,2,……,99,100;一次操作是指将这列数中最前面的两个数划去,然后把这两个数的和写在数列的最后面,例如一次操作后得到3,4,…,99,100,3；而两次操作后得到5,6,…,99,100,3,7;这样不断进行下去,最后将只剩下一个数;问：最后剩下的数是多少最初的100个数连同后面写下的数,纸上出现的所有数的总和是多少① ③ ② ④ ⑤ ⑥ ⑦ ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ ⑩ ⑾ ⑿ ⒀ ⒁ ⒂ ⒃ ⒄ ⒅ ⒆ ⒇马到成功解析：在每次操作过程中,数列中添加的数等于划去的两个数之和,因此数列中所有数的和保持不变,于是当最后只剩下一个数时,它就是原来的100个数之和,为1+2+…+99+100=5050;当数列中有2n个数时,经过n次操作后将被全部划去,同时出现n个新数,并且这n 个新数之和等于原来2n个数的和;这提示我们去考虑数列包含2,2 ×2,2 ×2 ×2,…项的时刻;6个2连乘是64,当经过100-64=36次操作后,原来的数1,2,…,71,36×2=72被划去,划去的数的和是1+2+…+71+72=2628;此时数列中共有64个数,并且这64个数的和与原来100个数的和相等,是5050;从该时刻起,依次再经过32,16,8,4,2,1次操作后,纸上出现的新数的个数依次为32,16,8,4,2,1;根据前面的分析,每一轮出现的所有新数的和都是5050;从数列中有64个数变为只有1个数,操作共进行了6轮;综上所述,纸上写出的所有数之和为2628+5050+5050×6=37978;学会了抽杀问题的思路再来理解这题的设计就比较容易了;。