注册 登录
  • 欢迎访问开心洋葱网站,在线教程,推荐使用最新版火狐浏览器和Chrome浏览器访问本网站,欢迎加入开心洋葱 QQ群
  • 为方便开心洋葱网用户,开心洋葱官网已经开启复制功能!
  • 欢迎访问开心洋葱网站,手机也能访问哦~欢迎加入开心洋葱多维思维学习平台 QQ群
  • 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏开心洋葱吧~~~~~~~~~~~~~!
  • 由于近期流量激增,小站的ECS没能经的起亲们的访问,本站依然没有盈利,如果各位看如果觉着文字不错,还请看官给小站打个赏~~~~~~~~~~~~~!

php解决 约瑟夫问题

PHP 水墨上仙 2942次浏览 已收录 手机上查看

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."人";
?>


开心洋葱 , 版权所有丨如未注明 , 均为原创丨未经授权请勿修改 , 转载请注明php解决 约瑟夫问题
喜欢 (0)
[开心洋葱]
分享 (0)
关于作者:
水墨上仙
……
加载中……