PHP implementation example of monkey king problem algorithm, monkey king

PHP implementation example of monkey king problem algorithm, monkey king_PHP tutorial

WBOY

Release： 2016-07-13 09:56:32

Original

1507 people have browsed it

An example of the monkey-choosing-king problem algorithm implemented in php, Monkey King

This article describes an example of the monkey-choosing-king problem algorithm implemented in php. Share it with everyone for your reference. The specific analysis is as follows:

1. Question:

n monkeys sit in a circle, numbered from 1 to n in a clockwise direction.
Then start counting from monkey No. 1 in a clockwise direction from 1. The monkey that reports m is out, and then restart counting from the next position of the monkey that just got out,
Repeat this until there is only one monkey left, which is the king.

Design and write programs to achieve the following functions:
(1) The user is required to input the starting number of monkeys $n and the last number reported $m.
(2) Give the initial number of the elected Monkey King.

2. Solution:

/**
 * @param int $n 开始时的猴子数量
 * @param int $m 报道的最后一个数
 *(报到这个数的猴子被淘汰,然后下一个猴子重新从①开始报数) 
 * @return int 猴子的初始编号 
 */
function monkeySelectKing($n,$m)
{
 //猴子的初始数量不能小于2
 if ($n<2)
 {
 return false;
 }
 
 $arr=range(1,$n);
 //将猴子分到一个数组里, 数组的值对应猴子的初始编号
 $unsetNum=0;
 //定义一个变量,记录猴子的报数
 
 for ($i = 2; $i <=$n*$m ; $i++)
 //总的循环次数不知道怎么计算,
 {
 //不过因为循环中设置了return,所以$m*$len效率还可以
 foreach ($arr as $k => $v)
 {
  $unsetNum++; //每到一个猴子, 猴子报数+1
 
 //当猴子的报数等于淘汰的数字时:淘汰猴子(删除数组元素)
 //报数归0(下一个猴子从1开始数)
  if ($unsetNum==$m) 
  {
//  echo "<pre class="brush:php;toolbar:false">";//打开注释,可以看到具体的淘汰过程
//  print_r($arr);
  unset($arr[$k]);
 //淘汰猴子  
  $unsetNum=0;
 //报数归零
  if (count($arr)==1)
 //判断数组的长度, 如果只剩一个猴子, 返回它的值
  {
   return reset($arr);
  }
  }
 }
 }
}
 
var_dump(monkeySelectKing(6, 3));

Copy after login

Supplementary improved algorithm (this algorithm is more concise and clear!):

function yuesefu($n,$m) { 
  $r=0; 
  for($i=2; $i<=$n; $i++) {

      $r=($r+$m)%$i; 
  }
  return $r+1; 
} 
print_r(yuesefu(3,3));

Copy after login

I hope this article will be helpful to everyone’s PHP program algorithm design.