猴子选大王的四种方法,并对其时间与内存消耗的分析和对比

 2018-12-10 01:08:25   {{zan}}   1   513 

本篇利用PHP对“猴子选大王”问题,给出了四种方法,并对其进行了时间消耗的分析与对比。

题目:n个猴子要选出一个大王,随机给出一个数m,当猴子报数为m的时候,则被淘汰,剩余的最后一个猴子即为大王。 

一、算法解释及代码展示

方法一:围圈报数

n 个猴子围成一圈从 1 开始报数,报数等于 m 的猴子淘汰,然后下个猴子继续从 1 报数。

方法二:变换队列

n 个猴子持 1~n 的号码排成一列,从持 1 号牌子的猴子开始遍历,不是 m 的倍数号码牌的猴子移动到队列最后,号码牌变为为最后一个猴子的号码牌 +1,是m的倍数号码牌的猴子淘汰。

方法三:递归

n 个猴子排队报数,来个饲养员i来帮忙计数,计数 i 等于 m 的时候,当前报数的猴子淘汰,饲养员 i 再从 0 开始计数。

方法四:取余数

这次又来了个饲养员 j,现在饲养员 i 和 j 觉定不淘汰猴子了,采用更科学的数学计算法,猴子排队,饲养员 i 计算每个猴子的余数,饲养员 j 给猴子报数,计算完最后一个猴子,饲养员i取得余数加 1 就是猴王。

下面是代码展示:


方法一:围圈报数 getMonkeyKing1($n, $m)

function getMonkeyKing1($n, $m)
{
   $i = 1;
   $arr = range(1, $n);
   while (count($arr) != 1) {
       foreach ($arr as $k => $v) {
           if ($i == $m) {
               unset($arr[$k]);
               $i = 1;
           } else {
               $i++;
           }
       }
   }
   return reset($arr);
}

方法二:变换队列getMonkeyKing2($n, $m)  

function getMonkeyKing2($n, $m)
{
   $arr = range(1, $n);
   $i = 0;
   while (count($arr) != 1) {
       if (($i + 1) % $m == 0) {
           unset($arr[$i]);
       } else {
           // 将一个数组元素放入最后
           array_push($arr, $arr[$i]);
           unset($arr[$i]);
       }
       $i++;
   }
   return $arr[$i];
}

方法三:递归getMonkeyKing3($n, $m, $i = 0) 

function getMonkeyKing3($n, $m, $i = 0)
{
   if (!is_array($n)) {
       $n = range(1, $n);
   }
   if (count($n) == 1) {
       return reset($n);
   }
   foreach ($n as $k => $v) {
       $i++;
       if ($i % $m == 0) {
           unset($n[$k]);
           $i = 0;
       }
   }
   return getMonkeyKing3($n, $m, $i);
}

方法四:取余数getMonkeyKing4($n, $m) 

function getMonkeyKing4($n, $m)
{
   $i = 0;
   for ($j = 2; $j <= $n; $j++) {
       $i = ($i + $m) % $j;
   }
   return $i + 1;
}

 二、消耗时间与内存对比分析

分别对四种算法进行了时间消耗与内存消耗对比与分析,对四个算法分别进行了10次试验,试验参数n取值为100000,m取值为3,取平均值结果如下:

序号 算法                       函数                                                    时间消耗(毫秒)                 内存消耗(byte)
①    方法一:围圈报数   getMonkeyKing1(100000,3)              81.500053405762                374712
②    方法二:变换队列   getMonkeyKing2(100000,3)              48.094320297241                374704
③    方法三:递归          getMonkeyKing3(100000,3, $i = 0)   79.710340499877                375192
④    方法四:取余数      getMonkeyKing4(100000,3)               4.8909902572632                373720 

结论:时间消耗:①>③>②>④,内存消耗:③>①>②>④,方法四是最优方案。

ps:其实在,方法①②③中,可以有优化的地方,比如,可以采用动态规划的思想,把count($n)保存起来,不用每次计算,可以省下很多时间,关于动态规划的思想,可以看我的这篇文章:算法 -- 求最长公共字符串&PHP

欢迎补充!


千而の大狮子!


本文链接地址,转载请标注:https://caohongyuan.cn/article/52

(邮箱不会公开,只会做回复通知用) 提交 清空 {{comment.content}}
Re:{{response.content}}