环形链表解决约瑟夫问题

php代码：

有道智云AI开放平台

有道智云AI开放平台

下载

//环形链表
    /*
        解决约瑟夫问题
        设定编号1-n个人 约定起始编号k的人从1开始报数，报到m的那个人出列。他的下一位又从1开始报数，数到M的那个人又出列，
        依次类推，直到所有人都出列为止，求出列顺序，和最后出列编号
     
    */
     
 
     
     
header("content-type:text/html;charset=utf-8");
    class Child{
        public $no;
        public $next=null;
      
        public function __construct($no){
        $this->no=$no;
        }
    }
     
    function addChild(&$first,$n)
    {
        $cur=null;
        for($i=0;$i<=$n-1;$i++){
            $child = new child($i+1);
            if($i==0){
                $first = $child;
                $first->next=$child;
                $cur=$first;
            }else{
                $cur->next=$child;
                $child->next=$first;
                $cur=$cur->next;
            }   
             
        }
    }
     
    function showChild($first){
         
        $cur=$first;
         
        while($cur->next != $first){
            echo $cur->no;
            $cur=$cur->next;
        }
        echo $cur->no;
    }
     
     
    function countChild($first,$m,$k)
    {
        $tail=$first;
        //考虑从第几个孩子开始
        for($i=0;$i<$m-1;$i++){
            $tail=$tail->next;
        }
         
        while($tail->next!=$tail) //剔除到链表中只有一个元素为止
        {
            for($i=0;$i<$k-1;$i++){
                $cur=$tail;//记录他的前一个位置
                $tail=$tail->next;
            }
            echo '出列人'.$tail->no;
            $cur->next=$tail->next;
            $tail=$tail->next;
        }
        echo '111'.$tail->no;
    }
     
addChild($first,10);
showChild($first);
echo "
";
countChild($first,2,3); //第二个小孩开始数，数到三出列