登陆注册
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:种田流生活向,非科幻文,不会扣这种黑科技高新技术。o(╯□╰)o见谅。
  • 界系

    界系

    从21世纪开始,一场科技与自然带来的“基因变异”,从宇宙诞生那一刻开始隐藏的秘密,正在随着时间的流逝,逐渐浮出水面。
  • 别惹宝宝

    别惹宝宝

    本是超级特工的张可穿越到了平行宇宙之中……“啥?我以后只能是一个三岁宝宝的样子?天呐!这让我怎么活?!”“别惹宝宝,宝宝很生气!”“宝宝的目标是星辰大海!”一个特工宝宝,就这么横空出世了!我的后代该怎么办呐!张可郁闷的扑在美女的胸里……喜欢宝宝的朋友可以添加书友群:418370170
  • 达斯加神庙

    达斯加神庙

    世界上最大的南极富豪探险游船走到南级的最尽头,风却慢慢地大,船长发出回航信号,船主啊来出于内心的贪婪,指使其继续前进,最终船被券进了大风里走到了另世界的另一端,这里叫达斯加,啊来使出巴格魔语拔掉达斯加神庙的中转盘,整个小镇地动山摇,阿来全身被冰封,女主角啊来女儿雪伦神奇的没有被冰封,在惊恐无助之际,男主角达加斯王子巴纳到来神庙把雪伦抓了起来,而外星系迪亚星人开始进攻地球另一端北极,男主角如何拯救自己的小镇,女主人如何把爸爸拯救出来,他们又如何大战各国魔法人守卫这个地球?改变贪婪,暴力,自私?
热门推荐
  • 传奇天界

    传奇天界

    一个热血少年,在一次普通历练中,意外得到一种神秘未知的强大力量后一步步走向成功和辉煌……………………
  • 痴情王爷娇媚妃

    痴情王爷娇媚妃

    她,一名现代女子,奇妙的穿越之旅,让她遇上不一样的他。顾容吏远,大顾国的王爷,生得呆傻,像一个孩子那样对生活充满希望。司徒仪珊,一个充满智慧而且知性的女孩,被无数的人所喜欢着。因为一场政治婚姻,她被强行的嫁给了顾容吏远,成为了他的妻子。在后来的相处之中,两人感情渐渐产生,但是,一场政治风波却是将两人席卷。这一切,阻碍着两人的感情,为了捍卫他们的未来,他们执意相守,但迎来的结局又是怎么样的?【情节虚构,请勿模仿】
  • 末日积分系统

    末日积分系统

    末日病毒降临,恐惧伴随着死亡,人类文明逐渐崩溃,仅存的人类也苟且偷生,林原手持末日积分系统能否拯救这个崩坏的世界?
  • 我们的征途是星辰大海

    我们的征途是星辰大海

    一个励志成为宇宙战舰驾驶员的边缘殖民地少年,不断努力实现自己的梦想。四大帝国,家族财团,海盗势力,流亡组织,残酷的战斗,险恶的人心,利益的纷争,不断促使着少年的成长。拥有神秘科技的未知种族,关于人类种族起源的巨大秘密,陨落万年的异族文明,无数的秘密也等待着少年去一一揭晓答案。
  • 问道灵虚

    问道灵虚

    天方城在被魔修屠城之后,生机尽绝。但就在这没有生机的死城中,却是有一名活着的少年。在之后正道玄焰门修士前来查探原因之时,发现了这名少年,少年遂拜入玄焰门下,从此踏上了修仙之途。看少年如何在有着千般奇法,万般妙术,剑影刀光,生死刹那的修仙世界里,寻求长生大道。
  • 福妻驾到

    福妻驾到

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

    全世界为你唱这小情歌

    在一次又一次的错过中,我始终是要找到你的......年华与陆辰,青梅竹马,两小无猜。16岁时,陆辰漂洋过海美国。n年后,陆辰回国和苏年华重遇,可是他们不断的错过,爱意在心口难开。这时陆辰的同父异母的哥哥夜然突然出现在年华的生活中,三个人陷入情感危机。
  • 逆袭事务所:炮灰你来啦

    逆袭事务所:炮灰你来啦

    “他不懂你的心,我懂”Thisis逆袭事务所。只要你的东西好,啊呸,故事感人,我们就可以帮你改造您的人生。要男主?noproblem要男二?虽说姑娘你的问题有点偏激,但也是没问题滴【不要怪我脑洞太大,只怪你们接受能力太弱】作者无能,不会做封面。(大换血)
  • 邪王霸爱:摄政王妃倾天下

    邪王霸爱:摄政王妃倾天下

    一个是不受宠的将军嫡女,前有恶毒后娘,后有坏心妹妹!一个是权倾朝野的摄政王,左有文武双全,右有钱权势力!一朝穿越,她誓要赚尽天下银两,抱得帅哥归!想欺负我?哼!待本小姐钱袋装满,定拿银子砸死你们!哎!那边的摄政王!你别跑!咱两合伙开店可好!“娘子,今日抱为夫不抱银子可好?”“赤道有多远,你就给我滚多远!”“娘子,赤道为何物?”“……此物只可意会不可言传。”【甜宠萌,打脸啪啪啪!】
  • 商略

    商略

    经商要有所成就,必须既要稳健,又要敢冒大险:既要有洞察商机的火眼金睛,又要有快速出手的行动力;既要能够发挥自身的经营智慧,又要善于借用他人的力量。经商是现代人追求成功人生的一条捷径,尽管荆棘密布,只要你用心,就一定能通过最适合自己的经商策略到达终点。本书对经商的一般性策略在九个方面做了对比性的归纳。包括:虚实策略、进退策略、出入策略、冷热策略、大小策略、敌友策略、缓急策略、新旧策略、主从策略。