- 相關(guān)推薦
PHP實(shí)現(xiàn)猴子選大王問題的算法
我們的事業(yè)就是學(xué)習(xí)再學(xué)習(xí)，努力積累更多的知識(shí)，因?yàn)橛辛酥R(shí)，社會(huì)就會(huì)有長足的進(jìn)步，人類的未來幸福就在于此。以下是小編為大家搜索整理的PHP實(shí)現(xiàn)猴子選大王問題的算法，希望對(duì)大家有所幫助!更多精彩內(nèi)容請(qǐng)及時(shí)關(guān)注我們應(yīng)屆畢業(yè)生考試網(wǎng)!
一、問題：
n只猴子圍坐成一個(gè)圈，按順時(shí)針方向從1到n編號(hào)。
然后從1號(hào)猴子開始沿順時(shí)針方向從1開始報(bào)數(shù)，報(bào)到m的猴子出局，再從剛出局猴子的下一個(gè)位置重新開始報(bào)數(shù)，
如此重復(fù)，直至剩下一個(gè)猴子，它就是大王。
設(shè)計(jì)并編寫程序，實(shí)現(xiàn)如下功能：
(1) 要求由用戶輸入開始時(shí)的猴子數(shù)$n、報(bào)數(shù)的最后一個(gè)數(shù)$m。
(2) 給出當(dāng)選猴王的初始編號(hào)。
二、解決方法：
?
|
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 開始時(shí)的猴子數(shù)量
* @param int $m 報(bào)道的最后一個(gè)數(shù)
*(報(bào)到這個(gè)數(shù)的猴子被淘汰,然后下一個(gè)猴子重新從①開始報(bào)數(shù))
* @return int 猴子的初始編號(hào)
*/
function monkeySelectKing($n,$m)
{
//猴子的初始數(shù)量不能小于2
if ($n<2)
{
return false;
}
$arr=range(1,$n);
//將猴子分到一個(gè)數(shù)組里, 數(shù)組的值對(duì)應(yīng)猴子的初始編號(hào)
$unsetNum=0;
//定義一個(gè)變量,記錄猴子的報(bào)數(shù)
for ($i = 2; $i <=$n*$m ; $i++)
//總的循環(huán)次數(shù)不知道怎么計(jì)算,
{
//不過因?yàn)檠h(huán)中設(shè)置了return,所以$m*$len效率還可以
foreach ($arr as $k => $v)
{
$unsetNum++; //每到一個(gè)猴子, 猴子報(bào)數(shù)+1
//當(dāng)猴子的報(bào)數(shù)等于淘汰的數(shù)字時(shí):淘汰猴子(刪除數(shù)組元素)
//報(bào)數(shù)歸0(下一個(gè)猴子從1開始數(shù))
if ($unsetNum==$m)
{
// echo "<pre>";//打開注釋,可以看到具體的淘汰過程
// print_r($arr);
unset($arr[$k]);
//淘汰猴子
$unsetNum=0;
//報(bào)數(shù)歸零
if (count($arr)==1)
//判斷數(shù)組的長度, 如果只剩一個(gè)猴子, 返回它的值
{
return reset($arr);
}
}
}
}
}
var_dump(monkeySelectKing(6, 3));
|
補(bǔ)充改進(jìn)算法(該算法更加簡潔明了!)：
?
|
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實(shí)現(xiàn)猴子選大王問題的算法】相關(guān)文章：
PHP實(shí)現(xiàn)抽獎(jiǎng)概率算法09-13
PHP紅包算法11-04
php經(jīng)典算法介紹10-05
PHP經(jīng)典算法題09-05
PHP幾個(gè)經(jīng)典算法題10-27
PHP的樹形結(jié)構(gòu)算法07-06
如何解決PHP無法實(shí)現(xiàn)多線程的問題08-20
實(shí)現(xiàn)PHP實(shí)現(xiàn)限制IP訪問11-11
PHP 快速排序算法解析06-11