PHP解决约瑟夫环问题 PHP解决约瑟夫环问题

“约瑟夫环”是一个数学的应用问题：一群猴子排成一圈，按1,2,…,n依次编号。然后从第1只开始数，数到第m只,把它踢出圈(也可以说杀掉)，从它后面再开始数，再数到第m只，在把它踢出去…，如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。
这是比较常见的写法

/** * @param $m每次数到第几只剔除 * @param $n猴子总数 */ public function getMonkeyKing($m, $n) { //首先将所有猴子编号组成一个数组 $arr = range(1, $n); $i = 1; //用于统计循环次数 while(count($arr) > 1){ //数组个数大于1个的情况下一直执行循环 if($i % $m != 0){ //取模余数不为0的就无需踢出，压入数组尾部执行下一次循环 array_push($arr, $arr[$i-1]); } //不管是需要踢出的和不需要踢出的都需要删除原有的 unset($arr[$i-1]); $i++; } echo $arr[$i-1]; //这个就是最后的猴子大王编号 }

递归算法实现

/** * @param int[] $arr 猴子编号数组 * @param int $m第几个踢出 * @param int $current起始元素下标 */ public function getMonkeyKing($arr = [1,2,3,4,5,6], $m = 8, $current = 0) { $number = count($arr); $i = 1; //用于统计循环次数,递归一次重新赋值为1 if($number == 1){ echo '编号为' . $arr[0] .'的猴子成为了大王'; die; }else{ while($i++ < $m){ //由于$i和$current相差1，所以$current循环的结果实际代表数组当前踢出元素的下标 $current++; $current = $current % $number; //取模的原因是由于第几个踢出会出现比实际数组元素最大下标大的情况 } echo '编号为' . $arr[$current] . '的猴子被踢出 '; //从数组移除踢出元素,起始位置为$current，踢出个数为1个 array_splice($arr, $current, 1); //递归执行 $this->getMonkeyKing($arr, $m, $current); } }

线性表应用实现 【PHP解决约瑟夫环问题】最后这个算法最牛，
哦，是这样的，每个猴子出列后，剩下的猴子又组成了另一个子问题。只是他们的编号变化了。第一个出列的猴子肯定是a[1]=m(mod)n(m/n的余数)，他除去后剩下的猴子是a[1]+1,a[1]+2,…,n,1,2,…a[1]-2,a[1]-1，对应的新编号是1,2,3…n-1。设此时某个猴子的新编号是i，他原来的编号就是(i+a[1])%n。于是，这便形成了一个递归问题。假如知道了这个子问题(n-1个猴子)的解是x，那么原问题(n个猴子)的解便是：(x+m%n)%n=(x+m)%n。问题的起始条件：如果n=1,那么结果就是1。