Scratch编程学算法解约瑟夫环问题之模拟法

欢迎大家来到IT世界,在知识的湖畔探索吧!

Scratch编程学算法解约瑟夫环问题之模拟法

一、问题的提出

上一篇头条文介绍了解约瑟夫环问题的递推公式算法，优点是高效简洁。缺点是只能求出最后一个幸存者顺序号。有一些约瑟夫问题可能需要更多的“幸存者”顺序号。

例如我们把约瑟夫问题改一个说法，

公元1世纪，犹太历史学家弗拉维奥·约瑟夫斯（Flavius Josephus）和他的两个铁杆兄弟在犹太反抗罗马的战争中，与另外38名犹太人被困于洞穴中。为避免被俘受辱，他们约定围成一圈，从第1人开始轮流报数，每数到第3人便将其杀死，最后剩下的人自杀。但约瑟夫及其兄弟不想自杀，于是通过数学计算找到最后出局的3个位置，从而幸存下来。

这就需要把最后三个出局者的编号算出来，便于他们三兄弟去站位。 如下图的第41,40和39次出局者的顺序号31、16和35，如下图所示：

欢迎大家来到IT世界,在知识的湖畔探索吧!

这就需要我们编程模拟这个逐步出局（被杀）的过程，把全部的出局者的编号求出来。

二、模拟法的算法分析

（一）、假设总人数为n,每次报数的间隔为m, 建立一个编号变量，存放出局者在这个的 圆圈中的位置顺序号（列表编号），

有 n 个活人围成一圈，顺序号为 1, 2, 3，…, n。

从编号 0 的人开始报数，每报数到 m 时，即编号增加（m-1），该人被淘汰；把这个人的顺序号依次存放在一个列表或字符串变量里面。剩余的n-1个人继续从下一个人开始报数，直到最后剩下1人，求其寻序号。

注意由于是圆排列，要注意编号增加（m-1）以后，可能值超出当前的活人总数n，因此需要取模运算防止越界:(编号+（m-1）)%n.

另外，如果把出局者剔除以后，列表中的编号数就指向了下一个人的顺序号。就可以继续将它加上（m-1）并取余。

三、约瑟夫问题递推算法的Scratch实现

有了前面的算法分析，，建立相应的列表和变量，编程就非常简洁。

（一）建立最初的活人顺序号列表。

（二）用直到循环实现依次将出局者顺序号放入列表““出局顺序”的Scratch程序代码：

（三）运行结果：

n=41,m=3

n=8,m=3

四、总结和拓展

总结：1模拟法的优点是把整个出局（死去）的全过程呈现出来。便于解决与约瑟夫环相关的一些拓展问题。比如就可以帮助约瑟夫和的两个铁哥们计算出最后出局的顺序号35,16,31.

2.注意编号变量实际是对应的人在当前列表中的编号，而不是列表中该项的内容（顺序号）。

拓展：1.如果在后面的循环程序中可否用计数循环？

2.如果编号变量不是从0开始，而是从1开始，我们在取余计算“编号”时需要注意什么？

3.请解决【报数游戏】问题：

由蓝桥杯编程竞赛题改编，位置编号角色和位置状态圆圈的角色分别由8个改为一个角色图章（或克隆）8次实现。

【规则】8个人（5男和3女），围成一个圆圈，给定一个数字n （2≤n≤5）)。从第一个开始依次报数，当报数为n时，这个人离开圆圈。然后下一个从1开始报数,再次报到n的人离开圆圈，如此循环进行游戏直到仅余5个人为止。请问游戏开始时，采用怎样的排法，才能使每次离开圆圈的都是女生，剩余的5人都是男生。例如给定的数字为3时，每次报到3的人离开圆圈。蓝色圆圈代表男生;红色圆圈代表女生。

编程实现: 报数游戏(初始由1开始顺时针报数)。

【具体要求】（1）点击绿旗，小猫说:“男生5人，女生3人，共8人。”（2） （5）对n=2，3，4，5，每隔2秒后，小猫说: “报数为n”;按照男生为蓝色，女生为红色，每次报到n的人离开圆圈的情况下，在舞台中正确呈现男生与女生在此轮游戏中的初始位置，使得3轮报数后留下的5人都是男生;（6）2秒后，程序结束。

【算法要点】实质上这是一个“约瑟夫环问题”。

（1）先建一个8个元素都是“男”的游戏者列表。由于到最后剩5个男生为止，实际是淘汰3轮或者找够3个出局者（女生）就结束；

（2）对于给定的n，某人虽然出局，但要保留他的初始位置不变，因此需要一个位置指针“序号”，遍历游戏者列表，另外需要一个报数“计数器”，从0开始，按规则累加达到n，这个位置就是出局者，标记成“女”，下一轮计数器清零，从下一个位置开始按规则计数到n个,标记出局者（女）……,所谓规则，就是如果该位置已经明确是出局者（女），就要跳过（计数器不增加1）。

（3）注意这是一个圆排列问题，8的下一个位置是1。n比较大时，某一轮的“序号”递增后可能超过人数8，这时序号对应的位置应该是序号8。

（4）如果用克隆，为了正确显示编号和位置状态，需要给这两个角色分别设置私有变量“造型号”和“状态序号”，克隆前就要给私变依次赋予循环变量值i或j，便于后面根据私变选择造型或者找到对应序号是否男生。传递消息用变量。

图章版“位置状态”角色的脚本和报数n=5的显示结果。