登陆注册
37240300000004

第4章 十万级斐波那契

“依上题所述,若N在100000到400000之间,作何解?”

杨成深吸一口气,他明白自己此前的思路已经走到了尽头,必须得换一种方式了。

对于递归而言,十万级以上是遥不可及的一道天堑,不管怎样使劲,都只有一种结局——挂。

所以,他决定了,放弃递归,使用传统的线性方法,顺序遍历求解。

递归不是顺序的,斐波那契数列的分治法是一种深度遍历求解,递归栈中函数作用域对象的开辟和回收都需要很多额外的性能,而顺序遍历不存在这样的情况。

顺序遍历共享的是同一个作用域!

可以使用两个临时的变量,因为公式f(n)=f(n-1)+f(n-2)的缘故,要求第n项你只需要分别保存第n-1项和第n-2项的结果。

这样做,将算法的空间复杂度降到了最低,和递归庞大的保存栈相比,优势就太大了。

想清了思路,杨成正打算提笔就写,他突然想到一个令人震惊的后果。

对于JavaScript,浮点数是有大小限制的,对于第几十万项的斐波那契数,它显然已经远远超出了浮点型的范围,那么,自己这个算法会不会导致溢出?

好在他很快想通了,关卡设计者怎么会想不到这样的问题,自己只要能写出正确的算法来就OK了。

这个算法其实并不难,杨成用了十几行代码就搞定了,他心里其实还是有些忐忑的,作为一名准程序员,有这种意识其实还是挺正常的。

不是有个笑话吗,假如有人问一名程序员:你的程序是不是出Bug了?这个程序员听到后第一反应是:傻x你懂程序嘛?你会用嘛?而如果有人问程序员:这个效果和预期的有些不一致呢。那程序员肯定心想:糟了!肯定是出Bug了!

杨成看着小册子第三次浮空,他有些习以为常了。

舒服地打了个哈欠,伸了伸懒腰,他发觉一个有趣的现象。

这窗外的月亮是不是太完美了,可以说是无暇的。

古人都常说:人有悲欢离合,月有阴晴圆缺,你这月亮做的也太假了一点吧?!

是不是美工姐姐被拖欠了工资啊?

杨成恶狠狠地想着,在心里恶搞了一番游戏团队。

然后他翘着二郎腿,再给自己来了一杯焦炭咖啡。

时间过得很慢,这次小册子被翻页的时间和次数都多得多,显然和数据量有关。

杨成甚至怀疑是台286电脑在充当服务器处理,现代电脑有这么辣鸡嘛?是不是并发量太大了,服务器被挤爆了的缘故呢?

等到杨成开始怀疑这个小册子组件模块编写者性别取向问题的时候,小册子终于完成了它的使命,“啪”的一声“坠机”了。

“玛德,至少过去了半个钟头”,杨成嘟哝着,再次翻开小册子某页。

刚才写的那十几行代码旁边,又多了一个小小的对勾。

然而,还没来得及为自己高超的“手写代码”能力欢呼雀跃,杨成很快看到了让自己张大嘴巴的一个景象。

“嚯!”,他不禁倒吸一口凉气,犹如泄了气的皮球,倒在了后椅上。

“先前的思路又得改!”

同类推荐
  • 某不科学的能力者召唤

    某不科学的能力者召唤

    一小萝莉:雷欣,十一岁时忽然发现自己居然可以召唤出二次元的人物,最重要的是,自己会同时拥有那些能力,但是,自己也被白色面具人追杀。“小鬼,我说你到底是要做什么啊!”一方娘大吼着,雷欣:“表介意啦~~只是帮你修一修头发而已,女生就要有女生的样子嘛~~”一方娘沦陷。“姐姐我们来玩啊!”一群红眼的小萝莉大叫着,“好啊!我们来玩老鹰捉小鸡吧!”小萝莉沦陷。“欣儿……”某把妹手(不是当麻)深情的望着雷欣。“才不是喜欢你呢!”雷欣沦陷……等等,似乎有什么不对的样子,不过管他呢!PS:本书嫁人百合都有了!就懒得分嫁人还是百合了
  • 王的命运传说

    王的命运传说

    那一刻——你跟我说:“等我回来”。然后,我一直等到如今。可是,我已经厌烦了。我不想再空虚的等下去了。于是我来了。Fate——InfiniteEyesRoleSystem(命运之无限视野任务系统)会替我找到你的。弟弟,吾王!书友群——242215899、欢迎来吐槽!
  • 铁幕苍穹

    铁幕苍穹

    人类,一个濒于灭绝的物种!光照在黑暗里,黑暗却不接受光。铁幕苍穹下,无数的生命,在刚开始的时候,就被丧心病狂地毁灭了。
  • 狗血穿越之想不出名字来

    狗血穿越之想不出名字来

    逗逼猪脚淫刀在现实是一个杀手,结果世界灭亡,然后狗血穿越,大家去看,穿越的有《哈利波特》《火影忍者》《自己编的异世界》。。。。就是这样了,自己看吧。(建议大家看过原版的再看这个,因为不看的话,会感觉很讨厌,什么也不知道。)本来是想写末日来,结果看的人太少,所以就改成穿越了。(前面的挺难看的,建议从哈利波特之后的看。)
  • 节操无限

    节操无限

    大名鼎鼎的西门大官人,成功阴死了轮回世界的轮回者,继承了轮回者的无限空间,开始他的黑暗邪恶兼且无节操的无限征途。要做就做最强大的王者,睡最极品的女人!我是西门大官人,我始终坚信自己是一个有节操的人,请不要怀疑这一点!本书特点:节奏快,黑暗系,妹子性格突出,无需影视剧基础,配角都是其他小说主角的性格和际遇,被西门大官人坑的死去活来。西门庆特点;布局推理强,言语或蜜或刀,嘴炮无双。对妹子从不怀柔,各种凶残,与其他小说完全不同,另类爽文。!
热门推荐
  • 魔吞天下

    魔吞天下

    一颗碧血魔丹,生出可吸收别人修为的诡异天赋。世道无常,天道不公,仙道卑鄙。那我便心向魔道。我叫叶孤城,来自陈谷镇,出于仙山凌云渡。
  • 替妃洞房

    替妃洞房

    前世,她只为一个人活着,十年的追求换来如今的结局!不爱,不痴,一刀绝红尘——刀绝尘!今世,她为一张卖身契,替妃洞房!依旧无爱,为了怀中娇儿,为护他一生周全,她倾尽所有!本以为已经成为定局!岂料,意外的人,闯入——熟悉的面容,熟悉的气息,她笑!前世今世,她的命运果然坎坷!
  • 罗密欧与朱丽叶·威尼斯商人

    罗密欧与朱丽叶·威尼斯商人

    《罗密欧与朱丽叶威尼斯商人(凝聚男女情爱离 别的悲喜剧)》为“青少年成长必读经典书系”之一 。《罗密欧与朱丽叶威尼斯商人(凝聚男女情爱离别 的悲喜剧)》收录根据莎士比亚戏剧作品《罗密欧与 朱丽叶》、《威尼斯商人》改编缩写的两篇故事。
  • 雷起九霄

    雷起九霄

    五帝之一的雷帝因服用九阳圣果,转世重生到一个废物身上,开始炼九阳紫雷,逆天道轮回,一路高歌猛进,再踏大道巅峰。
  • 我的美女徒弟

    我的美女徒弟

    俗话说得好,要想学得会,先跟师傅睡。于是,钱江收了一群美女徒弟。
  • 福妻驾到

    福妻驾到

    现代饭店彪悍老板娘魂穿古代。不分是非的极品婆婆?三年未归生死不明的丈夫?心狠手辣的阴毒亲戚?贪婪而好色的地主老财?吃上顿没下顿的贫困宭境?不怕不怕,神仙相助,一技在手,天下我有!且看现代张悦娘,如何身带福气玩转古代,开面馆、收小弟、左纳财富,右傍美男,共绘幸福生活大好蓝图!!!!快本新书《天媒地聘》已经上架开始销售,只要3.99元即可将整本书抱回家,你还等什么哪,赶紧点击下面的直通车,享受乐乐精心为您准备的美食盛宴吧!)
  • 小一涅盘传

    小一涅盘传

    世上美男何其多,小一单恋一枝花?怎么可能。对你,我是爱着的。对你,我是放不下的。对你,我是舍不得的。都收了可以吗?
  • 邪灵猎手

    邪灵猎手

    万物皆有灵,得道能通灵。灵者,鬼魂也。——《赤松遗记》你相信有鬼吗?有鬼必有道士,一个个千年道术家族,带你走进你不知道的不为人知的得道者的世界。总的来说,就是平凡少年白洋进了一个不正常大学,进了不正常的社团,遇到不正常的妹子,发生不正常的事件。本文慢热,拜托各位看官看完前十章。
  • 暖婚之调教男神

    暖婚之调教男神

    “你好,我叫言君诺,言是言出必行的言。”“你好,我叫宁若凡,宁是宁折不屈的宁。”初次见面的自我介绍,看似波澜不惊,却暗藏激流。一个是唱演俱佳的全能偶像,万千少女眼中的国民男神一个是女承父业,心心念念只想拍尽天下美景的摄影师当‘言出必行’的大明星遇上‘宁折不屈’的摄影师当高冷狂傲遇上理性偏执,谁被谁驯服,谁被谁调教?(本文纯属虚构,请勿模仿。)
  • 异世之最强巫医

    异世之最强巫医

    医者,心怀天下;巫者,灭世而生。我要权杖天下,成就无上地位,雄霸万世......