PHP

【PHP算法】一群猴子排成一圈,m,n猴子选大王算法

勇康博客网
预计阅读时长 7 分钟
位置: 首页 PHP 正文

怎么说呢,平时用不到,面试可能会考,php经典算法,猴子选大王

问题:

一群猴子排成一圈,按1,2,...,n依次编号。

然后从第1只开始数,数到第m只,把它踢出圈,

然后从它后面再开始数,再数到第m只,在把它踢出去...,

如此不停的进行下去,直到最后只剩下一只猴子为止,那只猴子就叫做大王。


思路分析:(遇到这种有变量的最好先假定具体数值,方便分析)

假定有6只猴子排成一圈,我们把圈给它剪开,那么编号就是1,2,3,4,5,6;排成一排

假定数到第2只把它剔除圈,那么为了维持圈循环的状态,当你数到1的时候,此时1应该放在6的后面,即:2,3,4,5,6,1

那么数到2的时候,剔除,应该就是:3,4,5,6,1

数到3的时候不剔除应该是:4,5,6,1,3

数到4的时候剔除:5,6,1,3

数到5的时候不剔除:6,1,3,5

数到6的时候剔除:1,3,5

数到7的时候不剔除:3,5,1

数到8的时候剔除:5,1

数到9的时候不剔除:1,5

数到10的时候剔除:5

最红猴王编号为:5


判断是否剔除:从以上规律,我们可以用数到几除以m取余,如果余数为0代表剔除,否则为不剔除,比如m为2,你数到1的时候那么就不剔除,数到2的时候余数为0,就要剔除....


编码:

function monkeyKing($n,$m){
    $monkeys = range(1, $n); //函数创建一个包含指定范围的元素的数组
    $i = 0;
    while (count($monkeys) > 1){
        if (($i+1)%$m == 0) {  //$i+1是指实际上数数的值,实际数数是1,2,3,4,5而$i是这些值的下标,
            //所以要加1得到实际的值与第m只相除余0才是数到第m只
            unset($monkeys[$i]);//数到第m只就删掉
        }else{
            array_push($monkeys, $monkeys[$i]);//不是第m只的放到最后
            unset($monkeys[$i]); //删除原来的占位
        }
        $i ++;
    }
    return $monkeys; //输出数组中的当前元素的值
}

$monkey = monkeyKing(6, 2);
print_r($monkey);
//结果为array('10' => 5) ,代表一共数到了10,最后剩下5号


本文来自投稿,不代表本站立场,如若转载,请注明出处:
-- 展开阅读全文 --
头像
Windows环境wkhtmltopdf安装使用教程
« 上一篇 2022-05-07
【php算法】有一母牛,到4岁可生育,每年一头,所生均是一样的母牛...问n年后有多少头牛?
下一篇 » 2022-05-07
取消
微信二维码
微信二维码
支付宝二维码

发表评论

共2条评论,1393人围观

头像 李海 说道:
2022-05-11 · 来自甘肃省兰州市 · Google Chrome 101.0.4951.41 Windows 10 x64

学这个 是不是得数学成绩要好?[Facepalm]

头像 勇康博客网 头像 说道:
2022-05-12 · 来自广东省深圳市 · Google Chrome 101.0.4951.54 Windows 10 x64

@李海 占一点吧,主要还是刷题,我之前面试碰到几次考这个算法的

作者信息

勇康博客网
承接企业、个人,仿站、定制。域名,主机一键代发
TA的最新作品

热门文章

2
3

动态快讯

标签列表

目录[+]