n-2型Josephus问题的求解方法.pdf

2023年12 月计算机应用文摘第39 卷第2 4期n-2型Josephus 问题的求解方法黄绍龙（洛阳师范学院数学科学学院,河南洛阳47 1934)摘要：文章主要利用Python语言讨论解决n-2型Josephus问题。首先，通过计算机模拟求解，其次分析问题的实质，得到递推关系并通过递归函数求解，再次，以n的取值为2 的次幂为分界点进行分组，观察解的模式来猜测解的解析式。通过数学归纳法证明了猜测的正确性，最终得出解可以通过循环左移1位获取。通过深入浅出地对n-2型Josephus问题进行分析和求解，有助于提高在数学问题思考方面的能力和水平。关键词：计算机模拟；递归函数；数学归纳法；循环左移位HUANG Shaolong中图法分类号：TP311(College of Mathematics and Science,Luoyang Normal University,Luoyang,Henan 471934,China)Abstract:The article mainly uses Python language to discuss and solve the n-2 type Josephus problem.Firstly,the solution is solved through computer simulation.Secondly,the essence of the problem is analyzedto obtain a recursive relationship and solved through a recursive function.Thirdly,the solution is groupedusing the power of n to the power of 2 as the boundary point,and the pattern of the solution is observed toguess the analytical formula of the solution.The correctness of the conjecture was proven throughmathematical induction,and the final solution can be obtained by cyclically shifting one position to the left.Analyzing and solving the n-2 type Josephus problem in a simple and easy manner can help improve onesability and level of thinking in mathematical problems.Key words:computer simulation,recursive function,mathematical induction,cyclic shift文献标识码：AMethods of solvingn-2 type Josephus problem1引言Josephus 问题是一个经典的数学问题。本文讨论的是编号从1-n的n个人围成一个圆圈,每数到2 就把他删除,直到剩下最后1人。这是Josephus问题的一种变体,本文称之为 n-2 型 Josephus 问题。通过对该问题的分析,可以将程序设计中的过程模拟、递归函数、二进制的循环移位等知识点以及数学归纳法串联起来，锻炼观察能力以及分析和综合的思维能力。2计算机模拟求解 n-2型Josephus问题假设n=12,如图1所示。本文使用笔和纸写出删除的顺序是2,4,6,8,10,12,3,7,11,5,1,因此9是幸存者。本文的目标是确定幸存者的编号W(n）。根据删除的规则，可以利用计算机模拟整个过程。以下是使用Python语言实现的程序代码及相应的注释：12111098图1由12 个人围成的圆圈M=2#每次数到2 则被删除N=41#总人数J=Fa ls e N#创建长度为N的列表,False表示“存活”,True表示“删除”R=#存储被删除的编号次序的列表m=1#记录当前数到几n=o#存储当前被删除的总人数while(n！=l e n(J）1)：#若当前存活的人数172345688大于2,则循环,使列表在逻辑上变为环结构fori in range(len(J)：#遍历整个列表if Ji=T r u e：#若访问的对象已被删除,则不计数continueelif m=M：#若访问对象存活且计数为M,则删除该对象Ji=T r u e#修改列表项的值为TrueR.append(i+1)号追加到列表R上n+=1#删除计数器加 1m+=1#数编号计数器加1if m M:#若数编号计数器超过M，则恢复为1m=1print(被删除者编号的先后顺序：）print(R)print(幸存者编号：)for i in range(len(J):的值为False,即幸存者if Ji=False:print(i+1)break3递归函数求解n-2型Josephus问题使n取不同的值,观察对应W(n)的值,从而分析是否存在某种规律。n取1一6 时运行程序得到的结果如表1所列。表1 n取1一6 时对应的W(n)的值n1W(n)1观察表1可知,W（n）总是奇数,这是因为在环绕圆圈的第一轮中删除了所有偶数。此外,如果几本身就是偶数，在一轮删除后会回到相同的起点，只是总人数减半，同时剩下的人的编号也会改变。假设最初有2 n个人，在第一轮删除后剩下的人的编号如图2 所示。接下来，编号为3的人被删除。这样就像初始时从1号人开始，只不过每个人的编号变成了当前位置编号的两倍再减去1，即：W(2n)=2W(n)-1,(n1)利用式(1)可以快速地求解较大的n对应的W(n)。例如,已知W(12)=9,那么W(24)=2W(12)-1=29-1=17。类似地,W(48)=33,且可以推断出 W(6 2m)=2m+2+1。如果初始的人数是奇数2 n+1,在环绕圆圈的第一轮中删除编号为2 n的人后,1号也将随之被删除。计算机应用文摘剩下的人的编号如图3所示。这就好像是从初始从n个人开始，但是这次他们的编号都变成当前位置编号的2 倍再加上1,即：W(2n+1)=2W(n)+1,(n1)2n-12n-3#删除对象的编图2 2 n个人在第一轮删除后的圆圈32n+12n-1#列表J中只有1个项图32 n+1个人第一轮删除后的圆圈综合以上两种情况,并结合W(1)=1可以得到任何情况下定义W的递推关系式：W(1)=1W(2n)=2W(n)-1,(n1)(W(2n+1)=2W(n)+1,(n1)式(3)展示的不是相邻项的递推关系,而是与当前问题规模减半后的递推关系,因此能够更快地计算出结果。有了递推关系，我们自然联想到使用程序设23132023年第2 4期(2)1395794513576计中的递归函数实现问题的求解。以下是利用5Python语言编写的求解函数Josephus:def josephus(n):if n=1:return 1elif n%2=0:return(2*josephus(n/2)-1)else:return(2*josephus(n-1)/2)+1)4n-2型Josephus问题的解析解(1)尽管可以根据W的递推关系式求解问题，但这仍然显得不够直接。我们追求问题的解析解,即由n直接确定W(n)的函数表达式,以加速计算结果的速度。通过递归函数可以得到对n取连续多个值时对应的W(n)值的表格。通过观察表格,可以寻找是否存在某种模式或规律，从而帮助我们猜测最终的结果。利用以下Python代码,可以生成表2。(3)2023 年第 2 4 期for i in range(1,17):print(%3s%(i),end=)print()for i in range(1,17):print(%3s%(josephus(i),end=)表 2 n 取1一16 时对应的W(n)的值45n123W(n)1131357仔细观察表2,若以2 的次幂为分界点进行分组，则组内的W(n）值呈现明显的规律性：每组的起始值为1,后边的值依次递增2。因此,把n表达为n=2+r,其中2 m是不超过n的最高次幂,r是n的剩余部分。基于此,W的递推关系式对应的解析解为：W(2+r)=2r+1,(m0且0 r2）（4)其中,2 n0且2 m+r=2n,则r为偶数,根据式（3）和归纳假设有：W(2m+r)=2W(2m-1+22r+1若m0且2 m+r=2n+1,则r为奇数,根据式(3)和归纳假设有：W(2m+r)=2W|2m1=2r+1两种情况下均可得W(2m+r)=2r+1,证毕。数学归纳法证明了（4)式的正确性,从而得到了n-2型Josephus 问题的解析解。例如,若要计算 W(130),则根据130=2 7+2 可知W(130)=22+1=5。相比数学归纳法,还有一种更简单的方式理解式(4)。说明如下：当n=2且m1时,数一圈下来剩下的人数是2m-1,仍然是偶数,所以下一圈的计数仍然是从编号为1的人开始。依此类推，每次新开始一圈的都是从编号为1的人开始,直到单独剩下编号为1的人结束,即W(2)=1。此外,也可以由式(3)的W(1)=1和W(2n)=2W(n)-1立即得出 W(2)=1。对于n=2+r,按照规则删除r个人后，剩下2 m个人,基于W(2)=1这一基本结论,可知剩下的这2m个人中第一个被计数的人将是最终的幸存者,而计算机应用文摘他的初始编号是2 r+1,从而得到W(2m+r)=2r+1。5通过循环移位得到n-2型Josephus问题的解2的次幂在寻求问题解的过程中发挥了重要的作用,所以我们很自然地想到查看 n 和W(n)的二进制89101167)-1=2(2.+1)-1=2(5)+1=2+2289表示。设n的二进制表示为n=(bmbm-1bjbo）2,即：161213 14151357911 1315n=bm2+bm-12m-+b,2+bo1每个比特b；是0 或1,并且首比特位bm是1。因为n=2m+r,0r2m,故:n=(1bm-bm-2.b,bo)2r=(0bm-bm-2 b,bo)22r=(bm-1 b m-2.b,bo0)22r+1=(bm-bm-2.b,bo1)2W(n)=(bm-1bm-2.b,bob2)2由于 W(n)=2r+1 且bm=1,可以得到:使用计算机术语，我们可以通过对n的二进制循环左移1位得到W（n）。其中，若n=130=(10000010)2,则 W(n)=W(10000010)2)=(101)2=5。因为计算机硬件实现移位操作具有很高的效率，所以式(9)给出解的速度更快。6结束语本文对 n-2 型 Josephus 问题的求解过程进行了较为详细的说明。首先,通过使用Python语言编程模拟过程变化的方法进行求解，旨在让读者对n-2型Josephus 问题有一个初步的感性认识。其次,透过问题的表象分析背后的实质，找出关于解的递推关系并利用递归函数进行求解。再次，根据已经讨论的两种方法计算连续的n较小时的若干解，观察规律从而猜(6)测解的解析式，并通过数学归纳法证明猜测的正确性。最后,基于解的解析式给出通过循环移位实现的高效求解方法。本文通过对 n-2型 Josephus 问题逐步深入的讲述方式,使读者较为自然地理解和接受计算机科学中的重要概念和方法。读者能够了解问题的来龙去脉，锻炼观察能力和思考能力,并学会利用数学工具和方法证实个人总结出的规律的正确性。参考文献：1CRAHAMRL.Concrete MathematicsM.北京：机械工业出版社,2 0 0 2.2G U T T A G JV.Py t h o n 编程导论（第2 版）M.北京：人民邮电出版社,2 0 18.作者简介：黄绍龙（198 0 一）,硕士,讲师,研究方向：计算机应用。(7)(8)(9)