Complete example of php using ring linked list to solve Joseph problem

In this paper, an example is given to tell php how to solve Joseph problem by using ring linked list. Share it for your reference, as follows:

Joseph's question:

The problem of Josephu is: let n individuals numbered 1, 2,... n sit around once, and the agreed number is k (1 < =k < = n), the person who counts to m leaves the list, the next one digit counts from 1, the person who counts to m leaves the list again, and so on, until everyone leaves the list, thus generating a sequence of exit numbers. And find out which person is the last to leave the list?

Realization of Circular Linked List by PHP and Solution of Joseph Problem;

/**
 * 链表结构
 */
class Child{
  public $no;
  public $next=null;
  public function __construct($no=null){
    $this->no = $no;
  }
}
/**
 * 链表操作
 */
class CycleLink{
  private $nodeNum = 0;
  /**
   * 添加节点
   */
  public function addNode($head,$node)
  {
    $currentNode = $head;
    while ($currentNode->next!=null && $currentNode->next!=$head) {
      $currentNode = $currentNode->next;
    }
    $currentNode->next = $node;
    $currentNode->next->next = $head;
    $this->nodeNum++;
  }
  /**
   * 删除节点
   */
  public function delNode($head,$no)
  {
    $currentNode = $head;
    while ($currentNode->next!=$head) {
      if($currentNode->next->no==$no){
        $currentNode->next = $currentNode->next->next;
        $this->nodeNum--;
        break;
      }
      $currentNode = $currentNode->next;
    }
  }
  /**
   * 获取节点数量
   */
  public function getNodeNum(){
    return $this->nodeNum;
  }
  /**
   * 查找节点
   */
  public function findNode($head,$no){
    $node = null;
    $currentNode = $head;
    while ($currentNode->next!=$head) {
      if($currentNode->next->no==$no){
        $node = $currentNode->next;
        break;
      }
      $currentNode = $currentNode->next;
    }
    return $node;
  }
  public function getNextNode($head,$node){
    if($node->next==$head){
      return $node->next->next;
    }
    return $node->next;
  }
  /**
   * 显示节点
   */
  public function showNode($head)
  {
    echo "<br/><br/>";
    $currentNode = $head;
    while ($currentNode->next!=$head){
      $currentNode = $currentNode->next;
      echo '第 '.$currentNode->no.' 名小孩<br/>';
    }
  }
}
/*
//创建1个head头,该head 只是1个头，不放入数据
$head     = new Child();
$childList   = new CycleLink();
$child_1   = new Child(1);
$child_2   = new Child(2);
$child_3   = new Child(3);
$child_4   = new Child(4);
$childList->addNode($head,$child_1);
$childList->addNode($head,$child_2);
$childList->addNode($head,$child_3);
$childList->addNode($head,$child_4);
$childList->showNode($head);
echo "<pre>";
var_dump($head);
$findNode = $childList->findNode($head,3);
echo "<pre>";
var_dump($findNode);
$childList->delNode($head,2);
$childList->showNode($head);
echo $childList->getNodeNum();
exit();
*/
/**
 * 约瑟夫问题
 * 设编号为1，2，...n的n个人围坐1圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，
 * 它的下1位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生1个出队编号的序列。
 * 并求出最后出列的人是哪个？
 */
class Josephu{
  private $head;
  private $childList;
  private $k;
  private $m;
  private $n;
  public function __construct($n,$k,$m){
    $this->k = $k;
    $this->m = $m;
    $this->n = $n;
    $this->createList($n);  // 创建小孩
    echo "<br/><br/>当前有 {$n} 个小孩，从第 {$k} 个小孩开始报数，数到 {$m} 退出<br/><br/>";
  }
  // 数数
  public function exec(){
    $currentNode = $this->childList->findNode($this->head,$this->k);  // 获取第1个开始报数的人
    $_num = 0;  // 当前数到的值
    $surplus_num = $this->n;
    // 开始报数
    while ($surplus_num>1) {  // 只要人数大于1，就继续报数
      // 当前报数值
      $_num++;
      $nextNode = $this->childList->getNextNode($this->head,$currentNode);
      // 数至第m个数，然后将其移除。报数恢复到0，重新循环。
      if( $_num==$this->m ){
        $_num = 0;
        $surplus_num--;
        // 当前小孩退出
        $this->childList->delNode($this->head,$currentNode->no);
        echo '<br/>退出小孩编号：' . $currentNode->no;
      }
      // 移动到下1个小孩
      $currentNode = $nextNode;
    }
    echo '<br/>最后1个小孩编号：' . $currentNode->no;
  }
  // 创建小孩
  private function createList($n){
    $this->childList = new CycleLink();
    $this->head = new Child();
    for ($i=1;$i<=$n;$i++){
      $node = new Child($i);
      $this->childList->addNode($this->head,$node);
    }
    $this->childList->showNode($this->head);
  }
}
$josephu = new Josephu(4, 1, 2);
$josephu->exec();

Run results:

The first child
The second child
The third child
The fourth child

At present, there are 4 children. Start counting from the first child and count to 2 to exit

For more readers interested in PHP related contents, please check the special 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.