An Example of Solving Joseph Ring Problem Based on Ring Linked List in php

In this paper, an example is given to solve Joseph's ring problem based on php ring linked list. Share it for your reference, as follows:

First, let's revisit the Joseph Ring problem: N people form a circle, count from the first one, the first M will be killed, and the last one will be left, and the rest will be killed. For example, N=6 and M=5 are killed in the order of 5, 4, 6, 2, 3 and 1.

The method of solving Joseph's ring by associative array is introduced earlier, and the method of solving Joseph's ring by ring linked list is as follows:

<?php
header("content-type:text/html;charset=utf-8");
class Child{
public $no;
public $next=null;
public function __construct($no){
$this->no=$no;
   }
}
function addChild($n,&$first){    //$n Is the number of people, create a circular linked list 
  for($i=0;$i<$n;$i++){
    $child=new Child($i+1);
    if($i==0){
    $first=$child;
    $cur=$child;
    $cur->next=$cur;
    }else{
    $cur->next=$child;
    $child->next=$first;
    $cur=$cur->next;
         }
   }
}
function showHero($first){
$cur=$first;
while($cur->next!=$first){
echo "<br/> Person number: ".$cur->no;
$cur=$cur->next;
     }
     echo "<br/> Person number: ".$cur->no;
}
function countChild($first,$m,$k){
  $cur=$first;
  for($i=0;$i<$m-1;$i++){
  $cur=$cur->next;
  }
  $j=0;
  while($cur!=$cur->next){
    if($j==$k-2){
      echo "<br/> Exit number: ".$cur->next->no;
      $cur->next=$cur->next->next;
      $cur=$cur->next;
      $j=0;
    }else{
      $cur=$cur->next;
      $j++;
    }
  }
  echo "<br/> Last column number: ".$cur->no;
}
addChild(10,$first);
showHero($first);
echo "<hr/>";
countChild($first,2,3); // No. 1 2 Individuals start counting and count to 3 Dequeue 
?>

Run results:

 Person number: 1
 Person number: 2
 Person number: 3
 Person number: 4
 Person number: 5
 Person number: 6
 Person number: 7
 Person number: 8
 Person number: 9
 Person number: 10
--------------------------------------------------------------------------------

 Exit number: 4
 Exit number: 7
 Exit number: 10
 Exit number: 3
 Exit number: 8
 Exit number: 2
 Exit number: 9
 Exit number: 6
 Exit number: 1
 Last column number: 5

For more readers interested in PHP related contents, please check the topics of this site: "PHP Data Structure and Algorithm Tutorial", "php Programming Algorithm Summary", "php String (string) Usage Summary", "PHP Array (Array) Operation Skills Complete Book", "PHP Common Traversal Algorithms and Skills Summary" and "PHP Mathematical Operation Skills Summary"

I hope this article is helpful to everyone's PHP programming.