PHP 解决约瑟夫环问题

2020-06-04_5ed8bd1aa04f1.jpeg

约瑟夫环

约瑟夫环是一个数学的应用问题,具体为,已知 n 个人(以编号 1,2,3…n 分别表示)围坐在一张圆桌周围。从编号为 k 的人开始报数,数到 m 的那个人出列;他的下一个人又从 1 开始报数,数到 m 的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。这个问题的输入变量就是 n 和 m,即 n 个人和数到 m 的出列的人。输出的结果,就是 n 个人出列的顺序。

图解

约瑟夫环问题.gif

代码

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
function main($queue,$n,$m){
$front = $round = 0;
$rear = $n;
while (true) {
if ($rear-$front==0) { //队不为空
break; // 跳出循环
}
for ($i=0; $i < $m-1; $i++) {
$front = ($front+1)%$n;
$rear = ($rear+1)%$n;
$queue[$rear] = $queue[$front];
}
$front = ($front+1)%$n;
$round++;
echo "第{$round}轮:".$queue[$front].PHP_EOL;
}
}
$n = 12;
$m = 3;
$queue = [$n];
//初始化队列,入队
for ($i=1; $i < $n+1; $i++) {
$queue[$i] = $i;
}
main($queue,$n,$m);

执行

1
2
3
4
5
6
7
8
9
10
11
12
13
$ php josephRing.php
第1轮:3
第2轮:6
第3轮:9
第4轮:12
第5轮:4
第6轮:8
第7轮:1
第8轮:7
第9轮:2
第10轮:11
第11轮:5
第12轮:10

[[Go 解决约瑟夫环问题]]

-------------本文结束感谢您的阅读-------------
0%