网站制作学习网经验与学习→正文:猴子选大王-算法
字体:

猴子选大王-算法

经验与学习 2010/8/4 11:19:09  点击:不统计

转载%77%77%77请%2E%66%6F%72%61%73%70%2E%63%6E注明
一群猴子排成一圈,按1,2,...,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去...,如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入m、n, 输出最后那个大王的编号.

据说是新浪面试题.废了很大的劲,没有想出来.一下是网络答案.供学习参考
第一种答案
<?
function get($m,$n){
$a=array();
for($i=1;$i<$m+1;$i++){$a[]=$i;}//首先将m个猴子按数组排列,1到m.
$i=0;//设置指针从0开始,实际为第一个猴子,1则为第二个猴子
while(count($a)>1){//如果数组个数大于1则进行循环
  if(($i+1)%$n==0){//如果当前指针+1也就是第$i个猴子,如果第i个猴子是n的倍数则需要踢出
  unset($a[$i]);
  }else{//如果不踢出,放到最后也就是将数组序号增加1
  array_push($a,$a[$i]);
  unset($a[$i]);//取消开始的序号
  }
  $i++;//将指针下移
 }
 return $a;
}
var_dump(get(5,1));
//还有一种是高手算法,一点也不理解.
function kickMonkey ($n,$m)
{$s = 0;
for ($i=2; $i <=$n; $i++){
 $s = ($s+$m)%$i;  
 } 
 $win = $s+1;
 return $win;
}
echo kickMonkey(5,2);
?>
看高手写的代码,望其项背啊!
原载于:文章来源:www.forasp.cn网站制作学习

·上一篇:sqlserver时间格式转换 >>    ·下一篇:WML >>
推荐文章
最新文章