php使用环形链表解决约瑟夫问题完整示例

本文实例讲述了php使用环形链表解决约瑟夫问题。分享给大家供大家参考，具体如下：

约瑟夫问题：

Josephu问题为：设编号为1，2，...n的n个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列，它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。并求出最后出列的人是哪个？

PHP实现环形链表以及约瑟夫问题的解决：

/** * 链表结构 */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/>';    }  }}/*//创建一个head头,该head 只是一个头，不放入数据$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个人围坐一圈，约定编号为k（1<=k<=n）的人从1开始报数，数到m的那个人出列， * 它的下一位又从1开始报数，数到m的那个人又出列，依次类推，直到所有人出列为止，由此产生一个出队编号的序列。 * 并求出最后出列的人是哪个？ */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);  // 获取第一个开始报数的人    $_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;      }      // 移动到下一个小孩      $currentNode = $nextNode;    }    echo '<br/>最后一个小孩编号：' . $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();