猴子选大王
猴子选大王是一个典型的编程问题,一般可用链表(可以用很大的数)或者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] : '';
}