php實現(xiàn)猴子選大王問題算法實例
更新時間：2015年04月20日 09:22:40 作者：wujunwei928
這篇文章主要介紹了php實現(xiàn)猴子選大王問題算法,實例分析了算法的原理與解決方法,具有一定參考借鑒價值,需要的朋友可以參考下
本文實例講述了php實現(xiàn)猴子選大王問題算法。分享給大家供大家參考。具體分析如下：
一、問題：
n只猴子圍坐成一個圈，按順時針方向從1到n編號。
然后從1號猴子開始沿順時針方向從1開始報數(shù)，報到m的猴子出局，再從剛出局猴子的下一個位置重新開始報數(shù)，
如此重復，直至剩下一個猴子，它就是大王。
設計并編寫程序，實現(xiàn)如下功能：
（1） 要求由用戶輸入開始時的猴子數(shù)$n、報數(shù)的最后一個數(shù)$m。
（2） 給出當選猴王的初始編號。
二、解決方法：
/**
* @param int $n 開始時的猴子數(shù)量
* @param int $m 報道的最后一個數(shù)
*(報到這個數(shù)的猴子被淘汰,然后下一個猴子重新從①開始報數(shù))
* @return int 猴子的初始編號
*/
function monkeySelectKing($n,$m)
{
//猴子的初始數(shù)量不能小于2
if ($n<2)
{
return false;
}
$arr=range(1,$n);
//將猴子分到一個數(shù)組里, 數(shù)組的值對應猴子的初始編號
$unsetNum=0;
//定義一個變量,記錄猴子的報數(shù)
for ($i = 2; $i <=$n*$m ; $i++)
//總的循環(huán)次數(shù)不知道怎么計算,
{
//不過因為循環(huán)中設置了return,所以$m*$len效率還可以
foreach ($arr as $k => $v)
{
$unsetNum++; //每到一個猴子, 猴子報數(shù)+1
//當猴子的報數(shù)等于淘汰的數(shù)字時:淘汰猴子(刪除數(shù)組元素)
//報數(shù)歸0(下一個猴子從1開始數(shù))
if ($unsetNum==$m)
{
// echo "<pre>";//打開注釋,可以看到具體的淘汰過程
// print_r($arr);
unset($arr[$k]);
//淘汰猴子
$unsetNum=0;
//報數(shù)歸零
if (count($arr)==1)
//判斷數(shù)組的長度, 如果只剩一個猴子, 返回它的值
{
return reset($arr);
}
}
}
}
}
var_dump(monkeySelectKing(6, 3));
補充改進算法（該算法更加簡潔明了?。?/p>
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程序算法設計有所幫助。
相關(guān)文章
PHP數(shù)據(jù)庫操作四：mongodb用法分析
這篇文章主要介紹了PHP數(shù)據(jù)庫操作mongodb用法,結(jié)合實例形式較為詳細的分析了MongoDB的功能、安裝、基本命令、使用方法及相關(guān)注意事項,需要的朋友可以參考下2017-08-08
這篇文章主要介紹了PHP GD庫生成圖像的幾個函數(shù)總結(jié),即imagegif、imagejpeg、imagepng、imagewbmp幾個生成圖片的函數(shù),需要的朋友可以參考下2014-11-11
最近，在用PHP+MySQL編寫一個小程序的時候，發(fā)現(xiàn)一個問題：錄入數(shù)據(jù)庫的時間與實際時間差8小時，這和中國位于的東8區(qū)是符合的。由于數(shù)據(jù)庫時間是由PHP寫入的，那問題就出現(xiàn)在PHP中了。2015-07-07
php使用自定義函數(shù)實現(xiàn)漢字分割替換功能示例
這篇文章主要介紹了php使用自定義函數(shù)實現(xiàn)漢字分割替換功能,結(jié)合實例形式分析了php針對漢字的遍歷、轉(zhuǎn)換與分割操作相關(guān)技巧,需要的朋友可以參考下2017-01-01
這篇文章主要介紹了通過php刪除xml文檔內(nèi)容的方法,實例分析了兩種刪除XML文檔的情況,并配有完整的注釋,非常具有實用價值,需要的朋友可以參考下2015-01-01
在閱讀PHP源碼和學習PHP擴展開發(fā)的過程中，我接觸到大量含有“TSRM”字眼的宏。通過查閱資料，知道這些宏與Zend的線程安全機制有關(guān)，而絕大多數(shù)資料中都建議按照既定規(guī)則使用這些宏就可以，而沒有說明這些宏的具體作用2011-11-11
在ASP中,我們可以使用Server.Transfer來實現(xiàn)在服務器端重定向,PHP中雖然沒有這樣的函數(shù),但是要實現(xiàn)類似的跳轉(zhuǎn)也不難2012-08-08
本篇文章是對PHP數(shù)據(jù)加密進行了詳細的分析介紹，需要的朋友參考下2013-06-06
本文主要分享了php根據(jù)用戶名和手機號查詢是否存在手機號碼的代碼，具有很好的參考價值，下面跟著小編一起來看下吧2017-02-02
PHP刪除二維數(shù)組中相同元素及數(shù)組重復值的方法示例
這篇文章主要介紹了PHP刪除二維數(shù)組中相同元素及數(shù)組重復值的方法,涉及php針對數(shù)組的遍歷、判斷、比較等相關(guān)操作技巧,需要的朋友可以參考下2017-05-05