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

Question

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

Answer 1

function initial_key($k){ //初始化数组索引，不知道有没有原函数，只好自定义一个
$arr=array();
reset($k);
foreach($k as $value) $arr[]=$value;
return $arr;
}function findking($n,$m){ //$n为猴子数，$m为点数间隔
$monkeys = range(1,$n,1);//猴子数组，值是对应的编号
for($i = 0;$i < $n-1;$i++){//大循环，一次循环踢出一只猴子，所以要循环n-1次
    $nownum = count($monkeys);//得到当前猴子数
    $monkeys = initial_key($monkeys);//调用索引初始化函数
  if(($m % $nownum) == 0)
  $kick_key = $nownum-1;
  else
  $kick_key = ($m % $nownum)-1;//以上获得要被踢出的猴子的索引
unset($monkeys[$kick_key]);//踢出猴子
if($kick_key!=0){
  $arr=array();
  for($k=0;$k<$kick_key;$k++){
  array_push($arr,$monkeys[$k]);
  unset($monkeys[$k]);
  }
  $monkeys=array_merge($monkeys,$arr);/*以上判断，如果被踢出的不是第一只猴子，那么将位于被踢
                                                       出猴子的前面的猴子依次调到队伍后面，为下次循环做准备*/
}
  }
  return current($monkeys);
}
?>

Answer 2

把C语言的实现代码改成php的即可

Answer 3

http://topic.csdn.net/u/20090327/15/eb87c0f9-75e1-4977-b1ee-fdb9a7a34b7e.html22楼的代码：
function kickMonkey ($n,$m) {
    $s = 0;
    for ($i=2; $i<=$n; $i++) {
        $s = ($s+$m)%$i;
    }
    $win = $s+1;
    return $win;
}echo kickMonkey(10,3);

Answer 4

$s = ($s+$m)%$i;
這句是關鍵
不用循環，直接用計算把win算出來

Answer 5

findKing(array(1,2,3,4,5,6,7,8), 5);function findKing(array $list, $m){
if(count($list) === 1){
var_dump($list);
return ;
}
array_splice($list, ($m%count($list) - 1), 1);
findKing($list, $m);
}

Answer 6

递归和循环都可以实现模拟，如果仅仅要求结果，6楼的应该是最好的了。
贴个我的。
function FindMonkeyKing($n, $m){ $MonkeyList = array();
for($i = 1; $i <= $n; $i++){
$MonkeyList[] = $i;
}
// print_r($MonkeyList);
// echo "</br>"; $Count = $n;
$LuckyBoy = 0;
while($Count > 1){
$LuckyBoy = ($m + $LuckyBoy) % $Count - 1;
if($LuckyBoy < 0)$LuckyBoy = $Count - 1;
unset($MonkeyList[$LuckyBoy]);
sort($MonkeyList); // 初始化键值。当然也可以自己写个函数
$Count = count($MonkeyList);
// print_r($MonkeyList);
// echo "</br>";
}
return $MonkeyList[0];
}