원숭이 왕 문제 알고리즘 example_php 기술의 PHP 구현

이 기사의 예에서는 PHP에서 원숭이 왕 문제 알고리즘을 구현하는 방법을 설명합니다. 참고할 수 있도록 모든 사람과 공유하세요. 구체적인 분석은 다음과 같습니다.

1. 질문:

n마리의 원숭이가 시계 방향으로 1부터 n까지 번호가 매겨진 원을 그리며 앉아 있습니다.
그런 다음 1번 원숭이부터 시계방향으로 1번부터 세기 시작합니다. m을 보고한 원숭이가 아웃되고, 방금 나온 원숭이의 다음 위치부터 다시 센다,
왕이 되는 원숭이 한 마리만 남을 때까지 이것을 반복합니다.

다음 기능을 달성하기 위한 프로그램을 설계하고 작성합니다.
(1) 사용자는 시작 $n에 원숭이 수와 보고된 마지막 숫자 $m을 입력해야 합니다.
(2) 선출된 원숭이 왕의 초기 번호를 알려주세요.

2. 해결책:

/**
 * @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));

추가적으로 개선된 알고리즘(이 알고리즘이 더 간결하고 명확해졌습니다!):

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

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

이 글이 모든 분들의 PHP 프로그램 알고리즘 설계에 도움이 되기를 바랍니다.