PHP는 Joseph 링 문제를 해결하기 위해 단방향 연결 목록을 구현합니다.

요셉 링 문제: 로마인들이 초타팟을 점령한 후, 39명의 유대인들은 요세푸스와 그의 친구들과 함께 동굴에 숨었습니다. 39명의 유대인들은 적에게 잡히느니 차라리 죽는 것이 낫다고 판단하여 자살을 결심했습니다. 방법, 41명 원을 그리며 줄을 서서 첫 번째 사람부터 세기 시작하고, 세 번째 사람이 셀 때마다 그 사람은 자살해야 하며, 모두가 자살할 때까지 다음 사람부터 다시 센다. 그러나 요세푸스와 그의 친구들은 이를 따르기를 원하지 않았습니다. 먼저 한 사람부터 시작해 k-2명을 건너고(첫 번째 사람이 넘어갔기 때문에), k번째 사람을 죽인다. 그런 다음 k-1명을 지나가고 k번째 사람을 죽입니다. 이 과정은 마침내 한 사람만 남을 때까지 원을 따라 계속되며, 이 사람은 계속 살 수 있습니다. 문제는 처형을 피하기 위해 처음에 어디에 서 있는가 하는 것입니다. 요세푸스는 친구에게 먼저 순종하는 척 해달라고 부탁했고, 자신과 친구를 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 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.