用户名: 密码: 忘记密码? 注册
收藏此问题 发表新评论

一些公司笔试中出现猴王算法(约瑟夫环)掀起了一股猴子潮

本帖最后由 hmly 于 2011-11-4 17:41 编辑

首先啊!作为一PHP程序猿要确定,算法啊,被用到的可能性几乎趋近于0,但是啊,算法是一门修行外加一些蛋痛装B公司爱考这些,所以啊,还是鼓励大家在闲得蛋痛的时候折腾一下算法。

我再重申一下我是个PHP程序猿,所以啊,喜欢用最简单直接的程序来解决问题,解决猴王问题不想那么多高深的了,直接一个一个数。{:soso_e120:}
  1. function monkeyKing($n, $m) {
  2.     $i = 0;
  3.     $monkeys = range(1, $n); //初始化猴子
  4.     while (count($monkeys) > 1) {
  5.         if ($i > 0) {//因为指针默认指向第一个,所以刚开始数就不要移动指针了
  6.             if (!next($monkeys)) {
  7.                 reset($monkeys); //数到头了,从头开始数
  8.             }
  9.         }
  10.         $i++;
  11.         if ($i == $m) {
  12.             unset($monkeys[key($monkeys)]); //干掉猴子
  13.             if (!current($monkeys)) {
  14.                 reset($monkeys); //如果删除的是最后一个猴子则指向第一个猴子
  15.             }
  16.             $i = 0;
  17.         }
  18.     }
  19.     return current($monkeys);
  20. }
复制代码



最后还是佩服一下这种算法:

  1. function monkeyKing($n, $m)  //n只猴,m个排除。
  2. {
  3.             $z=0;//z是王
  4.             for ($j = 2; $j <= $n; $j++) $z = ($z + $m) % $j;
  5.             return ++$z;
  6. }
  7. echo monkeyKing(5, 3);
复制代码



昵称: hmly  时间: 2011-11-04 17:41:25
上次我面试也是这个题,哎,没答上来{:soso_e110:}
昵称: freewills  时间: 2011-11-04 17:50:51
世界上有三种算法:ACM竞赛用的“算法”,招聘面试中的“算法”,算法。
昵称: aCat  时间: 2011-11-04 17:56:40
freewills 发表于 2011-11-4 17:50
上次我面试也是这个题,哎,没答上来

你点背哈!
不过是我可能现场也答不出来。
昵称: lovegx999  时间: 2011-11-04 18:11:36
aCat 发表于 2011-11-4 17:56
世界上有三种算法:ACM竞赛用的“算法”,招聘面试中的“算法”,算法。

悟透了
昵称: hmly  时间: 2011-11-04 18:35:49
算法依旧是算法!
昵称: hmly  时间: 2011-11-04 18:38:01
第二个像是数学家写的。
昵称: zhuifengxhl  时间: 2011-11-04 19:53:34
谢谢楼主分享!又长见识了{:soso_e113:}
昵称: shanzejun  时间: 2011-11-04 20:11:41
怎么能说算法是装逼用的呢,除非你不是程序员
昵称: yubozyh  时间: 2011-11-04 21:10:26
只有外行才说得出来这个话: "算法啊,被用到的可能性几乎趋近于0"
当你用代码解决了任何一个具体的问题(哪怕是最简单的交换两个标量值), 本身就已经是一个广义上的算法了.
昵称: iminto  时间: 2011-11-04 22:31:22
没有认真学过算法的人, 也可以做程序做网站可以赚非常多的钱, 但无法被看作真正的程序员
尤其是在傻瓜式的ASP时代, 做网站的人超过90%根本不懂算法. 他们无法解决稍微复杂一点的问题, 也无法理解代码的"性能"是什么意思
昵称: sztime  时间: 2011-11-06 03:42:29
本帖最后由 hmly 于 2011-11-6 13:31 编辑
sztime 发表于 2011-11-6 03:42
只有外行才说得出来这个话: "算法啊,被用到的可能性几乎趋近于0"
当你用代码解决了任何一个具体的问题(哪 ...


只能说明你的小学语文没过关,你没见前面有“作为一PHP程序猿”这个前提吗?搞PHP还没有javascript用到算法的时候多。
另外交换两个变量值用到位运算就算是算法了,那我还真不会算法。另外就像你说的算法是用来解决问题的不是用来干哪个啥的
昵称: sztime  时间: 2011-11-06 03:52:12
sztime 发表于 2011-11-6 03:52
没有认真学过算法的人, 也可以做程序做网站可以赚非常多的钱, 但无法被看作真正的程序员
尤其是在傻瓜式的A ...

我也有学习和使用C,C#它们几乎无时不刻不用到数据结构和算法。
所以你还是先回去学好语文再说吧!
昵称: hmly  时间: 2011-11-06 13:06:48
另外我承认我是踩着某些人的尾巴了。
纯搞PHP真的用到了算法?如果连无限级联菜单和递归,以及平时一些数据统计分析也算的话,可能纯搞PHP的也算用上算法了。如果有其它时候用到的请11楼举例。

另外为php,apache,nginx,mysql写扩展的PHP程序猿已经不是PHP程序猿,他们是会用PHP的C/C++程序猿或DBA。但我们现在讨论的是纯PHP程序猿。
昵称: hmly  时间: 2011-11-06 13:07:50
说PHP程序用不到多少算法, 那只是因为你们做的PHP太简单, 前台就那么几个页面, 后台拿别人的模板乱改一气, 当然扯不上多少算法了
昵称: hmly  时间: 2011-11-06 13:28:24
本帖最后由 hmly 于 2011-11-6 13:39 编辑
sztime 发表于 2011-11-6 13:31
说PHP程序用不到多少算法, 那只是因为你们做的PHP太简单, 前台就那么几个页面, 后台拿别人的模板乱改一气,  ...


所以啊哥们儿我也说了,你的招聘要求显然是招c/c++程序员只是要求他们会些php,如果说公司里面php和c,java的价钱一样的话出于公平考一考也还成,但是掌握着系统底层架构和数据分析功能C和JAVA咋可能比php工资低啊!
你说像坛子里面鸟哥和黑夜路人,逆雪寒这些个牛人们我真不敢说他们还是纯phper
另外像这道题据说是中关村某公司开始后其它公司跟风才出这样的笔试题,所以才让人BS
昵称: sztime  时间: 2011-11-06 13:31:24
本帖最后由 iminto 于 2011-11-6 14:36 编辑

     不会算法的请不要叫程序员,叫网页制作者或XXXer,XXX爱好者更合适。我从不把不会算法的人当程序员看。他们可以解决一些购物网站,留言本等网站的制作,但遇到核心应用就软了,就算勉强能写出来,写出来的代码不堪入目。

我可以举出很多例子,在WEB应用中使用算法的例子,有些也是我参与过的:
1.公交路线中的图算法
2.自动排课,客服排班系统中的遗传算法,这个是我们做过的
3.web网游中的A*寻路算法
4.数据挖掘,这个也是我们做过的。
5.ERP系统中的等等任务分配,运筹学等的应用
。。。。


昵称: hmly  时间: 2011-11-06 13:36:24
iminto 发表于 2011-11-6 14:31
不会算法的请不要叫程序员,叫网页制作者或XXXer,XXX爱好者更合适。我从不把不会算法的人当程序员看。 ...

根据需求招人是对的,不过不根据公司业务需求而跟风考算法是让人讨厌的。
另外
1、公交地铁路线算法能允许php组的人来做,那真是看得起php开发组的人了,或许数据量小的时候还真可行
2、排课,排班感觉也是简简单单的算法啊
3、web游戏没接触过不清楚,如果都是用php做,那真是太好了
4、数据挖掘这块我所经历的公司和从朋友同事听到过的全部用C或JAVA,公司能用php来做像用户行为分析这些真是太好了,尤其是像pv接近上亿,日志TB级别的分析。
5、运筹学?没搞过ERP,我使用过的ERP全是JAVA和.NET的。我想去搞诸如SugarCRM这样系统的PHPER确实需要一些算法。
昵称: iminto  时间: 2011-11-06 14:31:26
本帖最后由 iminto 于 2011-11-6 15:41 编辑
hmly 发表于 2011-11-6 14:55
根据需求招人是对的,不过不根据公司业务需求而跟风考算法是让人讨厌的。
另外
1、公交地铁路线算法能允 ...

      你说的是,搞php的确实很少接触算法,70%以上在算法上是空白。。。毕竟是以网页制作为主。事实上这些需求很多也是由java和C程序员去实现的。不过考算法还是有需求的,如果没有一点数据结构和算法思想的,只会做做网站,那思维必然很局限,我想也做不出啥有创意和突破性的东西。还不如花1500找几个初中生进来培训三个月,就完全可以胜任了,不就是CURD和HTML这些东西么。公司肯定都想物有所值的。。。
      我觉得不论什么程序员考点算法肯定是有意义的。

   排班系统还是很复杂的啊,涉及冲突检测,自动合并,优先级变动,临时调整等,比如某天某个人突然请假了,加班了,上课地点冲突了,遇上节假日啦。。。考虑的因素是很多的,特别是一个学校两万名学生,5-500,2000多名教职工的时候就不简单了。
    数据挖掘用php肯定是干不了的,就连用java都很吃力,只能用C系列的语言。

    不过我们参加的这个确实都是java和c++干的。
昵称: hmly  时间: 2011-11-06 14:55:05
对一个好程序员来说, 算法也是一种隐性的约束.
比如一个开车的人, 时时刻刻都在注意前面是否有红灯, 是否有人正在或打算穿越马路, 路上是否有异物等等, 而另一个骑单车的人他就不用考虑这么多, 横冲直撞, 逆行的都大有人在.
认真学过算法并尊重算法的人, 他在敲入每一行代码之前, 脑中就已经自动的思考过了这行代码可能会出现的问题, 会不会影响性能, 以及有没有更好的替代语句. 注意, 这完全是无意识的习惯和行为. 而普通的代码员, 他们的任务则是尽快完成任务, 只要代码能运行并给出想要的结果就够了, 至于性能问题和BUG, 那统统是后期的事了.
不过物极必反, 有时候这种好习惯也会变成一种痛苦, 尤其是对于一些完美主义者(或者有洁癖者).
昵称: iminto  时间: 2011-11-06 15:35:33
PHP是适合做网站
但说PHP不适合做复杂的功能是他根本没有用PHP做过复杂的系统, 完全在扯蛋
AJAX+LIINUX+MYSQL+PHP+MEMCACHED 实现一个复杂的WEBGAME的全部是完全没有问题的(包括战斗引擎)
而且日流量在2亿以上
昵称: sztime  时间: 2011-11-09 18:13:43
sztime 发表于 2011-11-9 18:13
对一个好程序员来说, 算法也是一种隐性的约束.
比如一个开车的人, 时时刻刻都在注意前面是否有红灯, 是否有 ...

这个貌似很高深。。。。
昵称: qiannz  时间: 2011-11-10 13:05:29
本帖最后由 hmly 于 2011-11-10 16:06 编辑
qiannz 发表于 2011-11-10 13:05
PHP是适合做网站
但说PHP不适合做复杂的功能是他根本没有用PHP做过复杂的系统, 完全在扯蛋
AJAX+LIINUX+MYS ...


复杂===算法??

以你的说法就是访问量大就一定是php的功劳?

像新浪微博支撑起那么大的访问量而且信息延时相当小的系统redis,memcachd,mongodb,jetty,netty...
这些是php的功劳?

别在这儿炫了,好像别人没做过亿级PV的网站似的。
正是使用过php做过大访问量和大负载网站的人才知道,php只是写表现层和应用,哪儿用什么算法。
昵称: hxfsc  时间: 2011-11-10 13:06:16
我才不管什么算法不算法,老板肯发钱就是王道。
我才不管什么技术不技术,客户点头汇款到我帐号才是正道。
我才不管什么语言不语言,实现需求收到外快才是真理!
昵称: hmly  时间: 2011-11-10 16:03:36
我以前的老板,曾经是金蝶的开发人员,他跟我说过一句话:能为企业创造价值的技术,才是有用的技术。

客户才不管你用了什么技术,才不管你用了什么算法,才不管你用了什么语言,满足他的要求,一切皆是浮云!
昵称: ayinsky  时间: 2011-11-10 17:42:04
活着才是王道
昵称: ayinsky  时间: 2011-11-10 17:43:41
楼下的说的很好 学习中。。。
昵称: howk  时间: 2011-11-11 12:26:06
看了大牛们的激烈的讨论,太高深了
昵称: 徐长发  时间: 2011-11-11 12:40:11
哇噻,这个东西深了...
昵称: lason  时间: 2011-11-11 12:42:30
要结果!
昵称: DODOphp  时间: 2011-11-14 16:18:54
输出顺序
function excutePush($test, $m){
        $i = 0;
        while(count($test) >0){
            for($j = 0; $j < $m - 1; $j ++){
                $i ++;
                if($i >= count($test)){
                    $i = 0;
                }
            }

            echo $test[$i] . "\n";
            array_splice($test, $i, 1);

            if($i > count($test) - 1){
                $i = 0;
            }
        }
    }
昵称: thizluo  时间: 2011-11-14 16:35:14
21楼说得比较好,算法是一种灵感,贯穿代码,难以言语表达。
就好像DOTA高手,每个走位都有思想和规律,而且很自然地做到,
菜鸟永远只会打酱油,被虐N次都不会明白的。
昵称: z32556601  时间: 2011-11-15 12:26:00
严重感觉我IQ不足。
昵称: gcd  时间: 2011-11-15 20:12:24
目前一个算法都不会,就会加减乘除,还计算的比较慢
昵称: 片羽  时间: 2011-11-15 22:17:21
第二种的写法很给力,思维有点绕
昵称: minoc  时间: 2011-11-16 11:56:48
算法真是一片空白啊。
没算法的程序员不是程序员。真心失败。。
昵称: 重庆一枝花  时间: 2011-11-27 15:16:54
只做PHP开发的话,如果实际工作中会遇到这种问题,那多半是架构设计有问题。不过从提高自身修养的角度出发,多了解了解,还是有好处的。
昵称: leiyu  时间: 2012-08-03 11:40:52
算法依旧是算法!
昵称: Simonsen  时间: 2012-08-04 10:18:48
所以现在的好多游戏都是爆玩家的电脑内存,在炎热的夏天被崔的2G的内存的笔记本都不够用啊就是上面那种只赚钱不求科学优化的人多了,现在我基本是爆内存的直接KILL掉
昵称: dolala999  时间: 2012-08-06 10:23:48
问一个问题 为什么复制一个几十M的文件只需1-2秒 而打开一个几十M的文集却要很久时间了

知道的请回答
昵称: h280338871  时间: 2012-08-06 13:11:31
ayinsky 发表于 2011-11-10 17:42
我才不管什么算法不算法,老板肯发钱就是王道。
我才不管什么技术不技术,客户点头汇款到我帐号才是正道。
...

现实最重要。。
活着最重要啊。。
一切的技术只是为了满足客户的需求。。
这个在理
昵称: h280338871  时间: 2012-08-06 13:13:52
艺多不压身,努力学习吧
昵称: 除美灭日平韩  时间: 2012-08-13 11:19:18
谢谢楼主分享!又长见识了
昵称: 剑枫  时间: 2012-08-13 15:57:31
mark第二此
昵称: dolala999  时间: 2012-08-16 10:59:41
路过顶一顶!!!
昵称: chenyachao  时间: 2012-08-16 13:07:08
厉害啊,看不懂
昵称: luhannah  时间: 2012-08-16 14:24:38
厉害啊,看不懂
昵称: zdenfey  时间: 2013-06-06 17:51:47
发表评论
昵称:
内容:
验证: