這篇文章主要介紹了PHP實現的基於單向鍊錶解決約瑟夫環問題,結合具體實例形式分析了php使用單鍊錶解決約瑟夫環問題的算法原理與相關操作技巧,需要的朋友可以參考下
本文實例講述了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 class="brush:php;toolbar:false">';
print_r($data);
echo '';
}
$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中文網其他相關文章！
