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();

运行结果：

第 1 名小孩
第 2 名小孩
第 3 名小孩
第 4 名小孩

当前有 4 个小孩，从第 1 个小孩开始报数，数到 2 退出

更多关于php相关内容感兴趣的读者可查看本站专题：《php数据结构与算法教程》、《php程序设计算法总结》、《php字符串(string)用法总结》、《php数组(array)操作技巧大全》、《php常用遍历算法与技巧总结》及《php数学运算技巧总结》

希望本文所述对大家php程序设计有所帮助。