用php实现约瑟夫环问题,求指导

原创
2014/02/20 16:38
阅读数 632

问题:一群猴子排成一圈,按 1,2,...,n 依次编号。然后从第 1 只开始数,数到第 m 只,把它踢出圈,从它后面再开始数, 再数到第 m 只,在把它踢出去...,如此不停的进行下去, 直到最后只剩下一只猴子为止,那只猴子就叫做大王。要求编程模拟此过程,输入 m、n, 输出最后那个大王的编号。 

思考:按正常思路来说,应该是以一个猴为起点(定位),开始往后数,又因为是个圈,从最后一个又转到第一个,可以认为是在取余。那么我就按照我数猴的思维模式开始写程序了。主要利用的数组。

<?php
function getking($n,$m){
	$array=range(1,$n);
	$now=0;//初始化$now,为定位标志,也就是从它开始数
	$nn=$n;//不破坏初始量
	while($nn>1){
		$now=($now+$m)%$nn;//计算该第几个猴子出局了,因为是圈,取余就够了
		if(!$now){$now=$nn;}//如果正好整除那么这个猴子是最后一个(不是第0个)
		array_splice($array,$now-1,1);//去掉这个猴子
		$nn--;$now--;//总数减少一个,标志前移一个
	}
	echo $array[0];
}
getking(100,17);

ps. array_splice是我无意间发现的函数,因为unset一个数组元素后不会重建键值,这个函数可以重建的。如果不是这样我就重新循环定义一个新数组了。

我觉得这么写非常简单,但是不知道为什么,关于这个题的解法中,没有这么写的呢?基本都是c++的思路,动游标来写,是我写的太低级了么?



展开阅读全文
加载中

作者的其它热门文章

打赏
0
3 收藏
分享
打赏
2 评论
3 收藏
0
分享
返回顶部
顶部