首页 > 代码库 > 约瑟夫环问题求解

约瑟夫环问题求解

问题描述:已知n个人,分别以编号1,2,3,...n表示,围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列,求最后一个出列人的编号。

 

一般性递归算法思考:n个人围成一圈,从k开始以m为步长报数,第(k+m)-1个人出列;于是转化为n-1个人围成一圈,从(k+m-1)+1开始以m为步长报数,第(k+m)+m-1个人出列;再转化为求n-2个人围成一圈,从(k+2m-1)+1开始以m为步长报数,第(k+2m)+m-1个人出列;依次类推,直至只剩1个人围成一圈,该人出列即为问题的解。另外,在经过多轮数数出列之后,起始报数人编号和出列人编号一直在递增,它们的取值最终都可能大于n;如果此过程不中断,必然出现同一个人多次出列的情况。

 

算法实现:Josephus(n, m, k)

/**
* 约瑟夫环胜利者求值,同时也打印出圈顺序至console以便于调试观察
*
* @para int n 总人数
* @para int m 数数步长
* @para int k 起始数数者
* @return int 最后胜利者
*/

function Josephus(n, m, k) {
    let list = ‘‘;
    
    if (n < 1) {
        return 0;
    } else if (n == 1) {
        list = ‘1‘;
        console.log(list);
        return 1;
    } else {
        return dequeue(n, m, k - 1);
    }

    function dequeue(n, m, out, i = n) { //n为总人数,m为数数步长,out为前一个出列者,i为迭代控制变量
        if (i < 1) {
            list = list.slice(0,-1);
            console.log(list);
            return out; //返回最后胜利者
        } else {
            out = (out + m - 1) % n + 1; //先减1后加1以避免(out + m) % n = 0,即当前出圈者为n时,模的取值却为0,而非n;同样又保证了当前out的取值始终落在[1, n]这个区间上,而如果令out = (out + m) % (n + 1),虽能保证当前out取值合法,却存在无效的情况,比如当(out + m) % (n + 1) = 0时,当前out取值1才是有效的
            list += out + ‘,‘;
            
            i = i - 1;
            return dequeue(n, m, out, i);
        }     
    }
}

 

约瑟夫环问题求解