资讯专栏INFORMATION COLUMN

PHP算法趣谈--猴子找大王

FuisonDesign / 2431人阅读

摘要:一算法问题将一群猴子排成一圈,按照猴子数按照依次编号。在计算机编程的算法中,类似问题又称为约瑟夫环。问题是,给定了和,一开始要站在什么地方才能避免被处决四算法设计与实现算法问题存猴子名称给猴子定义名称定义猴子排序个数

一、算法问题

将一群猴子排成一圈,按照猴子数按照1,2,...,n依次编号。然后从第1只开始数,定义数m个猴子,之后将数到的猴子将它踢出圈,从它后面再开始数, 再数到第m只,在把它踢出去...,如此循环的进行下去,直到最后只剩下一只猴子为止,那只猴子就是大王。

二、算法思想及来源

递归函数

子函数调用

时间复杂度是O(n*m)

此算法问题来自于约瑟夫问题(来源维基百科)

三、算法原题

约瑟夫斯问题(有时也称为约瑟夫斯置换),是一个出现在计算机科学和数学中的问题。在计算机编程的算法中,类似问题又称为约瑟夫环。 有n个囚犯站成一个圆圈,准备处决。首先从一个人开始,越过 k-2个人(因为第一个人已经被越过),并杀掉第k个人。接着,再越过 k-1个人,并杀掉第k个人。这个过程沿着圆圈一直进行,直到最终只剩下一个人留下,这个人就可以继续活着。 问题是,给定了n和k,一开始要站在什么地方才能避免被处决?

四、算法设计与实现
 1) {
            if($j%$n==0){
                unset($arr[$j]);
            }else{
                $arr[] = $arr[$j];
                unset($arr[$j]);
            }
            $j++;
        }
        return $arr;
    }
    print_r(xdw(40, 3));
 ?>

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/30632.html

相关文章

  • 2018 PHP 面试总结

    摘要:最近面试了不少公司,正好把记得的问题做个总结。抽象类的接口的区别,不在于编程实现,而在于程序设计模式的不同。一般来讲,抽象用于不同的事物,而接口用于事物的行为。 最近面试了不少公司,正好把记得的问题做个总结。 本文 github 会持续更新 公众号 搜索 苏生不惑 或者扫二维码关注,每周更新。 showImg(https://segmentfault.com/img/bVbsYyM?w...

    William_Sang 评论0 收藏0
  • 2018 PHP 面试总结

    摘要:最近面试了不少公司,正好把记得的问题做个总结。抽象类的接口的区别,不在于编程实现,而在于程序设计模式的不同。一般来讲,抽象用于不同的事物,而接口用于事物的行为。 最近面试了不少公司,正好把记得的问题做个总结。 本文 github 会持续更新 公众号 搜索 苏生不惑 或者扫二维码关注,每周更新。 showImg(https://segmentfault.com/img/bVbsYyM?w...

    lunaticf 评论0 收藏0
  • 单类SVM:SVDD

    摘要:话接上文的简单推导,这篇文章我们来看单类。单分类方法常用于异常检测,或者类别极度不平衡的分类任务中。另一种思路就是,在样本空间中为此类数据划定一个大致的边界。上式表明所有样本的权重之和为,而球心是所有样本的加权和。 话接上文(SVM的简单推导),这篇文章我们来看单类SVM:SVDD。可能大家会觉得很奇怪,我们为什么需要单分类呢?有篇博客举了一个很有意思的例子。 花果山上的老猴子,一生阅...

    Leck1e 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<