抽杀问题-约瑟夫问题

抽杀问题-约瑟夫问题

ID:26044098

大小:107.03 KB

页数:5页

时间:2018-11-24

抽杀问题-约瑟夫问题_第1页
抽杀问题-约瑟夫问题_第2页
抽杀问题-约瑟夫问题_第3页
抽杀问题-约瑟夫问题_第4页
抽杀问题-约瑟夫问题_第5页
资源描述:

《抽杀问题-约瑟夫问题》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库

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

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

3、料区就填入一个計数,直而計数达41为止,然后將阵列由索引1开始列出,就可以得知每个位置的自杀順序,这就是約瑟夫排列,41個人报数3的約瑟夫排列如下所示:1436138152243031634425175403161826737198352792032104121112839122233132923由上可知,最后一個自杀的是在第31个位置,而倒数第二个自杀的要排在第16个位置,之前的人都死光了,所以他们也就不知道約瑟夫与他的朋友并没有遵守游戏规则了。小升初常见抽杀考题例举:例1:把1~999这999个自然数按顺时针的方向依次排列在一个圆圈上(如下图)。从

4、1开始按顺时针的方向,保留1,擦去2;保留3,擦去4……这样每隔一个数擦去一个数,转圈擦下去。问:最后剩下一个数时,剩下的是哪个数?   马到成功解析:可通过找规律得出,如果有2n个数,那么转一圈擦去一半,剩下2n-1个数,起始数还是1;再转一圈擦去剩下的一半,又剩下2n-2个数,起始数还是1……转了n圈后,就剩下一个数是1。如果有2n+d(d<2n)个数,那么当擦去d个数时,剩下2n个数,此时的第一个数是最后将剩下的数。因为擦去的第d个数是2d,所以2d+1就是最后剩下的整数。999=29+487,最后剩下的一个数是487×2+1=975。例2:10

5、00个学生坐成一圈,依次编号为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并离开,那么,问题就与上面这题完全一

6、样了。因为剩下999人时,第1人是2号,所以最后剩下的人的号码应比上题大1,是975+1=976(号)。为了加深理解,我们重新解这道题。解:如果有2n个人,那么报完第1圈后,剩下的是2的倍数号;报完第2圈后,剩下的是22的倍数号……报完第n圈后,剩下的是2n的倍数号,此时,只剩下一人,是2n号。如果有(2n+d)(1≤d<2n)人,那么当有d人退出圈子后还剩下2n人。因为下一个该退出去的是(2d+1)号,所以此时的第(2d+1)号相当于2n人时的第1号,而2d号相当于2n人时的第2n号,所以最后剩下的是第2d号。由1000=29+488知,最后剩下的学

7、生的编号是488×2=976(号)。例3:有100张的一摞卡片,玲玲拿着它们,从最上面的一张开始按如下的顺序进行操作:把最上面的第一张卡片舍去,把下一张卡片放在这一摞卡片的最下面。再把原来的第三张卡片舍去,把下一张卡片放在最下面。反复这样做,直到手中只剩下一张卡片,那么剩下的这张卡片是原来那一摞卡片的第几张?分析与解:这100张卡片如果用线串起来,其实还是一个围成一圈的约瑟夫问题。如果上面几题的解法看不太懂,可学学这题,从最简单的情况开始找规律。下面从简单的不失题目性质的问题入手,寻找规律。列表如下:  设这一摞卡片的张数为N,观察上表可知:  (1)

8、当N=2a(a=0,1,2,3,…)时,剩下的这张卡片是原来那一摞卡片的最后一张,即第2a张;

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。