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

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 "

"; $currentNode = $head; while ($currentNode->next!=$head){ $currentNode = $currentNode->next; echo '第 '.$currentNode->no.' 名小孩
'; } } } /* //创建一个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 "

";
var_dump($head);
$findNode = $childList->findNode($head,3);
echo "
";
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 "

当前有 {$n} 个小孩，从第 {$k} 个小孩开始报数，数到 {$m} 退出

";
  }
  // 数数
  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 '
退出小孩编号：' . $currentNode->no;
      }
      // 移动到下一个小孩
      $currentNode = $nextNode;
    }
    echo '
最后一个小孩编号：' . $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();