Home > Article > Backend Development > PHP implementation of monkey king problem algorithm example_PHP tutorial
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 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!):
?
2 3
|
function yuesefu($n,$m) {
$r=0; |