概述

約瑟夫環(huán)問題又稱約瑟夫問題或丟手絹問題，是一道經(jīng)典的算法問題。問題描述也有很多變式，但大體的解題思路是相同的。本篇將以循環(huán)鏈表、有序數(shù)組、數(shù)學(xué)遞歸三種方式來解決約瑟夫環(huán)問題。

問題描述

先來看一下什么是約瑟夫環(huán)問題？

在羅馬人占領(lǐng)喬塔帕特后，39 個(gè)猶太人與Josephus及他的朋友躲到一個(gè)洞中，39個(gè)猶太人決定寧愿死也不要被敵人抓到，于是決定了一個(gè)方式，41個(gè)人排成一個(gè)圓圈，由第1個(gè)人開始報(bào)數(shù)，每報(bào)數(shù)到第3人該人就必須，然后再由下一個(gè)重新報(bào)數(shù)，直到所有人都身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個(gè)人開始，越過k-2個(gè)人（因?yàn)榈谝粋€(gè)人已經(jīng)被越過），并殺掉第k個(gè)人。接著，再越過k-1個(gè)人，并殺掉第k個(gè)人。這個(gè)過程沿著圓圈一直進(jìn)行，直到最終只剩下一個(gè)人留下，這個(gè)人就可以繼續(xù)活著。問題是，給定了和，一開始要站在什么地方才能避免被處決。

到了今天約瑟夫環(huán)問題的描述一般變成了：

在一間房中有N個(gè)人，所有人圍成一圈順時(shí)針開始報(bào)數(shù)，每次報(bào)到M的人退出游戲。退出游戲的下一個(gè)人再次重新開始報(bào)數(shù)，報(bào)到M的人再退出，依此循環(huán)，直到游戲只剩下最后一個(gè)人，則最后一個(gè)人的編號(hào)是多少？

循環(huán)鏈表

循環(huán)鏈表的解題思路比較簡(jiǎn)單，只需要將問題描述轉(zhuǎn)換成代碼即可。房間中的N個(gè)人組成一個(gè)長(zhǎng)度為N的鏈表，首尾相接組成循環(huán)鏈表。列表中的每一項(xiàng)的值即為每個(gè)人的編號(hào)，在數(shù)到M時(shí)將該項(xiàng)(記為x)剔除，即該項(xiàng)的前一項(xiàng)的next不再指向x，而是x.next。依此規(guī)律遍歷鏈表，直至鏈表中只剩下一項(xiàng)。

下面看一下代碼實(shí)現(xiàn)。

function createList(num) {
    //鏈表節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)
    function createNode(value) {
        return {
            value: value,
            next: ''
        }
    }
    //鏈表頭節(jié)點(diǎn)
    let head = createNode(1);
    let node = head;
    //自頭節(jié)點(diǎn)之后創(chuàng)建節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系
    for (let i = 2; i <= num; i++) {
        node.next = createNode(i);
        node = node.next;
    }
    //最后一個(gè)節(jié)點(diǎn)指向頭節(jié)點(diǎn)，構(gòu)成循環(huán)鏈表
    node.next = head;
    return head;
}
function deleteListNode(num, nth) {
    //創(chuàng)建數(shù)據(jù)長(zhǎng)度為num的循環(huán)鏈表
    let node = createList(num);
    //鏈表長(zhǎng)度>1時(shí)，繼續(xù)下一輪
    while (num > 1) {
        for (let i = 1; i <= nth - 1; i++) {
            if (i == nth - 1) {
                //i為nth-1，則node.next即為第nth個(gè)節(jié)點(diǎn)。剔除node.next
                node.next = node.next.next;
                //鏈表長(zhǎng)度--
                num--;
            }
            node = node.next;
        }
    }
    //剩余的最后一個(gè)節(jié)點(diǎn)的value值即為最后一人編號(hào)
    return node.value
}
//deleteListNode(m,n)即可得到最終結(jié)果

有序數(shù)組

用有序數(shù)組來模擬循環(huán)鏈表，將數(shù)組第一次遍歷剔除完成后剩余的數(shù)組項(xiàng)組成一個(gè)新的數(shù)組，再對(duì)新數(shù)組進(jìn)行新一輪的遍歷剔除，依此循環(huán)，直到數(shù)組長(zhǎng)度為1。

下面看一下代碼實(shí)現(xiàn)。

function jhonRing(num, nth) {
    let arr = [];
    //創(chuàng)建有序數(shù)組
    for (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    //當(dāng)數(shù)組長(zhǎng)度大于nth時(shí)，數(shù)組不用循環(huán)遍歷也可找到需要剔除的數(shù)據(jù)
    while (arr.length >= nth) {
        let newArr = [];
        //將數(shù)組末尾剩下的數(shù)據(jù)轉(zhuǎn)移到新數(shù)組的前方，新一輪遍歷從生于的數(shù)據(jù)開始
        let times = arr.length - arr.length % nth;
        newArr = arr.slice(times)
        arr.slice(0, times).map((item, index) => {
            //將除了剔除數(shù)據(jù)之外的其他數(shù)據(jù)加入新的數(shù)組
            if ((index + 1) % nth !== 0) {
                newArr.push(item)
            }
        })
        arr = newArr;
    }
    //當(dāng)數(shù)組長(zhǎng)度小于nth時(shí)，數(shù)組需要循環(huán)遍歷才能找到要剔除的數(shù)據(jù)，通過取余操作可減少遍歷的次數(shù)
    while (arr.length > 1) {
        //取余獲取要剔除的數(shù)據(jù)的下標(biāo)
        let index = nth % arr.length - 1;
        //剔除數(shù)據(jù)的后半部分與前半部分組成新的數(shù)組
        let newArr = arr.slice(index + 1).concat(arr.slice(0, index));
        arr = newArr;
    }
}
//jhonRing(num, nth)即可得到最終結(jié)果

用有序數(shù)組模擬鏈表的操作看上去跟鏈表差不多，時(shí)間復(fù)雜度看上去也一樣，甚至代碼也比不上鏈表簡(jiǎn)潔，但是為什么仍然要把這個(gè)方式提出來呢？這種方法的優(yōu)勢(shì)體現(xiàn)在M>>N的情況下，有序鏈表通過取余的方式有效的減少了循環(huán)遍歷數(shù)組的次數(shù)。以N為3，M為100為例，鏈表需要循環(huán)遍歷100/3+1次，而有序數(shù)組則根據(jù)取余操作的結(jié)果100/3-1=0，直接得到了要剔除的數(shù)據(jù)下標(biāo)為0。

數(shù)學(xué)遞歸

用數(shù)學(xué)問題求解約瑟夫環(huán)問題時(shí)極易找不到一條有效的規(guī)律總結(jié)路線，下面以M=3舉例講述一下總結(jié)規(guī)律時(shí)走過的彎路。(可跳過無效的思路，直接閱讀下方的有效思路)

比較多次數(shù)據(jù)量較小時(shí)的結(jié)果(?)

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

通過舉例發(fā)現(xiàn)，最終結(jié)果并不總是在某幾個(gè)數(shù)之間，除了1，2，4以外還出現(xiàn)7，則之后的結(jié)果也有可能有類似的情況，即最終結(jié)果并不總是局限于某一個(gè)數(shù)之間。f(3,3) f(6,3) f(9,3)等N為M的倍數(shù)的情況并沒有得到相同的結(jié)果，可見最終結(jié)果與3的倍數(shù)之間并不存在某種特殊聯(lián)系。因此通過這種積累比較數(shù)據(jù)量較小時(shí)的結(jié)果來尋找規(guī)律的方案不合適。

比較前幾次剔除數(shù)據(jù)之間的關(guān)系(?)

//將N個(gè)人自1-N進(jìn)行編號(hào)
1, 2, 3, 4........N-2，N-1, N
//第一次剔除的編號(hào)為M或M%N,可總結(jié)為M%N,記為K。則第二次剔除時(shí)的序列變?yōu)?br />K+1,K+2,.......N,1,2......K-1
//則第二次剔除的編號(hào)為K+M%(N-1) || M%(N-1)-(N-K-1)
依此得到規(guī)律
當(dāng)N-(K+1)>M%(N-1)時(shí),f(n)=f(n-1)+M%(N-(n-1))
當(dāng)N-(K+1)<M%(N-1)時(shí),f(n)=M%(N-(n-1))-(N-f(n-1)-1)

依此規(guī)律計(jì)算會(huì)發(fā)現(xiàn)，沒有進(jìn)行第二圈遍歷時(shí)得到的結(jié)果是正確的，遍歷進(jìn)入第二圈之后的結(jié)果錯(cuò)誤。根本原因在于進(jìn)入第二圈之后的數(shù)據(jù)不再連續(xù)，第一圈遍歷時(shí)剔除出的數(shù)據(jù)會(huì)影響第二圈遍歷的結(jié)果，故此方案不合適。

自上而下分析問題，自下而上解決問題(?)

用遞歸的思路去分析約瑟夫環(huán)問題。以N=10，M=3為例分析。

//將10個(gè)人從0開始編號(hào)（稍后解釋為什么不能從1開始編號(hào)）
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
//將最后一個(gè)出列的人的編號(hào)記做f(10,3)
//在10個(gè)人編號(hào)后，第一個(gè)人出列后，得到新的隊(duì)列及編號(hào)
3, 4, 5, 6, 7, 8, 9, 0, 1
//為了使新隊(duì)列的編號(hào)連續(xù)，我們可以將新隊(duì)列記做A,寫作
3, 4, 5, 6, 7, 8, 9, 10%10, 11%10
//若將一個(gè)9人普通隊(duì)列記做B，寫作0,1,2,3,4,5,6,7,8的最終結(jié)果記做f(9,3),則新隊(duì)列A的結(jié)果則可以表示為(f(9,3)+3)%10
//9人隊(duì)列A是10人隊(duì)列剔除一人后得到的，則9人隊(duì)列按N=9,M=3,初始編號(hào)為3的規(guī)則進(jìn)行游戲后得到的結(jié)果必然與N=10，M=3，初始編號(hào)為0的隊(duì)列最后出列的人相同。
//故10人隊(duì)列最后出列的人編號(hào)與9人隊(duì)列A出列的人編號(hào)之間存在關(guān)系f(10,3)=(f(9,3)+3)%10

基于以上可以得到結(jié)論f(N,M)=(f(N-1,M)+M)%N。則最終編號(hào)的結(jié)果即為f(N,M)+1。
為什么編號(hào)不能從1開始呢？因?yàn)槿∮嗖僮鞯姆祷亟Y(jié)果是從0開始。

function Josephus(num,nth){
    if(num==1){
        return 0;
    }else{
        return (Josephus(num-1,nth)+nth)%num
    }
}
//Josephus(N,M)+1即為最終編號(hào)

對(duì)遞歸函數(shù)做一下優(yōu)化

function JosephusR(num,nth){
    let value = 0;
    for(let i=1;i<=num;i++){
        //此處為對(duì)i取余，上述遞歸中num也是在逐漸變小的，所以此處為i而非num
        value=(value+nth)%i;
    }
    return value+1;
}
//JosephusR(N,M)即為最終編號(hào)

總結(jié)

通過數(shù)學(xué)遞歸方式的優(yōu)化，將約瑟夫環(huán)問題的時(shí)間復(fù)雜度從最初的O(mn)降低到O(n)。通過循環(huán)鏈表的方式來解決問題確實(shí)是最快最容易想到的思路，但是這種數(shù)學(xué)遞歸的方式對(duì)解決此類算法問題來說更有思考的價(jià)值。

到此這篇關(guān)于JavaScript三種方法解決約瑟夫環(huán)問題的方法的文章就介紹到這了,更多相關(guān)JavaScript 約瑟夫環(huán)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論