首页 > 程序开发 > PHP > [算法题]约瑟夫(josephus)环的php玩法
2014
11-14

[算法题]约瑟夫(josephus)环的php玩法

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

/**
* 猴子选大王
*
* @param int $m 猴子数
* @param int $n 出局数
* @return array
*
*/
#方法一
function yuesefu($m,$n) {  
    $r=0;  
    for($i=2; $i<=$m; $i++) {
        $r=($r+$m)%$i;  
    }
    return $r+1;  
}

#方法二
function king($m ,$n) {
	//构造数组
	for($i=1 ;$i<$m+1 ;$i++){
	   $arr[] = $i ;
	}
	$i = 0 ;    //设置数组指针

	while(count($arr)>1)
	{
	   //遍历数组,判断当前猴子是否为出局序号,如果是则出局,否则放到数组最后
	   if(($i+1)%$n ==0) {
	    unset($arr[$i]) ;
	   } else {
	    array_push($arr ,$arr[$i]) ; //本轮非出局猴子放数组尾部
	    unset($arr[$i]) ;   //删除
	   }
	   $i++ ;
	}
	return $arr ;
}
var_dump(yuesefu(1000,34));
var_dump(king(1000,34));
最后编辑日期:
作者:uuling
这个作者貌似有点懒,什么都没有留下。

留下一个回复

你的email不会被公开。