PHP implements one-way linked list to solve Joseph ring problem

Josephus Ring Question: After the Romans captured Chotapat, 39 Jews hid in a cave with Josephus and his friends. The 39 Jews decided that they would rather die than be caught by the enemy, so they decided on a way to commit suicide. 41 people line up in a circle, and counting starts with the first person. Every time the third person is counted, that person must commit suicide, and then the next person counts again until everyone commits suicide. However, Josephus and his friends did not want to comply. First start with one person, cross k-2 people (because the first person has been crossed), and kill the k-th person. Then, go past k-1 people and kill the k-th person. This process continues along the circle until finally only one person remains, and this person can continue to live. The question is, given and , where do you stand initially to avoid being executed? Josephus asked his friend to pretend to obey first. He placed his friend and himself in the 16th and 31st positions, thus escaping the death game.

More similar problems are: n people form a circle, numbered 1, 2,...,n, now starting from number 1, counting in sequence, when m is reported, the person who reported m exits, and the next person Start again from 1, continue the cycle, and ask what is the number of the last remaining person?

Code implementation:

<?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);

The above has introduced how to implement a one-way linked list in PHP to solve the Joseph ring problem, including aspects of the problem. I hope it will be helpful to friends who are interested in PHP tutorials.