PHP implementation of monkey king problem algorithm example

PHP implementation of monkey king problem algorithm example_PHP tutorial

WBOY

Release： 2016-07-13 09:56:39

Original

1197 people have browsed it

An example of the algorithm for the monkey to choose the king problem in php

The following is an introduction to the algorithm for the monkey to choose the king problem in php.

This article describes the example of how to implement the monkey king problem algorithm in PHP. Share it with everyone for your reference. The specific analysis is as follows:

1. Question:

n monkeys sit in a circle, numbered from 1 to n in a clockwise direction.

Then start counting from monkey No. 1 in a clockwise direction from 1. The monkey that reports m is out, and then restart counting from the position next to the monkey that just got out,

Repeat this until there is only one monkey left, and it is the king.

Design and write programs to achieve the following functions:

(1) The user is required to input the starting number of monkeys $n and the last number $m.

　(2) Give the initial number of the elected Monkey King.

2. Solution:

/**

* @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 "

";//打开注释,可以看到具体的淘汰过程
            // 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 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 The number of monkeys at the beginning * @param int $m The last number reported *(The monkey who reported this number will be eliminated, and then the next monkey will start counting again from ①) * @return int The initial number of the monkey */ function monkeySelectKing($n,$m) { //The initial number of monkeys cannot be less than 2 if ($n<2)<🎜> <🎜>{<🎜> <🎜>return false;<🎜> <🎜>}<🎜> <🎜> <🎜> <🎜>$arr=range(1,$n);<🎜> <🎜>//Group the monkeys into an array, and the value of the array corresponds to the initial number of the monkey<🎜> <🎜>$unsetNum=0;<🎜> <🎜>//Define a variable to record the number of monkeys <🎜> <🎜> <🎜> <🎜>for ($i = 2; $i <=$n*$m ; $i )<🎜> <🎜>//I don’t know how to calculate the total number of cycles, <🎜> <🎜>{<🎜> <🎜>//However, because return is set in the loop, the efficiency of $m*$len is okay<🎜> <🎜>foreach ($arr as $k => $v) { $unsetNum; //Every time a monkey is reached, the monkey counts 1 //When the monkey’s reported number is equal to the elimination number: eliminate the monkey (delete the array element) //The count returns to 0 (the next monkey starts counting from 1) if ($unsetNum==$m) { // echo "

";//Open the comments and you can see the specific elimination process
            // print_r($arr);
            unset($arr[$k]);
            //Eliminate the monkey
            $unsetNum=0;
            //Return to zero
            if (count($arr)==1)
            //Judge the length of the array, if there is only one monkey left, return its value
            {
            return reset($arr);
            }
            }
            }
            }
            }
             
            var_dump(monkeySelectKing(6, 3));

Supplementary improved algorithm (the algorithm is more concise and clear!):

function yuesefu($n,$m) {

$r=0;

for($i=2; $i<=$n; $i ) {

$r=($r $m)%$i;

}

return $r 1;

}

print_r(yuesefu(3,3));

2 3

function yuesefu($n,$m) { $r=0;

for($i=2; $i<=$n; $i ) { $r=($r $m)%$i; } return $r 1; } print_r(yuesefu(3,3));

I hope this article will be helpful to everyone’s PHP program algorithm design. http://www.bkjia.com/PHPjc/987105.htmlwww.bkjia.comtruehttp: //www.bkjia.com/PHPjc/987105.htmlTechArticleAn example of the algorithm for implementing the monkey-choosing-king problem in php. The following is an example of the algorithm for implementing the monkey-choosing-king problem in php. The example in this article describes how to implement the monkey-choosing-king problem algorithm in PHP. Share with everyone...