JavaScript三种方法解决约瑟夫环问题的方法

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› JavaScript›JavaScript编程经验

原作者: [db:作者] 来自: [db:来源] 收藏邀请

概述

约瑟夫环问题又称约瑟夫杀人问题或丢手绢问题，是一道经典的算法问题。问题描述也有很多变式，但大体的解题思路是相同的。本篇将以循环链表、有序数组、数学递归三种方式来解决约瑟夫环问题。

问题描述

先来看一下什么是约瑟夫环问题？

在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决。

到了今天约瑟夫环问题的描述一般变成了：

在一间房中有N个人，所有人围成一圈顺时针开始报数，每次报到M的人退出游戏。退出游戏的下一个人再次重新开始报数，报到M的人再退出，依此循环，直到游戏只剩下最后一个人，则最后一个人的编号是多少？

循环链表

循环链表的解题思路比较简单，只需要将问题描述转换成代码即可。房间中的N个人组成一个长度为N的链表，首尾相接组成循环链表。列表中的每一项的值即为每个人的编号，在数到M时将该项(记为x)剔除，即该项的前一项的next不再指向x，而是x.next。依此规律遍历链表，直至链表中只剩下一项。

下面看一下代码实现。

function createList(num) {
    //链表节点的数据结构
    function createNode(value) {
        return {
            value: value,
            next: ''
        }
    }
    //链表头节点
    let head = createNode(1);
    let node = head;
    //自头节点之后创建节点之间的关联关系
    for (let i = 2; i <= num; i++) {
        node.next = createNode(i);
        node = node.next;
    }
    //最后一个节点指向头节点，构成循环链表
    node.next = head;
    return head;
}
function deleteListNode(num, nth) {
    //创建数据长度为num的循环链表
    let node = createList(num);
    //链表长度>1时，继续下一轮
    while (num > 1) {
        for (let i = 1; i <= nth - 1; i++) {
            if (i == nth - 1) {
                //i为nth-1，则node.next即为第nth个节点。剔除node.next
                node.next = node.next.next;
                //链表长度--
                num--;
            }
            node = node.next;
        }
    }
    //剩余的最后一个节点的value值即为最后一人编号
    return node.value
}
//deleteListNode(m,n)即可得到最终结果

有序数组

用有序数组来模拟循环链表，将数组第一次遍历剔除完成后剩余的数组项组成一个新的数组，再对新数组进行新一轮的遍历剔除，依此循环，直到数组长度为1。

下面看一下代码实现。

function jhonRing(num, nth) {
    let arr = [];
    //创建有序数组
    for (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    //当数组长度大于nth时，数组不用循环遍历也可找到需要剔除的数据
    while (arr.length >= nth) {
        let newArr = [];
        //将数组末尾剩下的数据转移到新数组的前方，新一轮遍历从生于的数据开始
        let times = arr.length - arr.length % nth;
        newArr = arr.slice(times)
        arr.slice(0, times).map((item, index) => {
            //将除了剔除数据之外的其他数据加入新的数组
            if ((index + 1) % nth !== 0) {
                newArr.push(item)
            }
        })
        arr = newArr;
    }
    //当数组长度小于nth时，数组需要循环遍历才能找到要剔除的数据，通过取余操作可减少遍历的次数
    while (arr.length > 1) {
        //取余获取要剔除的数据的下标
        let index = nth % arr.length - 1;
        //剔除数据的后半部分与前半部分组成新的数组
        let newArr = arr.slice(index + 1).concat(arr.slice(0, index));
        arr = newArr;
    }
}
//jhonRing(num, nth)即可得到最终结果

用有序数组模拟链表的操作看上去跟链表差不多，时间复杂度看上去也一样，甚至代码也比不上链表简洁，但是为什么仍然要把这个方式提出来呢？这种方法的优势体现在M>>N的情况下，有序链表通过取余的方式有效的减少了循环遍历数组的次数。以N为3，M为100为例，链表需要循环遍历100/3+1次，而有序数组则根据取余操作的结果100/3-1=0，直接得到了要剔除的数据下标为0。

数学递归

用数学问题求解约瑟夫环问题时极易找不到一条有效的规律总结路线，下面以M=3举例讲述一下总结规律时走过的弯路。(可跳过无效的思路，直接阅读下方的有效思路)

比较多次数据量较小时的结果(❌)

N=1时，f(1,3)=1;
N=2时，f(2,3)=2;
N=3时，f(3,3)=2;
N=4时，f(4,3)=1;
N=5时，f(5,3)=4;
N=6时，f(6,3)=1;
N=7时，f(7,3)=4;
N=8时，f(8,3)=7;
N=9时，f(9,3)=1;
N=10时，f(10,3)=4;

通过举例发现，最终结果并不总是在某几个数之间，除了1，2，4以外还出现7，则之后的结果也有可能有类似的情况，即最终结果并不总是局限于某一个数之间。f(3,3) f(6,3) f(9,3)等N为M的倍数的情况并没有得到相同的结果，可见最终结果与3的倍数之间并不存在某种特殊联系。因此通过这种积累比较数据量较小时的结果来寻找规律的方案不合适。

比较前几次剔除数据之间的关系(❌)

//将N个人自1-N进行编号
1, 2, 3, 4........N-2，N-1, N
//第一次剔除的编号为M或M%N,可总结为M%N,记为K。则第二次剔除时的序列变为
K+1,K+2,.......N,1,2......K-1
//则第二次剔除的编号为K+M%(N-1) || M%(N-1)-(N-K-1)
依此得到规律
当N-(K+1)>M%(N-1)时,f(n)=f(n-1)+M%(N-(n-1))
当N-(K+1)<M%(N-1)时,f(n)=M%(N-(n-1))-(N-f(n-1)-1)

依此规律计算会发现，没有进行第二圈遍历时得到的结果是正确的，遍历进入第二圈之后的结果错误。根本原因在于进入第二圈之后的数据不再连续，第一圈遍历时剔除出的数据会影响第二圈遍历的结果，故此方案不合适。

自上而下分析问题，自下而上解决问题(✅)

用递归的思路去分析约瑟夫环问题。以N=10，M=3为例分析。

//将10个人从0开始编号（稍后解释为什么不能从1开始编号）
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
//将最后一个出列的人的编号记做f(10,3)
//在10个人编号后，第一个人出列后，得到新的队列及编号
3, 4, 5, 6, 7, 8, 9, 0, 1
//为了使新队列的编号连续，我们可以将新队列记做A,写作
3, 4, 5, 6, 7, 8, 9, 10%10, 11%10
//若将一个9人普通队列记做B，写作0,1,2,3,4,5,6,7,8的最终结果记做f(9,3),则新队列A的结果则可以表示为(f(9,3)+3)%10
//9人队列A是10人队列剔除一人后得到的，则9人队列按N=9,M=3,初始编号为3的规则进行游戏后得到的结果必然与N=10，M=3，初始编号为0的队列最后出列的人相同。
//故10人队列最后出列的人编号与9人队列A出列的人编号之间存在关系f(10,3)=(f(9,3)+3)%10

基于以上可以得到结论f(N,M)=(f(N-1,M)+M)%N。则最终编号的结果即为f(N,M)+1。
为什么编号不能从1开始呢？因为取余操作的返回结果是从0开始。

function Josephus(num,nth){
    if(num==1){
        return 0;
    }else{
        return (Josephus(num-1,nth)+nth)%num
    }
}
//Josephus(N,M)+1即为最终编号

对递归函数做一下优化

function JosephusR(num,nth){
    let value = 0;
    for(let i=1;i<=num;i++){
        //此处为对i取余，上述递归中num也是在逐渐变小的，所以此处为i而非num
        value=(value+nth)%i;
    }
    return value+1;
}
//JosephusR(N,M)即为最终编号