<?php
    //约瑟夫问题
    //环形链表

    
    class child{
        var $sn;
        var $next;
        public function __construct($sn){
            $this->sn=$sn;
        }
    }

    //创建环形链表
    
    function create(&$first,$k){
        for($i=0;$i<$k;$i++){
            if($i==0){
                //单个元素构成环形链表
                $first=new child($i+1);
                $cur=$first;
                //$cur->next=$first;
            }else{
                //多个元素构成环形链表
                $cur->next=new child($i+1);
                $cur=$cur->next;
                //$cur->next=$first;
            }
        }
        $cur->next=$first;
    }

    //遍历环形链表
    function show($first){
        $cur=$first;
        while($cur->next!=$first){
            echo $cur->sn.'<br>';
            $cur=$cur->next;
        }
        //最后一个元素
        echo $cur->sn.'<br>';

        /****或者直接全部遍历
        do{
            echo $cur->sn.'号<br>';
            $cur=$cur->next;
        }while($cur!=$first);
        *****/
    }
    //约瑟夫问题
    /*
    *param1 object first 环形链表头
    *param2    int       m     从第几个元素开始
    *param3 int    n     步长
    */
    function yuesefu(&$first,$m,$n){
        $cur=$first;
        //找出最后一个元素
        while($cur->next!=$first){
            $cur=$cur->next;
        }
        $curl=$cur;

        //从第m个元素开始
        for($i=1;$i<$m;$i++){
            $first=$first->next;
        }

        //步长为n，开始出列
        while($curl!=$first){
            for($i=1;$i<$n;$i++){
                $curl=$curl->next;
                $first=$first->next;
            }
            echo $first->sn.'号出列<br>';
            //断掉节点
            $first=$first->next;
            $curl->next=$first;
        }

        //最后剩下的元素
        echo $first->sn;

    }


    //测试

    $first=null;
    $k=8080;
    $m=26;
    $n=8;
    create($first,$k);
    //show($first);

    yuesefu($first,$m,$n);
?>