One article to solve the Joseph ring problem (PHP version)

This article introduces the PHP version of the Joseph Ring problem (monkey chooses the king). It has certain reference value. Friends in need can refer to it. I hope it will be helpful to everyone.

Joseph Ring Problem (Monkey Chooses the King) PHP Version

The Josephus Problem is sometimes described as the monkey chooses the king problem, and the title is as follows. (The origin of Joseph's question will be posted at the end)

A group of monkeys line up in a circle and are numbered 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 again, kick it out..., and so on. This continues until there is only one monkey left, and that monkey is called the king.

Requires programming to simulate this process, input m, n, and output the number of the last king.

Use a program to simulate this process. The code is as follows:

function monkeyKing($n, $m)
{
    $arr = range(1, $n);       //构造一个数组
    $i = 1;                         //从第一个开始循环
    while (count($arr) > 1) {       //如果总数大于1
        if ($i % $m != 0) {
            $arr[] = $arr[$i - 1];  //不被踢出则压入数组尾部
        }
        unset($arr[$i - 1]);        //压入数组然后删除
        $i++;                       //继续循环
    }
    return $arr[$i - 1];            //直至最后剩下一个为大王
}
print_r(monkeyKing(5, 3));         //第4只为大王

The following is the simulation process. For monkeys that are not eliminated, the tail of the array is continuously added:

 $n = 5
 $m = 3
 $arr = [1, 2, 3, 4, 5]
 $i   $arr
 ---+------------------------
 1    x 2 3 4 5 1
 2    x x 3 4 5 1 2
>3    x x x 4 5 1 2
 4    x x x x 5 1 2 4
 5    x x x x x 1 2 4 5
>6    x x x x x x 2 4 5
 7    x x x x x x x 4 5 2
 8    x x x x x x x x 5 2 4
>9    x x x x x x x x x 2 4
 10   x x x x x x x x x x 4 2
 11   x x x x x x x x x x x 2 4
>12   x x x x x x x x x x x x 4

The origin of Joseph's problem :

This question is named after Flavio Josephus, a 1st century Jewish historian. He wrote in his diary that he and 40 of his comrades were surrounded by Roman troops in the cave. They discussed whether to commit suicide or be captured, and finally decided to commit suicide, and decided who would kill whom by drawing lots. Josephus and one other man were the last two left. Josephus convinced the man that they would surrender to the Roman army and not commit suicide again. Josephus attributed his survival to luck or providence, he did not know which.

Recommended learning: "PHP Video Tutorial"

The above is the detailed content of One article to solve the Joseph ring problem (PHP version). For more information, please follow other related articles on the PHP Chinese website!