天空之城

您当前位置>>首页>>其它>>代码集>>PHP实现猴子选大王算法(约瑟夫环)

PHP实现猴子选大王算法(约瑟夫环)

来源:天空之城 - My Site   时间:2014-04-02 21:51:52   编辑:administrator   阅读数:420

[导读]n只猴子围坐成一个圈,按顺时针方向从1到n编号。然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王。

n只猴子围坐成一个圈,按顺时针方向从1到n编号。然后从1号猴子开始沿顺时针方向从1开始报数,报到m的猴子出局,再从刚出局猴子的下一个位置重新开始报数,如此重复,直至剩下一个猴子,它就是大王。(约瑟夫环)

虽然PHP中算法用的比较少,很多PHPer一般都接触不到明确说使用算法的,但是很多时候我们会不知不觉的使用一些简单的算法,很多的都是习惯去用,废话也不多说,本文主要内容就是“猴子选大王算法”(当然有些其他的叫法也正常),也就是著名的约瑟夫环,用PHP实现的话,开始自己只是想到用递归结合数组合并,当然这样每次循环都需要合并数组所以性能方面有所不足,也比较几种方法,从循环次数以及每次的资源消耗等方面考虑,当然主要的是一种算法思想,其他的暂不多做说明,以下是具体的三种编码实现(因为是学习比较分析,所以比较多的注释还有输出之类的,有些注释的代码也没清理,加上时间的统计片段,所以相对代码会比原先的多,代码看的比较乱):

<?php
/**
* @param  $n  总数
* @param  $m  当报数到 m 时,m出列
* @return $monkeys 最后剩下的数字
*/
function get_king($n,$m){
    $start_time = microtime(true);
    $arr = range(1,$n);
    //$k = 0;
//    for($i=1;$i<$n;++$i){
//        $n_middle = count($arr);      //用for和while每次循环都要重新统计
    while(($n_middle=count($arr))>1){
        //++$k;
        if($n_middle >= $m){
            $arr1 = array_slice($arr,0,$m-1);
            $arr2 = array_slice($arr,$m);
            
            $arr = array_merge($arr2,$arr1);
        }else{
            $num = $m%$n_middle; 
            if($num==0){
                $arr = array_slice($arr,0,$num-1);
            }else{
                $arr1 = array_slice($arr,0,$num-1);
                $arr2 = array_slice($arr,$num);
                
                $arr = array_merge($arr2,$arr1);
            }
        }
    }
    $end_time = microtime(true);
    $arr[1] = $end_time-$start_time;
    //$arr['loop_times'] = $k;
    return $arr;
}

var_dump(get_king(2000,100));

/**
 * 
 * 约瑟夫环(很佩服这段)
 * @param  $n  总数
 * @param  $m  当报数到 m 时,m出列
 * @return $monkeys 最后剩下的数字
 */
function yuesefu($n,$m) {
    $start_time = microtime(true);
    $r=0;  
    for($i=2; $i<=$n; ++$i) {
            $r=($r+$m)%$i;  
    }
    $end_time = microtime(true);
    $take_time = $end_time - $start_time;
    $res = $r+1;
    $arr = array(
        $res,
        $take_time,
//        'loop_times' => $n-1,
    );
    return $arr;  
}  

echo '<br />';
var_dump(yuesefu(2000,100));
echo '<br />';

/**
 * 
 * 猴子选大王
 * @param  $n  总数
 * @param  $m  当报数到 m 时,m出列
 * @return $monkeys 最后剩下的数字
 */
function monkeyKing($n, $m) {
    $start_time = microtime(true);
    $monkeys = range(1, $n);
    $i = 0;                // 取出时候的坐标
    $z = 0;                // 数到M的时候停
    //$k = 0;
    while(($mNum = count($monkeys)) > 1) {
        //++$k;
        if($i == $mNum) {
            $i = 0;                // 圈
        }
        ++$z;
        ++$i;
        if($z == $m) {
            array_splice($monkeys, --$i, 1);
            $z = 0;                // 归零
        }

    }
    $end_time = microtime(true);
    $monkeys[1] = $end_time-$start_time;
//    $monkeys['loop_times'] = $k;
    return $monkeys;
}
var_dump(monkeyKing(2000,100));

PHP实现猴子选大王算法(约瑟夫环)
原文地址:

上一篇:关于PHP的漏洞以及如何防止PHP漏洞?【转】
下一篇:PHP遍历目录文件

    相关文章

    更多»
      just do it
      天空之城天空之城