php 解决约瑟夫问题解析

前端之家收集整理的这篇文章主要介绍了php 解决约瑟夫问题解析前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。
PHP解决 约瑟夫问题感兴趣的小伙伴,下面一起跟随编程之家 jb51.cc的小编两巴掌来看看吧!
PHP解决 约瑟夫问题
问题描述:有n人围成一圈,从任意一个人开始,依次报数,数到m时,
第m个人出界(即出圈),出界的下一个人继续从1开始报数 ,数到m时,
第m个同样出界,依次类推

/**
 * PHP解决 约瑟夫问题
 *
 * @param 
 * @arrange 512-笔记网: www.www.jb51.cc
 **/
header("content-type:text/html;charset=utf-8");
set_time_limit(0);
/**
* 约瑟夫问题
*
* 又称丢手帕问题
* 问题描述:有n人围成一圈,从任意一个人开始,依次报数,数到m时,
* 第m个人出界(即出圈),出界的下一个人继续从1开始报数 ,数到m时,
* 第m个同样出界,依次类推
*
* 问:每个人出界顺序及最后一个人出界的顺序
* */
/**
* 构造数组
*
* @param int $n 数组元素个数
* @return array
* */
$arr=array();//n个人用一个元素个数为n的数组来表示
function initarray($n){
	global $arr;
	for($i=1;$i<=$n;$i++){
		$arr[$i]=array(0);
	}
}
/**
* 找出每个人出界的顺序
*
* @param int $n 数组的元素个数
* @param int $m 报数的上限
* @param int $p 从第$p个人(原始围成圈的顺序)开始报数
* @param int $k 第$k次出界
* @return void
* */
function joseph($n,$m,$p,$k){
	global $arr;
	if($n <= 1){
		echo "人数不能少于2";
	}
	for($j=1;$j<=$m;$j++){
		if($p>$n){
			$p=1;
		}
		if($arr[$p][0] != 0){
			$j--;
		}
		$p++;
	}
	$arr[$p-1][0]=$k;
	$y=0;//已经出界的人的计数器
	foreach($arr as $value){
		if($value[0] != 0){
			$y++;
		}
	}
	if($y < $n){
		joseph($n,++$k);
	}
}
initarray(41);
echo joseph(41,3,1,1);
foreach($arr as $k=>$value){
	if($value[0] == count($arr)){
		$last=$k;
	}
	echo "第<font color='red'><span style='width:15px'>$k</font></span>人将会是第<font color='blue'><span style='width:15px'>".$value[0]."</span></font>次出界<br/>";
}
echo "最后出界的人是第".$last."人";

/***   来自编程之家 jb51.cc(jb51.cc)   ***/@H_403_7@

猜你在找的PHP相关文章