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教程有興趣的朋友有所幫助。