PHP實現(xiàn)的猴王算法(猴子選大王)示例

更新時間：2018年04月30日 14:00:38 作者：senlin1202

這篇文章主要介紹了PHP實現(xiàn)的猴王算法(猴子選大王),對比分析了兩種PHP猴王算法,涉及PHP數(shù)組遍歷、判斷、遞歸等相關操作技巧,需要的朋友可以參考下

本文實例講述了PHP實現(xiàn)的猴王算法。分享給大家供大家參考，具體如下：

<?php
function getKingMokey($n, $m)
{
    $monkey[0] = 0;
    //將1-n只猴子順序編號 入數(shù)組中
    for($i= 1; $i<= $n; $i++)
    {
        $monkey[$i] = $i;
    }
    $len = count($monkey);
    //循環(huán)遍歷數(shù)組元素(猴子編號)
    for($i= 0; $i< $len; $i= $i)
    {
       $num = 0;
       foreach($monkey as $key => $value)
       {
        if($value == 0) continue;
        $num++;
        $values = $value;
       }
       //若只剩一只猴子 則輸出該猴子編號(數(shù)組元素值) 并退出循環(huán)
       if($num == 1)
       {
          echo $values;
          exit;
       }
       //將第$i只猴子踢出隊伍(相應數(shù)組位置元素值設為0)
       $monkey[$i] = 0;
       //打印該猴子位置
       echo $i."";
       //設置計數(shù)器
       for($j= 1; $j<= $m; $j++)
       {
          //猴子編號加一，遍歷下一只猴子
          $i++;
          //若該猴子未被踢出隊伍,獲取下一只猴子編號
          if($monkey[$i] > 0) continue;
          //若元素值為0，則猴子已被踢出隊伍，進而循環(huán)取下一只猴子編號
          if($monkey[$i] == 0)
          {
              //取下一只猴子編號
              for($k= $i; $k< $len; $k++)
              {
                  //值為0，編號加1
                  if($monkey[$k] == 0) $i++;
                  //否則，編號已取得，退出
                  if($monkey[$k] > 0) break;
              }
          }
          //若編號大于猴子個數(shù)，則從第0只猴子開始遍歷(數(shù)組指針歸零)
          //步驟同上
          if($i == $len) $i = 0;
          //同上步驟，獲取下一只猴子編號
          if($monkey[$i] == 0)
          {
             for($k= $i; $k< $len; $k++)
             {
                  if($monkey[$k] == 0) $i++;
                 if($monkey[$k] > 0) break;
             }
          }
      }
   }
}
//猴子個數(shù)
$n = 10;
//踢出隊伍的編號間隔值
$m = 3;
//調(diào)用猴王獲取函數(shù)
getKingMokey($n, $m);
?>

運行結(jié)果：

036927185104

用遞歸的算法

$monkeys = array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10); //monkey的編號
$m = 4; //數(shù)到第幾只的那只猴子被踢出去
function killMonkey($monkeys , $m , $current = 0){
  $number = count($monkeys);
    $num = 1;
    if(count($monkeys) == 1){
      echo $monkeys[0]."成為猴王了";
      return;
    }
    else{
      while($num++ < $m){
          $current++ ;
          $current = $current%$number;
        }
        echo $monkeys[$current]."的猴子被踢掉了<br/>";
        array_splice($monkeys , $current , 1);
        killMonkey($monkeys , $m , $current);
    }
}
killMonkey($monkeys , $m);

運行結(jié)果：