概述

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

問題描述

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

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

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

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

循環(huán)鏈表

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

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

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

有序數(shù)組

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

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

function jhonRing(num, nth) {
    let arr = [];
    //創(chuàng)建有序數(shù)組
    for (let i = 1; i <= num; i++) {
        arr[i - 1] = i;
    }
    //當數(shù)組長度大于nth時，數(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;
    }
    //當數(shù)組長度小于nth時，數(shù)組需要循環(huán)遍歷才能找到要剔除的數(shù)據(jù)，通過取余操作可減少遍歷的次數(shù)
    while (arr.length > 1) {
        //取余獲取要剔除的數(shù)據(jù)的下標
        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ù)組模擬鏈表的操作看上去跟鏈表差不多，時間復(fù)雜度看上去也一樣，甚至代碼也比不上鏈表簡潔，但是為什么仍然要把這個方式提出來呢？這種方法的優(yōu)勢體現(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ù)下標為0。

數(shù)學遞歸

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

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

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;

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

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

//將N個人自1-N進行編號
1, 2, 3, 4........N-2，N-1, N
//第一次剔除的編號為M或M%N,可總結(jié)為M%N,記為K。則第二次剔除時的序列變?yōu)?br />K+1,K+2,.......N,1,2......K-1
//則第二次剔除的編號為K+M%(N-1) || M%(N-1)-(N-K-1)
依此得到規(guī)律
當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)

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

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

用遞歸的思路去分析約瑟夫環(huán)問題。以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
//為了使新隊列的編號連續(xù)，我們可以將新隊列記做A,寫作
3, 4, 5, 6, 7, 8, 9, 10%10, 11%10
//若將一個9人普通隊列記做B，寫作0,1,2,3,4,5,6,7,8的最終結(jié)果記做f(9,3),則新隊列A的結(jié)果則可以表示為(f(9,3)+3)%10
//9人隊列A是10人隊列剔除一人后得到的，則9人隊列按N=9,M=3,初始編號為3的規(guī)則進行游戲后得到的結(jié)果必然與N=10，M=3，初始編號為0的隊列最后出列的人相同。
//故10人隊列最后出列的人編號與9人隊列A出列的人編號之間存在關(guān)系f(10,3)=(f(9,3)+3)%10

基于以上可以得到結(jié)論f(N,M)=(f(N-1,M)+M)%N。則最終編號的結(jié)果即為f(N,M)+1。
為什么編號不能從1開始呢？因為取余操作的返回結(jié)果是從0開始。

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

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

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)即為最終編號

總結(jié)

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

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

最新評論