JavaScript三種方法解決約瑟夫環(huán)問題的方法
概述
約瑟夫環(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)文章希望大家以后多多支持腳本之家!
相關(guān)文章
JavaScript中校驗(yàn)銀行卡號(hào)的實(shí)現(xiàn)代碼
本文通過案例給大家介紹了js中校驗(yàn)銀行卡號(hào)的代碼,代碼小編測(cè)試過,可行。代碼簡(jiǎn)單易懂,非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友參考下吧2016-12-12基于JS實(shí)現(xiàn)移動(dòng)端左滑刪除功能
最近做個(gè)項(xiàng)目,需要實(shí)現(xiàn)移動(dòng)端左滑刪除功能,當(dāng)時(shí)js代碼將網(wǎng)上找的進(jìn)行刪減優(yōu)化,下面通過本文給大家分享基于JS實(shí)現(xiàn)移動(dòng)端左滑刪除功能,感興趣的朋友一起看看2017-07-07layui使用templet格式化表格數(shù)據(jù)的方法
今天小編就為大家分享一篇layui使用templet格式化表格數(shù)據(jù)的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-09-09JS實(shí)現(xiàn)獲取GIF總幀數(shù)的方法詳解
如何通過js在上傳前就拿到它的總幀數(shù)來判斷呢?本文就跟大家分享一種解決方案,并將其封裝成插件發(fā)布至npm倉(cāng)庫(kù),快跟隨小編一起學(xué)習(xí)一下吧2022-05-05微信小程序引入外部icon(阿里巴巴矢量圖標(biāo))的全過程
在小程序中,有默認(rèn)的圖標(biāo)icon組件,但你會(huì)發(fā)現(xiàn)它的圖標(biāo)樣式很少,可能很多時(shí)候并不能滿足我們的需求,所以這篇文章主要給大家介紹了關(guān)于微信小程序引入外部icon(阿里巴巴矢量圖標(biāo))的相關(guān)資料,需要的朋友可以參考下2022-09-09List Installed Software Features
List Installed Software Features...2007-06-06Java 正則表達(dá)式學(xué)習(xí)總結(jié)和一些小例子
字符串處理是許多程序中非常重要的一部分,它們可以用于文本顯示,數(shù)據(jù)表示,查找鍵和很多目的.在Unix下,用戶可以使用正則表達(dá)式的強(qiáng)健功能實(shí)現(xiàn)這些 目的2012-09-09