本文實例講述了PHP實現的基于單向鏈表解決約瑟夫環問題。分享給大家供大家參考，具體如下：
約瑟夫環問題：在羅馬人占領喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人抓到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數，每報數到第3人該人就必須自殺，然后再由下一個重新報數，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從。首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。接著，再越過k-1個人，并殺掉第k個人。這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。問題是，給定了和，一開始要站在什么地方才能避免被處決？Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
更多的類似問題是：n個人圍成圈，依次編號為1,2,..,n，現在從1號開始依次報數，當報到m時，報m的人退出，下一個人重新從1報起，循環下去，問最后剩下那個人的編號是多少？
代碼實現：
<?phpclass Node{ public $value; // 節點值 public $nextNode; // 下一個節點}function create($node, $value){ $node->value = $value;}function addNode($node, $value){ $lastNode = findLastNode($node); $nextNode = new Node(); $nextNode->value = $value; $lastNode->nextNode = $nextNode;}/* 找到最后的節點 */function findLastNode($node){ if(empty($node->nextNode)){ return $node; }else{ return findLastNode($node->nextNode); }}/* 刪除節點 必須head為引用傳值 */function deleteNode(&$head, $node, $m, $k = 1){ if($k + 1 == $m){ if($node->nextNode == $head){ $node->nextNode = $node->nextNode->nextNode; $head = $node->nextNode; return $node->nextNode; }else{ $node->nextNode = $node->nextNode->nextNode; return $node->nextNode; } }else{ return deleteNode($head, $node->nextNode, $m, ++$k); }}/* 節點數 */function countNode($head, $node, $count = 1){ if($node->nextNode == $head){ return $count; }else{ return countNode($head, $node->nextNode, ++$count); }}function printNode($head, $node){ echo $node->value . ' '; if($node->nextNode == $head) return; printNode($head, $node->nextNode);}function show($data){ echo '<pre>'; print_r($data); echo '</pre>';}$head = new Node();create($head, 1);addNode($head, 2);addNode($head, 3);addNode($head, 4);addNode($head, 5);addNode($head, 6);addNode($head, 7);addNode($head, 8);addNode($head, 9);addNode($head, 10);addNode($head, 11);addNode($head, 12);$lastNode = findLastNode($head);$lastNode->nextNode = $head;$count = countNode($head, $head);$tmpHead = $head;while ($count > 2) { $tmpHead = deleteNode($head, $tmpHead, 3, 1); $count = countNode($head, $head);}printNode($head, $head);
希望本文所述對大家PHP程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
