2019年2月25日17:29:17

Josephus有过的故事：39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓。于是决定了自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀。然后下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。

抽象出的问题是 N个人围成一圈，从第S个人开始报数，报到C的人出圈，从出去的人的下一位，继续从下一任开始重新报数，报到m的人出圈；如此往复，直到所有人出圈。

final class Kid {    public $no;    public $next = null;    public function __construct($no) {        $this->no = $no;    }}

     next = $Kid; //自己指向自己                $current = $head; //对象赋值，是引用赋值            } else {                $current->next = $Kid;                $Kid->next = $head;//                //继续指向下一个                $current = $current->next;            }        }    }    /*     * $start 从几开始     * $count 数到几就出圈     */    public function play(Kid $head, $start, $count) {        $current = $head;        //移动指针从$start 移动到        while (1) {            if ($current->no == $start) {                break;            }            $current = $current->next;        }//        p($current);//        pp($this->countKids($current));//        $all = $this->countKids($current);        while ($current->next != $current->next->next) {            //少移动一位，方便一处节点            for ($i = 1; $i < $count; $i++) {                $current = $current->next;            }            //去除节点//            p($current);            p('出去的小孩是  --' . $current->next->no);            $current->next = $current->next->next;//            p($current);            //移动指针,移到删除节点的下一位就是重新数数的那个节点            $current = $current->next;        }        p($current->no);    }    public function countKids(Kid $head) {        $current = $head;        $count = 1;        while ($head->no != $current->next->no) {            $count++;            $current = $current->next;        }        return $count;    }}

调用

$CircularLinkedList = new CircularLinkedList();$CircularLinkedList->addKid(10, $head);$CircularLinkedList->play($head, 3, 2);

结果

出去的小孩是  --5出去的小孩是  --8出去的小孩是  --1出去的小孩是  --4出去的小孩是  --9出去的小孩是  --3出去的小孩是  --10出去的小孩是  --7出去的小孩是  --26