PHP算法之猴子选大王

猴子选大王

一群猴子要选新猴王。新猴王的选择方法是：让M只候选猴子围成一圈，从某位置起顺序编号为1~M号。从第1号开始报数，每轮从1报到N，凡报到N的猴子即退出圈子，接着又从紧邻的下一只猴子开始同样的报数。如此不断循环，最后剩下的一只猴子就选为猴王。请问是原来第几号猴子当选猴王？

输入

请输入猴子的数量m 11
请输入要排除第几个猴子n 3

输出

7

分析

常规做法又两种，一种是数组，一种是链表，（数学方法不考虑）。对于数组方法测试了两种思路，第一种是生成一个键为1-M的关联数组，值为true，退出的键值为false；另一种是值为1-M的数值数组，退出的unset；结果是使用unset效率更高些。链表是用数组模拟的链表，生成键为1-M的关联数组，值为下一位的键值，最后一位的值为1。退出了就把上一位和下一位链接起来。测试表明，使用链表的速度快于数组。

代码如下

<?php
echo "请输入猴子的数量m\n";
$m=intval(fgets(STDIN));
echo "请输入要排除第几个猴子n\n";
$n=intval(fgets(STDIN));
//1.数组方法
$start=microtime(true);
$arr=range(1,$m);
$j=0;
while (count($arr)>1){
    $tmp_arr=$arr;
    foreach ($tmp_arr as $k=>$v){
        $j++;
        if($j==$n){
            $j=0;
            unset($arr[$k]);
        }
    }
}
$end=microtime(true);
echo "数组方法：用时".($end-$start)."\t".reset($arr) ."\n";
unset($arr);

//2.链表
$start=microtime(true);
for ($i=1;$i<$m;$i++){
    $arr[$i]=$i+1;
}
$arr[$m]=1;
$i=1;
while ($i!=$arr[$i]){
    for($j=1;$j<$n-1;$j++){
        $i=$arr[$i];
    }
    $arr[$i]=$arr[$arr[$i]];
    $i=$arr[$i];
}
$end=microtime(true);
echo "链表方法：用时".($end-$start)."\t".$i."\n";

运行结果

请输入猴子的数量m
5000
请输入要排除第几个猴子n
5000
数组方法：用时1.2660729885101  3977
链表方法：用时0.77004408836365 3977