跳到主要内容

猴子选大王

猴子选大王-dodobook.net

猴子选大王是一个典型的编程问题,一般可用链表(可以用很大的数)或者while循环(使用此办法不能用太大的数)解决。

问题描述

出题方式1
n只猴子围坐成一个圈,按顺时针方向从1到n编号。然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,
再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王。
设计并编写程序,实现如下功能:
(1) 要求由用户输入开始时的猴子数n、报数的最后一个数m。
(2) 给出当选猴王的初始编号。
出题方式2
一群猴子排成一圈,按1,2,…,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去…,
如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号。
/**
* 猴子选大王
* @param int $n 猴子数
* @param int $m 报到m的猴子出局
* @return array
*/
function getMonkeyKing($n, $m) {
// 构造数组 [1, 2, 3, ...]
$list = range(1, $n);
// 设置数组指针
$i = 0;
while (count($list) > 1) {
/**
* 遍历数组,判断当前猴子是否为出局序号,如果是则出局,否则放到数组最后。
* 比如有 "$n=4" 只猴子,数到 "$m=3" 出局。遍历数组当 "($i + 1) % 3 == 0" 则为数到3了,直接出局(从数组中删除)。
* $i + 1(数组指针从0开始,数到3时,指针为2。)
*/
if (($i + 1) % $m == 0) {
unset($list[$i]);
} else {
// 本轮未出局猴子放到数组尾部
array_push($list, $list[$i]);
// 删除本轮猴子,因为已放到数组尾部。
unset($list[$i]);
}
$i++;
}
return isset($list[$i]) ? $list[$i] : '';
}