PHP 解决约瑟夫环问题

约瑟夫环

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

图解

代码

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);

执行

$ 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 解决约瑟夫环问题]]