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

狂沙lover 发布于 2014/02/24 10:11
阅读 1K+
收藏 3
PHP

问题:一群猴子排成一圈,按 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
南湖船老大
南湖船老大

你这还是不够简洁。来个更简单的

function kickMonkey ($n,$m) {
    $s = 0;
    for ($i=2; $i<=$n; $i++) {
        $s = ($s+$m)%$i;
    }
    $win = $s+1;
    return $win;
}
狂沙lover
狂沙lover
老大果然犀利,不明觉厉啊。。。。泪奔中,我要去研究下
0
梅开源
梅开源

不评价实现细节

一眼看去最大问题

如何表现这个算法的处理过程


0
leo108
leo108
这种题目核心在于算法,各个编程语言有不同的实现,这个没必要太纠结,多数是语法糖的缘故
0
tomener
tomener
还是你这个比较好理解
返回顶部
顶部