Introduction to PHP's method of solving the Joseph ring problem based on one-way linked lists

This article mainly introduces PHP's implementation of solving the Joseph Ring problem based on singly linked lists, and analyzes the algorithm principles and related operating techniques of PHP using singly linked lists to solve the Joseph Ring problem based on specific examples. Friends in need can refer to the following

The example of this article describes the solution of Joseph ring problem based on one-way linked list implemented by PHP. Sharing it with everyone for your reference, the details are as follows:

Joseph Ring Question: After the Romans captured Chotapat, 39 Jews hid in a cave with Josephus and his friends , 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 lined up in a circle, starting from the first person to count, and every time the third person was counted, the person must commit suicide, and then Then the next one 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 , the next person starts from 1 again, and the cycle continues, asking 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 . &#39; &#39;;
  if($node->nextNode == $head) return;
  printNode($head, $node->nextNode);
}
function show($data){
  echo &#39;<pre class="brush:php;toolbar:false">&#39;;
  print_r($data);
  echo &#39;

'; } $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 is the detailed content of Introduction to PHP's method of solving the Joseph ring problem based on one-way linked lists. For more information, please follow other related articles on the PHP Chinese website!