前言
傳說在公元1 世紀的猶太戰爭中，猶太歷史學家弗拉維奧?約瑟夫斯和他的40 個同胞被羅馬士兵包圍。猶太士兵決定寧可自殺也不做俘虜，于是商量出了一個自殺方案。他們圍成一個圈，從一個人開始，數到第三個人時將第三個人殺死，然后再數，直到殺光所有人。約瑟夫和另外一個人決定不參加這個瘋狂的游戲，他們快速地計算出了兩個位置，站在那里得以幸存。寫一段程序將n 個人圍成一圈，并且第m個人會被殺掉，計算一圈人中哪兩個人最后會存活。使用循環鏈表解決該問題。
看到這個問題首先想到的是要用到循環鏈表，還有就是要計算鏈表中有多少個元素，這兩點很重要。再有就是找到當前節點和在鏈表中向前移動m個節點。下面一一分析：循環鏈表很容易實現，就是初始化的時候使鏈表的頭節點的下一個指向它自己，這樣初始化一個空節點，注意鏈表的頭不是節點。寫法如下：this.head.next = this.head;計算鏈表中有多少個元素也很簡單，只需要找到頭節點，然后往下走直到再次回到頭結點
代碼如下：
var node = this.head;var i = 0;while (!(node.next.element == "head")){ node = node.next; i++;}return i;在初始化鏈表的時候我們定義一個當前節點，將它賦值為頭節點this.currentNode = this.head; ，這樣在移動節點的時候就可以用它指向下一個節點。向前移動節點的時候有個地方需要注意，如果當前移動到頭節點上需要再向前移動一個節點this.currentNode.next.next 。
代碼如下：
while (n>0){ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--;}代碼實現
/** * 使用循環鏈表實現解決約瑟夫環問題 * *///鏈表節點function Node(element){ this.element = element; this.next = null;}//定義鏈表類function LList(){ this.head = new Node("head"); this.head.next = this.head; this.find = find; this.insert = insert; this.findPrevious = findPrevious; this.remove = remove; this.currentNode = this.head; //從鏈表當前節點向前移動n個節點 this.advance = advance; //當前鏈表中有多少個元素 this.count = count; this.display = display;}//查找節點function find(item){ var currNode = this.head; while (currNode.element != item){ currNode = currNode.next; } return currNode;}//插入新節點function insert(newElement, item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode;}//查找當前節點的上一個節點function findPrevious(item){ var currNode = this.head; while (!(currNode.next == null) && (currNode.next.element != item)){ currNode = currNode.next; } return currNode;}//移除當前節點function remove(item){ var prevNode = this.findPrevious(item); if(!(prevNode.next == null)){ prevNode.next = prevNode.next.next; }}//向前移動n個節點function advance(n){ while (n>0){ if(this.currentNode.next.element == "head"){ this.currentNode = this.currentNode.next.next; }else{ this.currentNode = this.currentNode.next; } n--; }}//當前鏈表中有多少個元素function count(){ var node = this.head; var i = 0; while (!(node.next.element == "head")){ node = node.next; i++; } return i;}//輸出所有節點function display(){ var currNode = this.head; while (!(currNode.next == null) && !(currNode.next.element == "head")){ document.write(currNode.next.element + " "); currNode = currNode.next; }}var person = new LList();person.insert('1','head');person.insert('2', '1');person.insert('3', '2');person.insert('4' , '3');person.insert('5' , '4');person.insert('6' , '5');person.insert('7' , '6');person.insert('8' , '7');person.insert('9' , '8');person.insert('10' , '9');person.display();document.write('<br>');var n = 3;while (person.count() > 2){ person.advance(n); person.remove(person.currentNode.element); person.display(); document.write('<br>');}這里我們假設有10個人，每次數到第三個人的時候這個人自殺，最后輸出的結果如下：
最后結果是約瑟夫和他的同伴一個站在隊伍的第4個，一個站在隊伍的第10個，最后只剩下他們兩個人。不知道歷史上有沒有這件事，如果真的有這件事，在這么短的時間內解決這個問題，約瑟夫真他么是個天才，不知道當時他有沒有用指針來解決這個問題，還是用普通的數組遞歸解決。
總結
以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或者工作能帶來一定的幫助，如果有疑問大家可以留言交流。
新聞熱點
疑難解答
