资讯专栏INFORMATION COLUMN

太原面经分享:如何用js实现返回斐波那契数列的第n个值的函数

Galence / 3175人阅读

摘要:那其实这个问题还可以换个问法实现一个函数,输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面,欢迎关注

面试攒经验,let"s go!

值此高考来临之际,闲不住的我又双叒叕出发去面试攒经验了,去了公司交待一番流程后,面试官甩给了我一张A4纸,上面写着一道js算法笔试题(一开始我并不知道这是在考察js算法),上面写着“1、1、2、3、5、8......,求第n个数的值

不得不承认,当时我第一眼看这道题大脑里是懵逼的。后来才想起来,这不就是数学题里的那个斐波那契(肥婆纳妾)数列么!从第三个数开始,每个数都是前两个数的和。

能get到这个点,你已经成功了一半了。另一半就是需要你将数学公式逻辑转变成js程序逻辑。

那其实这个问题还可以换个问法:实现一个函数,输入一个数字n能返回斐波那契数列的第n个值。

分析思路

首先,思路很重要,让我们一起来分析一下,大概的思路是这样的:

首先我们要把特殊的部分给独立出来做个判断,哪些数字是特殊的呢?很明显是斐波那契数列的前两项,而斐波那契数列的前两项都为1。然后定义三个变量,firstNum、secondNum、total,分别代表着第一个数字,第二个数字,还有他们俩之和。
然后通过一个for循环遍历,将firstNum加上secondNum的结果赋值给total,然后将secondNum的value赋值给firstNum,把total的value赋值给secondNum,以此根据传入的n来不断地循环叠加,达到想要的total值,最后return返回出去。

思路说完后,让我们用js把它实现出来:

// 可能是最普通的解法

var series = function (n) {

  var sum = [0, 1];

  if(n < 2) {

    return sum[n];

  }



  var firstNum = 0;

  var secondNum = 1;

  var total = 0;



  for (var i = 2; i<= n; i++) {

    total = firstNum + secondNum;

    firstNum = secondNum;

    secondNum = total;

  }

  return total;

}
面试题的最优解

记住,面试官与咱们应聘者的思维不同,你应聘的时候你大部分时间是在想,这道题我会不会做,能不能做出来,而他们想的是这道题的最优解。

前端的工作,“最优解”其实是一种自我追求进步的表现。

除了以上这种办法,还有什么更好的解决办法吗?答案是有的。

先来看看迭代的解法

var series = function (n) {

  var feipo = [0,1];

  for(var i=2;i<=n;i++){

    feipo[i] = feipo[i-1] + feipo[i-2]

  }

  return feipo[n];

}

// console.log(series(6));

再来看看递归的解法

var series = function (n) {

  if(n >= 2) {

    return series(n-1) + series(n-2)

  }else {

    return n;

  }

}

// console.log(series(6));

究竟哪个才是最优解,相信看完文章的你们已经有了答案。

可能你们会问:

那闰土你在笔试时做出来了么?
你猜~
写在后面

目前为止我也参加过很多次大大小小的前端面试,确实也听说过有不少面试官会问到一些算法。通常会涉及的,是链表、树、字符串、数组相关的知识。前端面试对算法要求不高,似乎已经是业内的一种共识了。虽说算法好的前端面试肯定会加分,但是仅凭常见的面试题,而不去联系需求,很难让人觉得,算法对于前端真的很重要。

直到有这么一天,太原这家公司的前端leader给我出了这么一道js算法题之后,还跟我聊了很多内容,与我固有的思维产生了强烈的碰撞。面试官还跟我讲,他们公司的技术总监是微软出身,很注重算法这块,他当初应聘进来的时候,也是考察的算法。

虽然这次面试被pass了,但是我认为工程师都应该学习算法,我觉得那不仅仅是对软件工程思想的培养,更是一种对心智的锻炼。

文章预告:更多的前端面试分享我都会第一时间更新在我的公众号<闰土大叔>里面,欢迎关注!

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

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

相关文章

  • JS专题之memoization

    摘要:前言在计算机领域,记忆是主要用于加速程序计算的一种优化技术,它使得函数避免重复演算之前已被处理过的输入,而返回已缓存的结果。被执行了不是素数,其他数字默认是素数。我们可以看出,如果从开始打印斐波那契数列,函数被执行了次。 前言 在计算机领域,记忆(memoization)是主要用于加速程序计算的一种优化技术,它使得函数避免重复演算之前已被处理过的输入,而返回已缓存的结果。 -- wi...

    zhisheng 评论0 收藏0
  • Python全栈之路系列之递归

    摘要:所谓递归其实就是函数本身调用函数,直到满足指定条件之后一层层退出函数,例如从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢故事是什么呢从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢故事是什么呢从前有座山,山里有座庙 所谓递归其实就是函数本身调用函数,直到满足指定条件之后一层层退出函数, 例如 从前有座山,山里有座庙,庙里有个老和尚,正在给小和尚讲故事呢!故事是...

    kviccn 评论0 收藏0
  • js 实现斐波那契数列(数组缓存、动态规划、尾调用优化)

    摘要:根据该规则,返回第个斐波那契数。尾递归函数调用自身,称为递归。一个前端眼中的斐波那契数列解斐波那契数列的实用解法调用栈尾递归和手动优化尾调用优化译我从用写斐波那契生成器中学到的令人惊讶的件事 斐波那契数列是以下一系列数字: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在种子数字 0 和 1 ...

    赵连江 评论0 收藏0
  • 《Python有什么好学的》之生成器/迭代器

    摘要:为什么是斐波那契谈到生成器迭代器,人们总是喜欢用斐波那契数列来举例。那么,换句话来说,即能由推导式得出的数列,其实都可以用来做生成器迭代器的例子。然而,生成器和生成器类的实例都属于迭代器。 Python有什么好学的这句话可不是反问句,而是问句哦。 主要是煎鱼觉得太多的人觉得Python的语法较为简单,写出来的代码只要符合逻辑,不需要太多的学习即可,即可从一门其他语言跳来用Python写...

    n7then 评论0 收藏0
  • 每周一练 之 数据结构与算法(Queue)

    摘要:与堆栈区别队列的操作方式和堆栈类似,唯一的区别在于队列只允许新数据在后端进行添加。移除队列的第一项,并返回被移除的元素。三使用队列计算斐波那契数列的第项。前两项固定为,后面的项为前两项之和,依次向后。 showImg(https://segmentfault.com/img/remote/1460000019005270); 这是第二周的练习题,这里补充下咯,五一节马上就要到了,自己的...

    anquan 评论0 收藏0

发表评论

0条评论

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