猴王算法

这是在坛子里面看到的Sina面试题，本人菜鸟，搞了一下午，和哥们搞出两种方式！但总觉得不太完美，高手能有更好的解决方案忘指点！
[php]
<?php
  /*
  13. 一群猴子排成一圈，按1，2，...，n依次编号。
  然后从第1只开始数，数到第m只,把它踢出圈，从它后面再开始数，
  再数到第m只，在把它踢出去...，如此不停的进行下去，
  直到最后只剩下一只猴子为止，那只猴子就叫做大王。
  要求编程模拟此过程，输入m、n, 输出最后那个大王的编号。
  */
function monkeyKing1($n,$m){
$monkeys=range(1,$n);
$i=0;//取出时候的坐标
$z=0;//数到M的时候停
while(($mnum=count($monkeys))>1){
  if($i==$mnum){
   $i=0;
  }
  echo 'z='.$z.'/i='.$i.'<br/>';
  $z++;
  $i++;
  if($z==$m){
   array_splice($monkeys,--$i,1);
   $z=0;
   print_r($monkeys);
   echo "<br/>";
  }
}
return($monkeys[0]);
}
echo 'King is:'.monkeyKing1(6,4);
function monkeyKing2($n,$m){
$monkeys=range(1,$n);
$i=0;
while(count($monkeys)>1){
  $i++;
  $s=key($monkeys);
  echo $i.'/'.$s.'<br/>';
  if($i==$m){
   unset($monkeys[$s]);
   print_r($monkeys);
   $i=0;
   prev($monkeys);//由于下面的NEXT不管你有没有删除都会往下跳，所以这里当删除时要往回跳，比方删除4以后我们应该让指针回到3的位置，这样指针才会再从5开始传递！
   echo "<br/>";
  }
  if(!next($monkeys)){
   reset($monkeys);
  }
}
return($monkeys[key($monkeys)]);
}
echo 'King is:'.monkeyKing2(6,4);
?>
[/php]

顶起

这是著名的亚瑟夫环问题

网上应该有很多解决方案

C++语言中也有类似的算法.....弄个循环链表,有点小忘的说...

josephus问题，用链表做其实挺好的，当然比较好的方法还是递推，O(N)算法。
[php]
function monkeyKing($n,$m)
{
    for($i=1,$next_first=1;$i<=$n;$i++)
    {
         $next_first = ($next_first+$m)%$i;
    }
    return $next_first;
}[/php]

有点小错，应该是下面这个
[php]
function monkeyKing($n,$m)
{
    for($i=1,$next_first=0;$i<=$n;$i++)
    {
         $next_first = ($next_first+$m)%$i;
    }
    return $next_first+1;
}
[/php]

晕死，这不是当年数据结构课上的例题么？？？

       泡茶钓鱼

顶起...