本文實例講述了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報起，循環下去，問最后剩下那個人的編號是多少？
代碼實現：
<?php
class 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相關內容感興趣的讀者可查看本站專題：《PHP數據結構與算法教程》、《PHP基本語法入門教程》、《php面向對象程序設計入門教程》、《php字符串(string)用法總結》及《php程序設計算法總結》
希望本文所述對大家PHP程序設計有所幫助。
【網站聲明】本站除付費源碼經過測試外，其他素材未做測試，不保證完整性，網站上部分源碼僅限學習交流，請勿用于商業用途。如損害你的權益請聯系客服QQ：2655101040 給予處理，謝謝支持。