抽杀问题例举[世界名题与小升初之二]

上传人:小** 文档编号:62912846 上传时间:2018-12-23 格式:DOC 页数:4 大小:101KB
返回 下载 相关 举报
抽杀问题例举[世界名题与小升初之二]_第1页
第1页 / 共4页
抽杀问题例举[世界名题与小升初之二]_第2页
第2页 / 共4页
抽杀问题例举[世界名题与小升初之二]_第3页
第3页 / 共4页
抽杀问题例举[世界名题与小升初之二]_第4页
第4页 / 共4页
亲,该文档总共4页,全部预览完了,如果喜欢就下载吧!
资源描述

《抽杀问题例举[世界名题与小升初之二]》由会员分享,可在线阅读,更多相关《抽杀问题例举[世界名题与小升初之二](4页珍藏版)》请在金锄头文库上搜索。

1、阅读材料世界名题与小升初之:抽杀问题(約瑟夫问题) 在各类竞赛中,各类小升初考试中相关的世界名题出现的概率极高,这是由小升初与数学竞赛的特点决定,这特点便是:知识性,趣味性,思想性相结合。先给大家介绍这一问题的由来。 据说著名犹太历史学家 Josephus有过以下的故事:在罗马人占领乔塔帕特後,39 個犹太人与Josephus及他的朋友躲到一個洞中,39個犹太人決定宁愿死也不要被人抓到,于是決定了一个自杀方式,41個人排成一个圆圈,由第1個人开始报数,每报数到第3人该人就必須自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从,Josephus要他

2、的朋友先假装遵从,他將朋友与自己安排在第16個与第31個位置,于是逃过了这场死亡游戏。解法約瑟夫问题可用代数分析來求解,将这个问题扩大好了,假设现在您与m个朋友不幸参与了这个游戏,您要如何保护您的朋友?只要画两个圆圈就可以让自己与朋友免于死亡游戏,这两个圆内圈是排列顺序,而外圈是自杀顺序,如下图所示: 使用程式来求解的话,只要将阵列当作环状来处理就可以了,在陈列中由计数1开始,每找到三个无资料区就填入一个计数,直接计数 來求解的話,只要將阵列当作环状来处理就可以了,在阵列中由計数1开始,每找到三个无资料区就填入一个計数,直而計数达41为止,然后將阵列由索引1开始列出,就可以得知每个位置的自杀順

3、序,这就是約瑟夫排列,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:把1999这999个自然数按顺时针的方向依次排列在一个圆圈上(如下图)。从1开始按顺时针的方向,保留1,擦去2;保留3,擦去4这样

4、每隔一个数擦去一个数,转圈擦下去。问:最后剩下一个数时,剩下的是哪个数?解析:可通过找规律得出,如果有2n个数,那么转一圈擦去一半,剩下2n-1个数,起始数还是1;再转一圈擦去剩下的一半,又剩下2n-2个数,起始数还是1转了n圈后,就剩下一个数是1。如果有2n+d(d2n)个数,那么当擦去d个数时,剩下2n个数,此时的第一个数是最后将剩下的数。因为擦去的第d个数是2d,所以2d+1就是最后剩下的整数。999=29+487,最后剩下的一个数是4872+1=975。例2:1000个学生坐成一圈,依次编号为1,2,3,1000。现在进行1,2报数:1号学生报1后立即离开,2号学生报2并留下,3号学生

5、报1后立即离开,4号学生报2并留下学生们依次交替报1或2,凡报1的学生立即离开,报2的学生留下,如此进行下去,直到最后还剩下一个人。问:这个学生的编号是几号?分析:这个问题与上面这题非常相似,只不过本例是报1的离开报2的留下,而上题相当于报1的留下报2的离开,由上题的结果可以推出本例的答案。本例中编号为1的学生离开后还剩999人,此时,如果原来报2的全部改报1并留下,原来报1的全部改报2并离开,那么,问题就与上面这题完全一样了。因为剩下999人时,第1人是2号,所以最后剩下的人的号码应比上题大1,是9751=976(号)。为了加深理解,我们重新解这道题。解:如果有2n个人,那么报完第1圈后,剩

6、下的是2的倍数号;报完第2圈后,剩下的是22的倍数号报完第n圈后,剩下的是2n的倍数号,此时,只剩下一人,是2n号。如果有(2nd)(1d2n)人,那么当有d人退出圈子后还剩下2n人。因为下一个该退出去的是(2d1)号,所以此时的第(2d1)号相当于2n人时的第1号,而2d号相当于2n人时的第2n号,所以最后剩下的是第2d号。由1000=29488知,最后剩下的学生的编号是4882=976(号)。例3:有100张的一摞卡片,玲玲拿着它们,从最上面的一张开始按如下的顺序进行操作:把最上面的第一张卡片舍去,把下一张卡片放在这一摞卡片的最下面。再把原来的第三张卡片舍去,把下一张卡片放在最下面。反复这

7、样做,直到手中只剩下一张卡片,那么剩下的这张卡片是原来那一摞卡片的第几张?分析与解:这100张卡片如果用线串起来,其实还是一个围成一圈的约瑟夫问题。如果上面几题的解法看不太懂,可学学这题,从最简单的情况开始找规律。下面从简单的不失题目性质的问题入手,寻找规律。列表如下:设这一摞卡片的张数为N,观察上表可知:(1)当N=2a(a=0,1,2,3,)时,剩下的这张卡片是原来那一摞卡片的最后一张,即第2a张;(2)当N=2a+m(m2a)时,剩下的这张卡片是原来那一摞卡片的第2m张。取N=100,因为100=26+36,236=72,所以剩下这张卡片是原来那一摞卡片的第72张。总结上题及例1例2:可

8、归纳为两种情况:1、 留1,杀2类:剩下号(总数小于总数最大的2的次方数)212、 杀1,留2类:剩下号(总数小于总数最大的2的次方数)2记住留1要加1,杀1不用加1,总发现有学生在这点上分辨不清。因此可对照:例1:为“留1”类,可用:(999512)21975例2:为“杀1”类,可用(1000512)2976例3:为“杀1”类,可用(10064)272上面的512,64都是小于总数的最大的2的次方数。再看一道经变化的逆推题:例4:如下左图,七枚棋子围成一个圆圈,从开始,每隔一个取一个,依次取走、,最后剩下.二十枚棋子围成一个圆圈(如右图),从 开始,每隔一个取一个,最后将只剩下一枚棋子是.

9、实际上例就是抽杀问题的“杀1留2类”,右图可假设先从1开始取起,那根据规律留下的为:(2016)28号,想留下6号得逆时针倒推2枚棋子。则最后结果为19号开始。试试我们玩的扑克牌:例5:有两副扑克牌,每副牌的排列顺序均按头两张是大王、小王,然后是黑桃、红桃、方块、梅花四种花色排列。每种花色的牌又按1,2,3,J,Q,K顺序排列。某人把按上述排列的两副扑克牌上下叠放在一起,然后把第一张丢掉,把第二张放在最底层,再把第三张丢掉,把第四张放在最底层,.如此进行下去,直至最后只剩下一张牌。试问所剩的这张牌是哪一张?解:注意到:如果手中只有64张牌,按这样规则丢牌,那么后剩下的应该是第64张牌。现在手中

10、有108张牌,多出1086444张,我们只需按此规定丢掉44张后,把88张牌放在手中牌的最底层时,这时手中牌恰为64张。这样,再丢下去,最后留下的就是原牌顺序的第88张,接下来的难点就涉及周期问题了,是哪张牌呢?先去掉一副,再去掉黑桃、红桃各十三张,即为88-54-2266。按照花色排列应为方块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=656

11、1,故从1号开始按规则划数,划了8899-6561=2338(个)数后,还剩下6561个数。这划去的数中的最后一个233823=3507,故最后留下6561个数中的第一个就是3508。这道题也可归纳出一个规律:“留1,杀2,3”型留下的这个数为(总数小于总数的最大的3的次方数)231考一考:连续自然数1,2,3,8899排成一列。从1开始,划掉1和2,留下3,划掉4和5留下6这么转圈划下去,最后留下的是哪个数?这道题可定为“杀1,2留3”型,其中的规律与答案就留给你自己去研究了。另外在最前面约瑟夫的介绍中的类型可说成为“留1、2杀3型”你探索一下这道题有什么规律。最后见识一下隐形抽杀问题:例7

12、:在纸上写着一列自然数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个新数

13、之和等于原来2n个数的和。这提示我们去考虑数列包含2,2 2,2 2 2,项的时刻。 6个2连乘是64,当经过100-64=36次操作后,原来的数1,2,71,362=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+50506=37978。学会了抽杀问题的思路再来理解这题的设计就比较容易了。5

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 商业/管理/HR > 管理学资料

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号