php解决 约瑟夫问题

php解决 约瑟夫问题问题描述：有n人围成一圈，从任意一个人开始，依次报数，数到m时，第m个人出界(即出圈),出界的下一个人继续从1开始报数 ，数到m时，第m个同样出界，依次类推

<?php
header("content-type:text/html;charset=utf-8");
set_time_limit(0);
/**
* 约瑟夫问题
*
* 又称丢手帕问题
* 问题描述：有n人围成一圈，从任意一个人开始，依次报数，数到m时，
* 第m个人出界(即出圈),出界的下一个人继续从1开始报数 ，数到m时，
* 第m个同样出界，依次类推
*
* 问：每个人出界顺序及最后一个人出界的顺序
* */
/**
* 构造数组
*
* @param int $n 数组元素个数
* @return array
* */
$arr=array();//n个人用一个元素个数为n的数组来表示
function initarray($n){
    global $arr;
    for($i=1;$i<=$n;$i++){
        $arr[$i]=array(0);
    }
}
/**
* 找出每个人出界的顺序
*
* @param int $n 数组的元素个数
* @param int $m 报数的上限
* @param int $p 从第$p个人(原始围成圈的顺序)开始报数
* @param int $k 第$k次出界
* @return void
* */
function joseph($n,$m,$p,$k){
    global $arr;
    if($n <= 1){
        echo "人数不能少于2";
    }
    for($j=1;$j<=$m;$j++){
        if($p>$n){
            $p=1;
        }
        if($arr[$p][0] != 0){
            $j--;
        }
        $p++;
    }
    $arr[$p-1][0]=$k;
    $y=0;//已经出界的人的计数器
    foreach($arr as $value){
        if($value[0] != 0){
            $y++;
        }
    }
    if($y < $n){
        joseph($n,$m,$p,++$k);
    }
}
initarray(41);
echo joseph(41,3,1,1);
foreach($arr as $k=>$value){
    if($value[0] == count($arr)){
        $last=$k;
    }
    echo "第<font color='red'><span style='width:15px'>$k</font></span>人将会是第<font color='blue'><span style='width:15px'>".$value[0]."</span></font>次出界<br/>";
}
echo "最后出界的人是第".$last."人";
?>