/**
 * 鏈表結(jié)構(gòu)
 */
class Child{
  public $no;
  public $next=null;
  public function __construct($no=null){
    $this->no = $no;
  }
}
/**
 * 鏈表操作
 */
class CycleLink{
  private $nodeNum = 0;
  /**
   * 添加節(jié)點
   */
  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++;
  }
  /**
   * 刪除節(jié)點
   */
  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;
    }
  }
  /**
   * 獲取節(jié)點數(shù)量
   */
  public function getNodeNum(){
    return $this->nodeNum;
  }
  /**
   * 查找節(jié)點
   */
  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;
  }
  /**
   * 顯示節(jié)點
   */
  public function showNode($head)
  {
    echo "<br/><br/>";
    $currentNode = $head;
    while ($currentNode->next!=$head){
      $currentNode = $currentNode->next;
      echo '第 '.$currentNode->no.' 名小孩<br/>';
    }
  }
}
/*
//創(chuàng)建一個head頭,該head 只是一個頭，不放入數(shù)據(jù)
$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();
*/
/**
 * 約瑟夫問題
 * 設(shè)編號為1，2，...n的n個人圍坐一圈，約定編號為k（1<=k<=n）的人從1開始報數(shù)，數(shù)到m的那個人出列，
 * 它的下一位又從1開始報數(shù)，數(shù)到m的那個人又出列，依次類推，直到所有人出列為止，由此產(chǎn)生一個出隊編號的序列。
 * 并求出最后出列的人是哪個？
 */
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);  // 創(chuàng)建小孩
    echo "<br/><br/>當(dāng)前有 {$n} 個小孩，從第 {$k} 個小孩開始報數(shù)，數(shù)到 {$m} 退出<br/><br/>";
  }
  // 數(shù)數(shù)
  public function exec(){
    $currentNode = $this->childList->findNode($this->head,$this->k);  // 獲取第一個開始報數(shù)的人
    $_num = 0;  // 當(dāng)前數(shù)到的值
    $surplus_num = $this->n;
    // 開始報數(shù)
    while ($surplus_num>1) {  // 只要人數(shù)大于1，就繼續(xù)報數(shù)
      // 當(dāng)前報數(shù)值
      $_num++;
      $nextNode = $this->childList->getNextNode($this->head,$currentNode);
      // 數(shù)至第m個數(shù)，然后將其移除。報數(shù)恢復(fù)到0，重新循環(huán)。
      if( $_num==$this->m ){
        $_num = 0;
        $surplus_num--;
        // 當(dāng)前小孩退出
        $this->childList->delNode($this->head,$currentNode->no);
        echo '<br/>退出小孩編號：' . $currentNode->no;
      }
      // 移動到下一個小孩
      $currentNode = $nextNode;
    }
    echo '<br/>最后一個小孩編號：' . $currentNode->no;
  }
  // 創(chuàng)建小孩
  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();