【PHP算法】一群猴子排成一圈,m,n猴子选大王算法

怎么说呢，平时用不到，面试可能会考，php经典算法，猴子选大王

问题：

一群猴子排成一圈，按1，2，...，n依次编号。

然后从第1只开始数，数到第m只,把它踢出圈，

然后从它后面再开始数，再数到第m只，在把它踢出去...，

如此不停的进行下去，直到最后只剩下一只猴子为止，那只猴子就叫做大王。

思路分析：（遇到这种有变量的最好先假定具体数值，方便分析）

假定有6只猴子排成一圈，我们把圈给它剪开，那么编号就是1，2，3，4，5，6；排成一排

假定数到第2只把它剔除圈，那么为了维持圈循环的状态，当你数到1的时候，此时1应该放在6的后面，即：2,3,4,5,6,1

那么数到2的时候，剔除，应该就是：3,4,5,6,1

数到3的时候不剔除应该是：4,5,6,1,3

数到4的时候剔除：5,6,1,3

数到5的时候不剔除：6,1,3,5

数到6的时候剔除：1,3,5

数到7的时候不剔除：3,5,1

数到8的时候剔除：5,1

数到9的时候不剔除：1,5

数到10的时候剔除：5

最红猴王编号为：5

判断是否剔除：从以上规律，我们可以用数到几除以m取余，如果余数为0代表剔除，否则为不剔除，比如m为2，你数到1的时候那么就不剔除，数到2的时候余数为0，就要剔除....

编码：

function monkeyKing($n,$m){
    $monkeys = range(1, $n); //函数创建一个包含指定范围的元素的数组
    $i = 0;
    while (count($monkeys) > 1){
        if (($i+1)%$m == 0) {  //$i+1是指实际上数数的值，实际数数是1，2，3，4，5而$i是这些值的下标，
            //所以要加1得到实际的值与第m只相除余0才是数到第m只
            unset($monkeys[$i]);//数到第m只就删掉
        }else{
            array_push($monkeys, $monkeys[$i]);//不是第m只的放到最后
            unset($monkeys[$i]); //删除原来的占位
        }
        $i ++;
    }
    return $monkeys; //输出数组中的当前元素的值
}

$monkey = monkeyKing(6, 2);
print_r($monkey);
//结果为array('10' => 5) ,代表一共数到了10，最后剩下5号