JavaScript三種方法解決約瑟夫環(huán)問題的方法
概述
約瑟夫環(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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
layui使用templet格式化表格數(shù)據(jù)的方法
今天小編就為大家分享一篇layui使用templet格式化表格數(shù)據(jù)的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2019-09-09List Installed Software Features
List Installed Software Features...2007-06-06