快速业务通道

AS3面试题:复杂算法的改进

作者 凌众技术 来源 网页制作 浏览 发布时间 2012-03-08

最近在网上看到一个AS3面试题,感兴趣写了个答案,当然标不标准我就不知道了~

题目:
对一批编号为1-100全部开关朝上(开)的灯进行以下操作:
开关编号凡是1的倍数反方向拨一次开关;若该编号也是2的倍数反方向又拨一次开关;若该编号又是3的倍数反方向又拨一次开关……以此类推一直计算到100为止。
目的:请trace出经过反复开关操作后所有关闭的灯的开关编号。

这是我写给大家看的易懂版本:


var n:int, m:int;
var range:int = 100;
for(var i:int = 1; i <= range; i ++){
  n = 1;
  while(true){
    if(n > i / n){
      break;
    }
    if(i % n == 0){
      if(i / n == n){
        trace("结果",i);
        break;
      }
    }
    n ++;
  }
}

下面是写着玩的缩写版本,不过正常写项目代码,我不会这样干的,在这儿只是娱乐一下而已。下面这段代码想玩就看看,不想玩的看上面就行了,判断原理是一样,没区别!

var n:int = 1, range:int = 1000;
for(var i:int = 1; i <= range; i += n = 1){
  while(n > 0) n = n > i / n ? 0 : !(i % n) ? i / n == n ? -1 : n + 1 : n + 1;
  if(n == -1) trace("结果",i);
}

我将range都改成100000后,第一种方法耗时7233毫秒,第二种缩减的写法耗时1840毫秒。对于易读易懂,你会选择那种方法呢?

对于暗泪同学的回复,下面增加一点内容:
其实上面写的是正常算法,如果2亿次,通过分析题目,可以得出只要该数能被开平方时,就是关闭状态,因此这道题目如果是写在项目里面,可以这样写:

var range:int = 1000000000;
var num:int = Math.pow(range,0.5);
for(var i:int = 1; i <= num; i ++){
  trace("结果",i * i)
}

我测试过10亿次的效率,仅需要6毫秒~何其快啊!

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务,公司网站:http://www.lingzhong.cn 为了给广大客户了解更多的技术信息,本技术文章收集来源于网络,凌众科技尊重文章作者的版权,如果有涉及你的版权有必要删除你的文章,请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息,谢谢!

分享到: 更多

Copyright ©1999-2011 厦门凌众科技有限公司 厦门优通互联科技开发有限公司 All rights reserved

地址(ADD):厦门软件园二期望海路63号701E(东南融通旁) 邮编(ZIP):361008

电话:0592-5908028 传真:0592-5908039 咨询信箱:web@lingzhong.cn 咨询OICQ:173723134

《中华人民共和国增值电信业务经营许可证》闽B2-20100024  ICP备案:闽ICP备05037997号