主页 > PHP | WEB开发 > 约瑟夫环 的php递归实现

约瑟夫环 的php递归实现

2010 年 12 月 25 日 没有评论
<?php
/*
*约瑟夫环的问题
*已知n个人(以编号1,2,3,4....n分表表示),围坐在一张圆桌子周围。从编号为K的人开始报数,数到M的那个人
*出列;他的下一个人又从1开始报数,数到M的那个人又出列,依此规律下去,直到圆桌周围的人全部出列。
*求出最后一个出列的人的编号是多少?
*/
function killMonkey($monkeys , $m , $current = 0)
{
	$number = count($monkeys);
	$num = 1;		//这是个计数器
	if(count($monkeys) == 1){		//如果该数组只有一个了,那么数据处理完毕了
		echo "最后被剔除的编号是:".$monkeys[0]."<br />";
		return;
	}
	else
	{
		/*
			这里是关键的部分
		*/
		while($num < $m){
			$current++ ;		//当前的位置向前移一位
			$current = $current%$number;	//这样子处理,是为了使得当前要处理的数据的编号永远在这个数组的编号范围内
			$num ++;
		}
		echo "现在是编号为   <font color='red'>".$monkeys[$current]."</font>   的被踢掉了<br/>";
		array_splice($monkeys , $current , 1);		//把数组的一部分去掉
		killMonkey($monkeys , $m , $current);		//递归调用
	}
}
$monkeys = range(0,25);
unset($monkeys['0']);
$m = 5;
killMonkey($monkeys , $m);
?>

Tags: PHP

发表评论

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


*

您可以使用这些HTML标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>