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

/*
 *一群猴子排成一圈，按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);