数猴子的小程序(约瑟夫环)

/*
 *一群猴子排成一圈,按1,2,...,n依次编号。然后从第1只开始数,数到第m只,把它踢出圈,从它后面再开始数,再数到第m只,在把它踢出去...,如此不停的进行下去,
 *直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程最新的新浪PHP面试题模拟此过程,输入m、n, 输出最后那个大王的编号。 
 *
 *此函数的原理是 比如:array(1=>1,2=>2,3=>3); 要数每当2的时候出局,则数到2的时候,把"1=>1"这个值移到 "4=>1",即2=>2这个值出局后的数组为array(3=>3,4=>1);
 */
function fundLastMonk($n,$m){
	$arr = range(0,$n);//生成数组
	unset($arr[0]);//从序号1开始的数组
	$i = 0;
	while(1){
		$i++;				
		if($i % $m == 0){
			if($arr[$i] == null){//当被删除的值为空时,则不停的把数组的第一个值移到最后面,直到该值不为空。(这种情况可能是因为:数组的值的数量少于出局数,或者数组的值不够,把已经数过的值移到后面)
				while(1){
					foreach($arr as $key=>$val){
						if($arr[$i] != null) break 2;
						$arr[] = $val;
						unset($arr[$key]);
					}
				}
				
				if($arr[$i + 1] == null){//当要被出局的值是数组的最后一个值的时候,先把前面的值移到后面
					foreach($arr as $key=>$val){
						if($key == $i) break;
						$arr[] = $val;
						unset($arr[$key]);
					}
				}
			}else{//把数过的数移到数组的最后面
				foreach($arr as $key => $val){
					if($key == $i)break;
					$arr[] = $val;
					unset($arr[$key]);
				}
			}
			
			unset($arr[$i]);	
		}
		if(count($arr) == 1) {
			return array_shift($arr);
		}
	}
}

echo fundLastMonk(5,6);
此条目发表在php小程序分类目录。将固定链接加入收藏夹。

发表评论

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

看不清?