首页 > 代码库 > 猴王算法

猴王算法


有n只猴子围成一个圈,从第一个开始数,数到第m个将其踢出,接着后面继续从1数,如此循环,直到只剩最后一只z,那只就是猴王.输入n,m.输出z

 1 //网上算法,返回序号.
 2 function monkeyKing($n, $m){
 3     
 4     $z=0; //z是王
 5     for ($j = 2; $j <= $n; $j++) $z = ($z + $m) % $j;
 6     return ++$z;
 7 }
 8 
 9 
10 //个人实现,返回数组元素
11 function monkeyKing2($n, $m){
12     
13     $array = range(1, $n);
14     $count = 1;
15     while(count($array) > 1){
16         if($count % $m == 0){
17             unset($array[key($array)]); $count = 1;
18         }else{
19             $count++;
20         }
21         if(!next($array)) reset($array);
22     }
23     return $array;
24 }

 

猴王算法