php解決約瑟夫環(huán)算法實(shí)例分析
本文實(shí)例講述了php解決約瑟夫環(huán)算法。分享給大家供大家參考，具體如下：
今天偶遇一道算法題
“約瑟夫環(huán)”是一個(gè)數(shù)學(xué)的應(yīng)用問(wèn)題：一群猴子排成一圈，按1,2,…,n依次編號(hào)。然后從第1只開(kāi)始數(shù)，數(shù)到第m只,把它踢出圈，從它后面再開(kāi)始數(shù)， 再數(shù)到第m只，在把它踢出去…，如此不停的進(jìn)行下去， 直到最后只剩下一只猴子為止，那只猴子就叫做大王。要求編程模擬此過(guò)程，輸入m、n, 輸出最后那個(gè)大王的編號(hào)。
方法一：遞歸算法
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);
}
}
$monkeys = array(1 , 2 , 3 , 4 , 5 , 6 , 7, 8 , 9 , 10); //monkeys的編號(hào)
$m = 3; //數(shù)到第幾只猴子被踢出
killMonkey($monkeys , $m);
運(yùn)行結(jié)果：
3的猴子被踢掉了
6的猴子被踢掉了
9的猴子被踢掉了
2的猴子被踢掉了
7的猴子被踢掉了
1的猴子被踢掉了
8的猴子被踢掉了
5的猴子被踢掉了
10的猴子被踢掉了
4成為猴王了
方法二：線性表應(yīng)用
最后這個(gè)算法最牛，
哦，是這樣的，每個(gè)猴子出列后，剩下的猴子又組成了另一個(gè)子問(wèn)題。只是他們的編號(hào)變化了。第一個(gè)出列的猴子肯定是a[1]=m(mod)n(m/n的余數(shù))，他除去后剩下的猴子是a[1]+1,a[1]+2,…,n,1,2,…a[1]-2,a[1]-1，對(duì)應(yīng)的新編號(hào)是1,2,3…n-1。設(shè)此時(shí)某個(gè)猴子的新編號(hào)是i，他原來(lái)的編號(hào)就是(i+a[1])%n。于是，這便形成了一個(gè)遞歸問(wèn)題。假如知道了這個(gè)子問(wèn)題(n-1個(gè)猴子)的解是x，那么原問(wèn)題(n個(gè)猴子)的解便是：(x+m%n)%n=(x+m)%n。問(wèn)題的起始條件：如果n=1,那么結(jié)果就是1。
function yuesefu($n,$m) {
$r=0;
for($i=2; $i<=$n; $i++) {
$r=($r+$m)%$i;
}
return $r+1;
}
echo yuesefu(10,3)."是猴王";
運(yùn)行結(jié)果：
4是猴王
更多關(guān)于PHP相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《PHP數(shù)據(jù)結(jié)構(gòu)與算法教程》、《php程序設(shè)計(jì)算法總結(jié)》、《php字符串(string)用法總結(jié)》、《PHP數(shù)組(Array)操作技巧大全》、《PHP常用遍歷算法與技巧總結(jié)》及《PHP數(shù)學(xué)運(yùn)算技巧總結(jié)》
希望本文所述對(duì)大家PHP程序設(shè)計(jì)有所幫助。
- php解決約瑟夫環(huán)示例
- 約瑟夫環(huán)問(wèn)題的PHP實(shí)現(xiàn) 使用PHP數(shù)組內(nèi)部指針操作函數(shù)
- PHP使用棧解決約瑟夫環(huán)問(wèn)題算法示例
- PHP實(shí)現(xiàn)約瑟夫環(huán)問(wèn)題的方法分析
- PHP基于遞歸實(shí)現(xiàn)的約瑟夫環(huán)算法示例
- PHP實(shí)現(xiàn)的基于單向鏈表解決約瑟夫環(huán)問(wèn)題示例
- php基于環(huán)形鏈表解決約瑟夫環(huán)問(wèn)題示例
- php實(shí)現(xiàn)約瑟夫問(wèn)題的方法小結(jié)
- php約瑟夫問(wèn)題解決關(guān)于處死犯人的算法
- PHP基于關(guān)聯(lián)數(shù)組20行代碼搞定約瑟夫問(wèn)題示例
- php使用環(huán)形鏈表解決約瑟夫問(wèn)題完整示例
相關(guān)文章
2010年最新PHP類的精髓歸納,需要的朋友可以參考下。2010-03-03
php獲取一定范圍內(nèi)取N個(gè)不重復(fù)的隨機(jī)數(shù)
這篇文章主要介紹了php獲取一定范圍內(nèi)取N個(gè)不重復(fù)的隨機(jī)數(shù)的方法,通過(guò)range函數(shù)創(chuàng)建指定范圍內(nèi)數(shù)組及shuffle進(jìn)行數(shù)組隨機(jī)排序,并使用array_slice抽取數(shù)組實(shí)現(xiàn)該功能,非常簡(jiǎn)單實(shí)用,需要的朋友可以參考下2016-05-05
PHP基于openssl實(shí)現(xiàn)的非對(duì)稱加密操作示例
這篇文章主要介紹了PHP基于openssl實(shí)現(xiàn)的非對(duì)稱加密操作,結(jié)合實(shí)例形式分析了openssl安裝、密鑰生成及php基于openssl的非對(duì)稱加密算法相關(guān)操作技巧,需要的朋友可以參考下2019-01-01
PHP學(xué)習(xí)筆記之字符串編碼的轉(zhuǎn)換和判斷
GBK 和 UTF-8 編碼的轉(zhuǎn)換是一個(gè)非常惡心的事情，比如像 PHP 中的 json_encode 本身根本不支持 GBK 形式的編碼。有兩個(gè)庫(kù)函數(shù)能夠支持編碼的轉(zhuǎn)換，通常能夠想到的就是 iconv 函數(shù)，使用起來(lái)也非常爽：2014-05-05
php判斷終端是手機(jī)還是電腦訪問(wèn)網(wǎng)站的思路及代碼
解下來(lái)將寫個(gè)小程序使用php判斷終端是手機(jī)還是電腦訪問(wèn)網(wǎng)站，感興趣的朋友可以參考下哈，希望對(duì)你學(xué)習(xí)php有所幫助2013-04-04
這篇文章主要介紹了PHP簡(jiǎn)單創(chuàng)建壓縮圖的方法,通過(guò)自定義函數(shù)實(shí)現(xiàn)壓縮圖像的功能,涉及php圖片的讀取與圖形圖像的創(chuàng)建相關(guān)技巧,需要的朋友可以參考下2016-08-08
PHP 實(shí)現(xiàn)多服務(wù)器共享 SESSION 數(shù)據(jù)
稍大一些的網(wǎng)站，通常都會(huì)有好幾個(gè)服務(wù)器，每個(gè)服務(wù)器運(yùn)行著不同功能的模塊，使用不同的二級(jí)域名，而一個(gè)整體性強(qiáng)的網(wǎng)站，用戶系統(tǒng)是統(tǒng)一的，即一套用戶名、密碼在整個(gè)網(wǎng)站的各個(gè)模塊中都是可以登錄使用的。2009-08-08
PHP彈出提示框并跳轉(zhuǎn)到新頁(yè)面即重定向到新頁(yè)面
本文為大家介紹下使用PHP彈出提示框并跳轉(zhuǎn)到新頁(yè)面，也就是大家所認(rèn)為的重定向，下面的示例大家可以參考下2014-01-01
這篇文章主要介紹了在PHP的Yii框架中使用行為Behaviors的方法,包括行為的綁定與解除等操作講解,需要的朋友可以參考下2016-03-03
在WordPress中實(shí)現(xiàn)發(fā)送http請(qǐng)求的相關(guān)函數(shù)解析
這篇文章主要介紹了在WordPress中實(shí)現(xiàn)發(fā)送http請(qǐng)求的相關(guān)函數(shù)解析,包括使用WP_Http類中的函數(shù)來(lái)發(fā)送post或get請(qǐng)求的方法,需要的朋友可以參考下2015-12-12