猴子选大王
一群猴子要选新猴王。新猴王的选择方法是：让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
