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;
}
}<?php /*
* 环形链表 解决约瑟夫问题
*/ final class CircularLinkedList { public function addKid($n = 0, &$head = null) {
for ($i = 0; $i < $n; $i++) {
$Kid = new Kid($i + 1);
if ($i == 0) { //第一个小孩的情况
$head = $Kid; //对象赋值，是引用赋值
$head->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
出去的小孩是 --2
6