约瑟夫环的C语言实现与应用

张谞晟

（黑龙江大学，黑龙江 哈尔滨 150081）

约瑟夫环的C语言实现与应用

张谞晟

（黑龙江大学，黑龙江 哈尔滨 150081）

通过对约瑟夫环在数组，链表和递归方面算法的研究，文章比较了不同算法对时间复杂度和空间复杂度的影响，从而多层次理解约瑟夫环问题，再将约瑟夫环的算法运用到文本加密方面。

约瑟夫环；C语言；递归

据说著名犹太历史学家Josephus有过以下的故事：在罗马人占领乔塔帕特后，39个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。同样类似的问题还有很多，比如猴子选大王[1]，耶稣找叛徒这类典型问题都是所谓的约瑟夫环问题。

1 约瑟夫环问题描述

现在规定约瑟夫环问题中的圈中人数为n，而喊到m的人就得出圈，按着圆圈的顺序一次次出圈，问一开始站在哪个位置才能保证成为最后一个还在圈内的人。

2 用数组来实现约瑟夫环问题

用数组处理问题的关键就在于：①如何让数组首尾相接；②如何在有人出圈后还保持良好的循环；③处理方法就是用循环每次读一个数组成员，但用i对n取余得到的值作为读取的数组成员的下标，从而实现首尾相接；④的处理方法就是初始化数组时让每个成员的值为1，代表该人还在圈内，当循环到1时，就让报数cc加一；当循环到0时，就什么都不做，因为该人已出圈[2]。

还有关于报数CC的处理也是用的对m取余来处理。

3 用单向循环链表来实现约瑟夫环问题

同样的问题用单向循环链表来实现就不用纠结首尾相接的解决方案了，因为最后一个节点的next指向了头节点。问题变成了：①在一个节点出圈（被删除）后，如何将前一个节点和后一个节点相连；②如何判断圈内还有一个人。

①的解决方法就是在指针指向前一个节点的时候就报下一个节点的数，如果该数为m，就让前一个节点的next的next赋值给前一个节点的next，从而使得上一个节点的next指向下下个节点，来实现中间节点的删除。

②的解决方法就是在令循环跳出的条件变成当头节点next的next指向的就是头节点（除头节点以外只有一个节点时结束循环）

4 用递归来实现约瑟夫环问题

无论是用数组还是链表的方法，由于每次都得报数（存储每次出圈的过程），导致这两种算法的时间复杂度一直都处于o（nm）的状态，虽然链表法略微优于数组法，但依旧无法在n和m都很大时让算法的效率提高一个维度，这个时候递归的思想就该上场了[3]。

假设在第一次喊到m，其出圈后，接下来的序列如下（序号是从0～n-1）

M，m+1 …… n-1，0…… m-3，m-2

将这个序列从0开始重新初始化，得到的序列如下：0，1，…… n-m-1 n-m …… n-3，n-2

而每一次出圈都可以将其像这样从0开始初始化，由此，n个人的圈在第一个人出圈后，就可转换成n-1个人的出圈问题了，以此类推，最后递推到1个人的出圈问题了，此时只能是这一个人出圈，序号为0。

设未重新初始化的序列为f，初始化后的序列为g比较两个序列的对应位置编号关系可以得到f=（g+m）%n

由此可以得出递归关系式f[i]=（f[i-1]+m）%×i（i为圈内人数）。

通过递归算法，可以清楚地发现，算法的时间复杂度降到了o（n），而不再是臃肿的o（nm），但美中不足的就是该方法无法存储每次出圈的过程，但题目未要求输出每次出圈之人的编号或时间，这个算法的效率还是很高的。

5 复杂度分析

时间复杂度：由于数组与链表的实现算法需要模拟报数过程，在n人的圈中每次从1报数到m，所以这两种算法的时间复杂度为o（nm），当n与m相当大的时候程序会执行速度会很慢。而当采用递归算法时，由于不需要模拟报数过程，算法只需要递归n次，所以其时间复杂度为o（n），在n, m很大时也能较快解出答案。

空间复杂度：由于数组与链表的需要模拟报数过程，所以每次必须开辟一个个数为n的数组，使得其空间复杂度为o（n），而对于递归算法来说，每次需要开辟一个数来存储return的值，使得其空间复杂度也为o（n）。

由此可见，在相同空间复杂度的情况下，递归算法在时间复杂度上夺得头筹。所以有的问题用巧妙的数学思想来思考并设计合适的算法会降低算法的时间复杂度，但在提高程序效率的同时，可能也会牺牲一些过程数据作为代价。

6 约瑟夫环的应用

约瑟夫环这个经典的算法在实际生活中可以用来作为一种加密算法，或者也可以作为一种混淆算法。

文本加密：文本发送者首先输入一段明文，然后输入两个两个密钥k1和k2，k1是代表分组长度（约瑟夫环中人数n），k2代表原来的约瑟夫环中的m。先将明文按照分组长度k1拆分成若干段（最后一段可能小于k1），系统根据约瑟夫环的算法计算出出圈顺序后，每一个出圈的编号就对应一个分组中对应位字符的移位个数。

比如说，发送者输入的明文为“helloworld”，输入密钥k1为6，k2为4，将字符串分成两组，分别为“hellow”和“orld”根据约瑟夫环算法得到出圈顺序为4, 2, 1, 3, 6, 5，将两个分组按出圈顺序移位（h+4-〉l, e+2-〉g, l+1-〉m, l+3-〉o, o+6-〉u, w+5-〉b），得到“lgmoub”和“stmg”，最后合并得到密文“lgmoubstmg”。

密文接收者在收到密文和密钥后，同样也先按照k1分组，再根据约瑟夫环算法同样算出出圈顺序后，反向移位密文后就可解得明文。

[1]刘文锋.约瑟夫环的C语言数组的实现[J].科技信息，2010（21）：586.

[2]崔进平.约瑟夫问题的几种算法[J].泰安师专学报，2001（6）：27-29.

[3]潘大志.递推算法在扩展约瑟夫环问题中的应用[J].计算机工程与应用，2010（34）：62-63，106.

Implementation and application of C language in Joseph ring

Zhang Xusheng
（Heilongjiang University, Harbin 150081, China）

Based on the Joseph ring in the array, and the recursive algorithm of the list, the article compares the different algorithms of time complexity and space complexity, and multi-level understanding of Joseph ring problem, then applies the Joseph ring algorithm to text encryption.

Joseph ring; C language; recursion

张谞晟（1996— ），男，江苏常熟，本科，学生；研究方向：程序逆向，算法分析。