<html>
<head>
<meta http-equiv='content-type' content='text/html;charset=utf-8'>
</head>
<body>
<h1>约瑟夫问题</h1>
<p>老师的方法：有4个小朋友，从1号从小朋友可始数2，求出最后留存留在圈子内的人编号？</p>
<?php
    class Child{
        //小朋友有一个属性next指向下一个小朋友
        public $no;
        public $next=null;
        //构造函数
        public function __construct($no){
            $this->no=$no;
        }//__contstruct
    }//Child
    //写一个函数来创建一个四个小朋友的环形链表
    //蛇无头不行，要有一个头，开始转，就是first,可动起来
    //先定义一下指向第一个小朋友的引用
    $first=null;
    $n=40;//表示有小朋友数量
    $m=3;//数几下
    $k=3;//从第几个人开始数
    //取地址符
    //此函数作用是把n个小朋友，构成一个环形链表,$first就指向了此链表的第一个小朋友
    function addChild(&$first,$n){
        $cur=$first;
        for($i=0;$i<$n;$i++){
            $child=new Child($i+1);
            //怎么构成环形链表呢？
            //一个小朋友也可以成链表
            if($i==0){
                $first=$child;
                $first->next=$child;
                $cur=$first;//$cur也在头
            }else{
                //$first->next=$child;
                //$child->next
                //头点不能动,一般用$cur
                $cur->next=$child;
                $child->next=$first;
                $cur=$cur->next;
            }//if
        }//for
    }//addChild
    //遍历所有的小朋友，把所有小朋友显示出来
    function showChild($first){
        //$cur是跑龙套的
        $cur=$first;
        while ($cur->next !=$first) {
            echo '<br>小孩子的编号是：'.$cur->no;
            $cur=$cur->next;
        }
        //当退出while时，已到了链表的最后，故而仍要处理最后一个孩子
        echo '<br>小孩子的编号是：'.$cur->no;
    }//showChild
    ///addChild($first,$n);
    //showChild($first);
    //以上的只出来了3个啊
    //从第一个小孩开始数，共数2
    function countChild($first,$m,$k){
        //思考：因为我们找到一个小朋友，从环形中删除
        //为了能删除一个辅助变量，此变量指向的小朋友，在$first的前面
        $tail=$first;
        while ($tail->next !=$first) {
            $tail=$tail->next;
        }
        //当退出while时，我们的$tail就指向最后一个小朋友
        //每移动一次，相当于，数了一下；（他本身也有一次）
        //移动二次，相当于，数了3下,他自己也数不要动
        // 从第几个人开始数，定位
        for($i=0;$i<$k-1;$i++){
            $tail=$tail->next;
            $first=$first->next;
        }
        while($tail !=$first){
            for($i=0;$i<$m-1;$i++){
                $tail=$tail->next;
                $first=$first->next;
            }//for
            echo '<br>出圈的人是：'.$first->no;
            //数完了就删除,那个$first指向的节点，出环形链表
            $first=$first->next;
            $tail->next=$first;
        }//当$tail=$first，说明只有最后一个人了
        echo '<br>最后在圈里人的是'.$tail->no;
    }//count
    addChild($first,$n);
    showChild($first);
    countChild($first,$m,$k);
exit;
    //test
    class Dog{
        public $age;
        public function __construct($age){
            $this->age=$age;
        }
    }
    function test($dog1){
        //表示用完全地址来传递
    //function test(&$dog1){
        $dog1->age=30;
    }
    $dog1=new Dog(100);
    test($dog1);
    //调用函数，就是开辟一个新栈
    echo $dog1->age;
?>
</body>
</html>