admin 管理员组文章数量: 1086019
2024年3月21日发(作者：go 微服务框架 对比)
[阅读材料]世界名题与小升初之：
抽杀问题（約瑟夫问题）
--
马到成功老师
在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与
数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。
先给大家介绍这一问题的由来。
据说著名犹太历史学家 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……这样每隔一个数擦去一个数，转
圈擦下去。问：最后剩下一个数时，剩下的是哪个数？
nn-1
马到成功解析：可通过找规律得出，如果有
2
个数，那么转一圈擦去一半，剩下
2
个数，
n-2
起始数还是1；再转一圈擦去剩下的一半，又剩下2个数，起始数还是1……转了n圈后，
就剩下一个数是1。
如果有2+d（d＜2n）个数，那么当擦去d个数时，剩下2个数，此时的第一个数是最后将
9
剩下的数。因为擦去的第d个数是2d，所以2d+1就是最后剩下的整数。999=2+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（号）。
为了加深理解，我们重新解这道题。
解：如果有2个人，那么报完第1圈后，剩下的是2的倍数号；报完第2圈后，剩下的是
2nn
2的倍数号……报完第n圈后，剩下的是2的倍数号，此时，只剩下一人，是2号。
如果有（2＋d）（1≤d＜2）人，那么当有d人退出圈子后还剩下2人。因为下一个
n
该退出去的是（2d＋1）号，所以此时的第（2d＋1）号相当于2人时的第1号，而2d号相
nn9
当于2人时的第2号，所以最后剩下的是第2d号。由1000=2＋488知，最后剩下的学生
的编号是488×2=976（号）。
nnn
n
nn
精选
例3：有100张的一摞卡片，玲玲拿着它们，从最上面的一张开始按如下的顺序进行操作：
把最上面的第一张卡片舍去，把下一张卡片放在这一摞卡片的最下面。再把原来的第三张卡
片舍去，把下一张卡片放在最下面。反复这样做，直到手中只剩下一张卡片，那么剩下的这
张卡片是原来那一摞卡片的第几张？
分析与解：这100张卡片如果用线串起来，其实还是一个围成一圈的约瑟夫问题。
如果上面几题的解法看不太懂，可学学这题，从最简单的情况开始找规律。
下面从简单的不失题目性质的问题入手，寻找规律。列表如下：
设这一摞
卡片的张数为
N，观察上表可知：
（1）当N=2a（a=0，1，2，3，…）时，剩下的这张卡片是原来那一摞卡片的最后一张，
即第2a张；
（2）当N=2a+m（m＜2a）时，剩下的这张卡片是原来那一摞卡片的第2m张。
取N=100，因为100=26+36，2×36=72，所以剩下这张卡片是原来那一摞卡片的第72
张。
总结上题及例1例2：可归纳为两种情况：
1、 留1，杀2类：剩下号＝（总数－小于总数最大的2的次方数）×2＋1
2、 杀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号开始。
精选
版权声明：本文标题：抽杀问题-约瑟夫问题 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://roclinux.cn/p/1710989606a583014.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。
发表评论