PHP random selection algorithm (2)

In the previous article "PHP Random Pick-One Algorithm (1)", we briefly introduced the interview questions of PHP Pick-One Algorithm. Next, we will continue to combine the previous content to explain in detail the PHP algorithm.

The problem is as follows:

A group of monkeys line up in a circle and are numbered sequentially according to 1, 2,...,n. Then start counting from the 1st one, count to the mth one, kick it out of the circle, start counting from behind it, count to the mth one, kick it out..., and continue in this way until the end. Until there is only one monkey left, that monkey is called the king. Programming is required to simulate this process, input m, n, and output the number of the last king.

The solution code example is as follows:

<?php

function king($n, $m){
    $monkeys = range(1, $n);         //创建1到n数组
    $i=0;
    while (count($monkeys)>1) {     //循环条件为猴子数量大于1
        if(($i+1)%$m==0) {     //$i为数组下标;$i+1为猴子标号
            unset($monkeys[$i]);  //余数等于0表示正好第m个，删除，用unset删除保持下标关系
        } else {
            array_push($monkeys,$monkeys[$i]);     //如果余数不等于0，则把数组下标为$i的放最后，形成一个圆形结构
            unset($monkeys[$i]);
        }
        $i++;//$i 循环+1，不断把猴子删除，或 push到数组
    }
    return current($monkeys);  //猴子数量等于1时输出猴子标号，得出猴王
}
echo king(10,3);

Here we create a method King, the parameter $n represents n monkeys, and $m represents counting to the mth monkey. Then in the king method body, we first create an array from 1 to n through the range function and use $monkeys to receive it. Then use a while loop to determine the elements that meet the requirements.

The condition of the while loop is that when the number of monkeys $monkeys is greater than 1, the loop body will be executed. In the loop body, use if...else to determine if ($i 1)%$m==0, that is, when the remainder is equal to 0, that is, the mth monkey is counted, then use unset to delete this element and Maintain the subscript relationship.

If the remainder is not equal to 0, use the array_push function to put the array subscript $i at the end to form a circular structure. The array_push function is used to push one or more elements to the end of the array (push).

Finally, make $i loop 1, continuously delete monkeys, or push them to the array. When the number of monkeys is equal to 1, the monkey label is output, and the monkey king is obtained.

In the above method, the parameters we give are 10 and 3, and the output result is:

4

means that the monkey king obtained is the monkey labeled 4 .

This article’s introduction to the PHP one-picking algorithm ends here. In the next article "PHP Randomly Picking One Algorithm (3)", we will introduce to you how to use Xdebug to run Debugging the implementation of this method.

The above is the detailed content of PHP random selection algorithm (2). For more information, please follow other related articles on the PHP Chinese website!