夜丶有雪

青青子衿,悠悠我心。

约瑟夫环

约瑟夫环是一个数学的应用问题:已知n个人(以编号1,2,3…n分别表示)围坐在一张圆桌周围。从编号为k的人开始报数,数到m的那个人出列;他的下一个人又从1开始报数,数到m的那个人又出列;依此规律重复下去,直到圆桌周围的人全部出列。
php有非常完善的数据结构模拟方案,可以非常简洁的解决这样的问题。当然数量级太大那还是使用数学方法吧!

<?php
function king($n, $m)
{
	$monkey = range(1, $n);//模拟建立一个连续数组
	$i = 0;
	while (count($monkey) >= 1)
	{
		$i += 1; // 开始查数
		$head = array_shift($monkey); //直接一个一个出列最前面的猴子
		if ($i % $m != 0)
		{
			array_push($monkey, $head); // 如果没数到m或m的倍数,则把该猴放回尾部去.
		}
		else 
		{
			$out[] = $head;
		}
	}
	return $out;
}
$out = king(9, 5);
print_r($out);
点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注