博主信息
编程三昧
博文
8
粉丝
0
评论
0
访问量
2538
积分:0
P豆:16

JavaScript 实现:输出斐波那契数列

2021年06月26日 23:07:50阅读数:383博客 / 编程三昧

问渠那得清如许,为有源头活水来。

想要保持自己的技术活力,最有效的手段就是通过不断地输入来提供足够的养分。我们也不必刻意追求高深的或者新鲜的知识点,通过对一个基础问题的全方位多维度解析,同样也会收获不小。

发散思维

题目

有这么一道题目需要我们来解答:

  • 试输出斐波那契数列的前10项,即 1、1、2、3、5、8、13、21、34、55。

分析

有些人看到题目中出现了“斐波那契数列”这个概念后,可能脑袋就蒙圈了,其实大可不必!

对于这道题,可以不用理会这个陌生概念,我们只需要关心后面它给出的数字规律即可。

我们可以看到,规律总结起来就一句话:从第三位开始,后面每项的值等于前两项之和,用式子表示的话就是:a~n~ = a~n-1~ + a~n-2~(n ≥ 2) 。

根据题目要求,其实就是要我们做两件事:

  1. 生成每一项的值。

  2. 打印输出所有值。

基础解法

解题思路:

  • 创建一个数组存放数列各项的值。

  • for 循环生成数列各项并存入数组(为了计算后面各项的值),打印生成的项。

代码实现如下:

/** * @description 创建一个生成数列数组的方法 * @param {number} n 表示要生成多少项(即数组长度,不是数组下标) */function createFibArr(n) {    // 声明一个存放数据的数组    let fibArr = [];    // 从第三项(下标为2)开始,每一项都等于前两项之和    for (let index = 0; index < n; index++) {        index < 2 ? fibArr.push(1) : fibArr.push(fibArr[index - 1] + fibArr[index - 2]);        console.log(fibArr[index]);    }}// 调用方法createFibArr(10);

分析:

这应该是最基本的解题方法,很容易就实现了。

但如果这是面试题的话,这样的答案只能说是中规中矩,没有出彩的地方,最重要的是体现不出我们与众不同的气质啊,所以,我们应该用点其他的手段来提升下自己的逼格!

初级递归

解题思路:

  • 通过递归的手段计算出各位置对应的值(这里有个前提是:第一项和第二项是确定值,否则,递归就不好用了)。

  • 打印结果。

代码实现如下:

/** * @description 计算出第 n 项的值 * @param {number} n 表示每一项的下标值 * @returns {number} 下标为 n 的位置的值  */function calFibValue(n) {    console.count("执行次数:")    return n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));}/** * @description 打印计算结果 * @param {number} n 代表要打印多少项 */function printRes(n) {    for (let index = 0; index < n; index++) {        console.log(calFibValue(index));    }}// 调用打印方法printRes(10);// 执行次数:: 276

分析:

递归的使用确实提升了代码的逼格,但是又引来了另外一个问题:性能问题。

每一项的值都是从第一项开始计算累加 出来的,比如计算第四项的值,其过程如下:

  1. 返回第一项的值:1 。

  2. 返回第二项的值: 1 。

  3. 计算第三项的值为 1 + 1 = 2 。

  4. 计算第四项的值为 2 + 1 = 3 。

在计算第五项值的时候,还要经过上面这个过程来获取第四项的值,进行了大量的重复运算。

为了惊艳面试官,我们还需要再做优化!

递归优化

解题思路:

  • 导致重复计算的是递归那部分的逻辑,所以优化点在递归这里。

  • 既然存在重复运算,那就意味着其实后面的运算完全可以使用前面已经计算出来的值,所以我们需要引入缓存来保存每次的计算结果。

代码实现:

/** * @description 计算出第 n 项的值 * @param {number} n 表示每一项的下标值 * @returns {number} 下标为 n 的位置的值  */// 存放每次计算结果的 Map 结构// 这里也可以用数组,但是在语义方面没有 Map 或对象直接let fibValueMap = new Map();function calFibValue(n) {    console.count("执行次数:");    // 如果缓存中已存在对应的值,则直接返回    if (fibValueMap.has(n)) {        return fibValueMap.get(n);    }    const value = n < 2 ? 1 : (calFibValue(n - 1) + calFibValue(n - 2));    // 在计算出每一项的之后,需要及时存入 Map    fibValueMap.set(n, value);    return value;}/** * @description 打印计算结果 * @param {number} n 代表要打印多少项 */function printRes(n) {    for (let index = 0; index < n; index++) {        console.log(calFibValue(index));    }}// 调用打印方法printRes(10);// 执行次数:: 26

分析:

根据打印出来的 count 来看,优化后的递归次数是优化前的 1/10 左右,这个结果就很惊喜了。

这次面试官应该可以满意了吧。

总结

万变不离其宗,只要将解题思路理清了,代码实现只是一个结果而已。在平常的工作学习中,我们要有意识地培养自己的发散性思维,从多角度去看待问题,你可能会发现不一样的风景哦!希望能够对大家有所启发哦!

在面试中,为了突显自己的独特气质或者人家面试题目就有具体要求的,我们使用一些看起来高大上的思路,这无可厚非。

但是呢,在平常的工作中,我还是更建议大家:在性能相近的情况下,能使用基础方法解决的一般不要用“高档”方法,因为基础方法出错的概率小很多。就比如今天这道题,其实基础解法的性能是最好的。

少写 BUG,我们才能有更多的时间来摸鱼,不是吗?

~

~ 本文完,感谢阅读!

~

发散思维

版权申明:本博文版权归博主所有,转载请注明地址!如有侵权、违法,请联系admin@php.cn举报处理!

全部评论

文明上网理性发言,请遵守新闻评论服务协议

条评论
  • javascript的方法:1、使用递归方法,代码如“function fib(n){...}”;2、使用for循环,代码如“for(var i=2;i<n;i++){..
    下面由javascript教程栏目给大家介绍JS的三种方法,希望对需要的朋友有所帮助!