程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> 網頁編程 >> PHP編程 >> 關於PHP編程 >> php實現猴子選大王問題算法實例,猴子大王

php實現猴子選大王問題算法實例,猴子大王

編輯:關於PHP編程

php實現猴子選大王問題算法實例,猴子大王


本文實例講述了php實現猴子選大王問題算法。分享給大家供大家參考。具體分析如下:

一、問題:

n只猴子圍坐成一個圈,按順時針方向從1到n編號。
然後從1號猴子開始沿順時針方向從1開始報數,報到m的猴子出局,再從剛出局猴子的下一個位置重新開始報數,
如此重復,直至剩下一個猴子,它就是大王。

設計並編寫程序,實現如下功能:
(1)   要求由用戶輸入開始時的猴子數$n、報數的最後一個數$m。
(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>";//打開注釋,可以看到具體的淘汰過程
//  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程序算法設計有所幫助。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved