设为首页 | 加入收藏
PHP
心如止水
网络编程
育儿心经
成长经历
心如止水 首页 > 心如止水 > PHP

猴子选大王的面试老题

所属类别:PHP 发布者: 心如止水 来源:喜气妍妍 发布时间:2013-04-20 21:51:21

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

    /**
     * 猴子选大王
     * @param int $m 猴子总数
     * @param int $n 出局报数
     */
    private function monkeyKing($m, $n) {
        for ($i=1; $i<=$m; $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;
    }

下面有别人写的算法:(我是理解不了,谁能帮我解析下 谢谢!)

function yuesefu($m,$n)  // $m : 猴子的总数  $n: 要数的数     函数返回大王的编号  
{  
    $r=0;  
    for($i=2;$i<=$m; $i++)  
    {$r=($r+$n)%$i;}
    return $r+1;  
}

标签: php ;

100% 0% 欢迎顶踩!
        6 票                 0
顶 踩
看过本文的所有网友评论:
我也来评论几句:
验证码: 请输入右边图片上的字母或数字(不区分大小写);看不清,请直接点击图片即可换一张