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

 　　下面為你介紹php實現猴子選大王問題算法實例。

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

　　一、問題：

　　n只猴子圍坐成一個圈，按順時針方向從1到n編號。

　　然後從1號猴子開始沿順時針方向從1開始報數，報到m的猴子出局，再從剛出局猴子的下一個位置重新開始報數，

　　如此重復，直至剩下一個猴子，它就是大王。

　　設計並編寫程序，實現如下功能：

　　(1) 要求由用戶輸入開始時的猴子數$n、報數的最後一個數$m。

　　(2) 給出當選猴王的初始編號。

　　二、解決方法：

　　?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 /** * @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));

　　補充改進算法(該算法更加簡潔明了!)：

　　?

1 2 3 4 5 6 7 8 9 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程序算法設計有所幫助。