笔算解决约瑟夫问题

笔算解决约瑟夫问题在M比较小的时候 ，可以用笔算的方法求解，M=2即N个人围成一圈，1，2，1，2的报数，报到2就去死，直到只剩下一个人为止。当N=2k的时候，第一个报数的人就是最后一个死的，对于任意的自然数N 都可以表示为N=2k+t,其中tn/2于是当有t个人去死的时候，就只剩下2k个人 ，这2k个人中第一个报数的就是最后去死的。这2k个人中第一个报数的人就是2t+1于是就求出了当M=2时约瑟夫问题的解：求出不大于N的最大的2的整数次幂，记为2k，最后一个去死的人是2(N-2k)+1M=3即N个人围成一圈，1，2，3，1，2，3的报数，报到2就去死，直到只剩下一个人为止。此时要比M=2时要复杂的多我们以N=2009为例计算N=2009，M=3时最后被杀死的人记为F(2009,3),或者可以简单的记为F(2009)假设现在还剩下n个人，则下一轮将杀死n/3个人，表示取整，还剩下n-n/3个人设这n个人为a1,a2,.,a(n-1),an从a1开始报数，一圈之后，剩下的人为a1,a2,a4,a5,.a(n-n mod 3-1),a(n-n mod 3+1),.,an于是可得：1、这一轮中最后一个死的是a(n-n mod 3),下一轮第一个报数的是a(n-n mod 3+1)2、若3|n,则最后死的人为新一轮的第F(n-n/3)个人若n mod 30 且f(n-n/3)n mod 3则最后死的人为新一轮的第F(n-n/3)-（n mod 3）人3、新一轮第k个人对应原来的第 3*(k-1)/2+(k-1)mod 2+1个人综合1，2，3可得：F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(6)=1，当f(n-n/3)n mod 3时 k=F(n-n/3)-（n mod 3） ，F(n)=3*(k-1)/2+(k-1)mod 2+1这种算法需要计算 log(3/2)2009次 这个数不大于22，可以用笔算了于是：第一圈，将杀死669个人，这一圈最后一个被杀死的人是2007，还剩下1340个人，第二圈，杀死446人，还剩下894人第三圈，杀死298人，还剩下596人第四圈，杀死198人，还剩下398人第五圈，杀死132人，还剩下266人第六圈，杀死88人，还剩下178人第七圈，杀死59人，还剩下119人第八圈，杀死39人，还剩下80人第九圈，杀死26人，还剩下54人第十圈，杀死18人，还剩36人十一圈，杀死12人，还剩24人十二圈，杀死8人，还剩16人十三圈，杀死5人，还剩11人十四圈，杀死3人，还剩8人十五圈，杀死2人，还剩6人F(1)=1,F(2)=2,F(3)=2,F(4)=1,F(5)=4，F(6)=1，然后逆推回去F(8)=7 F(11)=7 F(16)=8 f(24)=11 f(36)=16 f(54)=23 f(80)=31 f(119)=43 f(178)=62 f(266)=89 f(398)=130F(596)=191 F(894)=286 F(1340)=425 F(2009)=634在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。先给大家介绍这一问题的由来。 据说著名犹太历史学家 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：把1999这999个自然数按顺时针的方向依次排列在一个圆圈上（如下图）。从1开始按顺时针的方向，保留1，擦去2；保留3，擦去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号学生报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圈后，剩下的是2的倍数号；报完第2圈后，剩下的是22的倍数号报完第n圈后，剩下的是2n的倍数号，此时，只剩下一人，是2n号。如果有（2nd）（1d2n）人，那么当有d人退出圈子后还剩下2n人。因为下一个该退出去的是（2d1）号，所以此时的第（2d1）号相当于2n人时的第1号，而2d号相当于2n人时的第2n号，所以最后剩下的是第2d号。由1000=29488知，最后剩下的学生的编号是4882=976（号）。例3：有100张的一摞卡片，玲玲拿着它们，从最上面的一张开始按如下的顺序进行操作：把最上面的第一张卡片舍去，把下一张卡片放在这一摞卡片的最下面。再把原来的第三张卡片舍去，把下一张卡片放在最下面。反复这样做，直到手中只剩下一张卡片，那么剩下的这张卡片是原来那一摞卡片的第几张？分析与解：这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：可归纳为两种情况：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：如下左图,七枚棋子围成一个圆圈,从开始,每隔一个取一个,依次取走、,最后剩下.二十枚棋子围成一个圆圈(如右图),从 开始,每隔一个取一个,最后将只剩下一枚棋子是.实际上例就是抽杀问题的“杀1留2类”，右图可假设先从1开始取起，那根据规律留下的为：（2016）28号，想留下6号得逆时针倒推2枚棋子。则最后结果为19号开始。试试我们玩的扑克牌：例5：有两副扑克牌，每副牌的排列顺序均按头两张是大王、小王，然后是黑桃、红桃、方块、梅花四种花色排列。每种花色的牌又按1，2，3，J,Q,K顺序排列。某人把按上述排列的两副扑克牌上下叠放在一起，然后把第一张丢掉，把第二张放在最底层，再把第三张丢掉，把第四张放在最底层，.如此进行下去，直至最后只剩下一张牌。试问所剩的这张牌是哪一张？解：注意到：如果手中只有64张牌，按这样规则丢牌，那么后剩下的应该是第64张牌。现在手中有108张牌，多出1086444张，我们只需按此规定丢掉44张后，把88张牌放在手中牌的最底层时，这时手中牌恰为64张。这样，再丢下去，最后留下的就是原牌顺序的第88张，接下来的难点就涉及周期问题了，是哪张牌呢？先去掉一副，再去掉大毛、小毛各一张，黑桃、红桃各十三张，即为88-54-2-1326。按照花色排列应为方块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个数。这划去的数中的最后一个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：在纸上写着一列自然数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，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。学会了抽杀问题的思路再来理解这题的设计就比较容易了。风风BLOG上的一道抽杀题：1到9000个排成一个圆圈，123点数，留1，去23。最后剩下一个是几？（风风提供）解法一：因为9000=38+2439，去掉2439个数后，在剩下的6561个数里，第一个数是（3439+1）23=3660，但是需要注意的是：到3660时并不是报的1，而是3，依次报的数是3、1、2、3、1、2.，（属于去1、3留2型，可以找到规律，最后剩下的数是中间数），在这6561个数里，正中间的是第（6561+1）2=3281个数，是3660+（3281-1）=6940.解法二：因为留1去2，3时，如果剩下的数的个数是6，18，54，162，时，最后都是剩下1，即剩下3的整数次方的2倍时，最后留下的那个数就是开头的那个。因为3724374，就要去掉900043744626，去掉4626个数时，后去掉的那个数是4626236939，下一个数6940就是剩下的4374个数的第一个，也就是最后剩下的那个数。所以最后剩