這篇文章主要介紹了php實現猴子選大王問題算法,實例分析了算法的原理與解決方法,具有一定參考借鑒價值,需要的朋友可以參考下

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

一、問題：

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

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

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

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

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

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

二、解決方法：

1. /** 
2. * @param int $n 開始時的猴子數量 
3. * @param int $m 報道的最后一個數 
4. *(報到這個數的猴子被淘汰,然后下一個猴子重新從①開始報數)  
5. * @return int 猴子的初始編號  
6. */ 
7. function monkeySelectKing($n,$m) 
8. { 
9. //猴子的初始數量不能小于2 
10. if ($n<2) 
11. { 
12. return false; 
13. } 
14.  
15. $arr=range(1,$n); 
16. //將猴子分到一個數組里, 數組的值對應猴子的初始編號 
17. $unsetNum=0; 
18. //定義一個變量,記錄猴子的報數 
19.  
20. for ($i = 2; $i <=$n*$m ; $i++) 
21. //總的循環次數不知道怎么計算, 
22. { 
23. //不過因為循環中設置了return,所以$m*$len效率還可以 
24. foreach ($arr as $k => $v) 
25. { 
26. $unsetNum++; //每到一個猴子, 猴子報數+1 
27.  
28. //當猴子的報數等于淘汰的數字時:淘汰猴子(刪除數組元素) 
29. //報數歸0(下一個猴子從1開始數) 
30. if ($unsetNum==$m)  
31. { 
32. // echo "<pre>";//打開注釋,可以看到具體的淘汰過程 
33. // print_r($arr); 
34. unset($arr[$k]); 
35. //淘汰猴子  
36. $unsetNum=0; 
37. //報數歸零 
38. if (count($arr)==1) 
39. //判斷數組的長度, 如果只剩一個猴子, 返回它的值 
40. { 
41. return reset($arr); 
42. } 
43. } 
44. } 
45. } 
46. } 
47.  
48. var_dump(monkeySelectKing(6, 3)); 

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

1. function yuesefu($n,$m) {  
2. $r=0;  
3. for($i=2; $i<=$n; $i++) { 
4.  
5. $r=($r+$m)%$i;  
6. } 
7. return $r+1;  
8. }  
9. print_r(yuesefu(3,3)); 

希望本文所述對大家的php程序算法設計有所幫助。