js打印斐波那契数列(JavaScript输出斐波那契数列的实现方法)
js打印斐波那契数列
JavaScript输出斐波那契数列的实现方法目录
- 题目
- 分析
- 基础解法
- 初级递归
- 递归优化
- 总结
有这么一道题目需要我们来解答:
- 试输出斐波那契数列的前10项,即 1、1、2、3、5、8、13、21、34、55。
有些人看到题目中出现了“斐波那契数列”这个概念后,可能脑袋就蒙圈了,其实大可不必!
对于这道题,可以不用理会这个陌生概念,我们只需要关心后面它给出的数字规律即可。
我们可以看到,规律总结起来就一句话:从第三位开始,后面每项的值等于前两项之和,用式子表示的话就是:an = an-1 + an-2(n ≥ 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 。
- 计算第三项的值为 1 + 1 = 2 。
- 计算第四项的值为 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,我们才能有更多的时间来摸鱼,不是吗?
到此这篇关于JavaScript输出斐波那契数列的文章就介绍到这了,更多相关JS输出斐波那契数列内容请搜索开心学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持开心学习网!
- JS实现金额大小写转换
- python将对象转换成json(python对象与json相互转换的方法)
- angularjs数据绑定类指令及作用(详解Angular数据绑定及其实现方式)
- extjs tabPanel的用法
- vuejs组件使用教程交流(Vue vee-validate插件的简单使用)
- 详解JS中你不知道的各种循环测速(详解JS中你不知道的各种循环测速)
- ExtJs中XTemplate使用
- vue.js 怎么做插件(Vue.js实现音乐播放器)
- js中作用域
- js事件冒泡与事件捕获(基于事件冒泡、事件捕获和事件委托详解)
- 动画用css3还是js(前端制作动画的几种方式css3,js)
- javascript写游戏脚本(原生JS实现飞机大战小游戏)
- lombok 代码行数(Lombok实现方式JSR-269)
- js的showModalDialog的用法
- extjs Border边框布局
- extjs xtype的使用
- 我们现在吃的苹果是哪里来的 原来现代苹果引入中国仅有一百多年(我们现在吃的苹果是哪里来的)
- 买绿宝不能只挑黄绿色 菜农教你3招挑,个个皮薄肉脆,香甜爆汁(买绿宝不能只挑黄绿色)
- 大果肉搭配薄瓜皮, 绿宝 脆甜爽口,不愧是甜瓜中的 佼佼者(大果肉搭配薄瓜皮)
- 河南尉氏县因地制宜发展果蔬种植 水坡镇绿宝甜瓜变 金瓜(河南尉氏县因地制宜发展果蔬种植)
- 谢广坤,你这么欺负谢腾飞,良心不会痛吗(你这么欺负谢腾飞)
- 乡村爱情15 宋晓峰怀疑自己孩子,腾飞与姜奶奶亲子鉴定出结果(宋晓峰怀疑自己孩子)
热门推荐
- html5video怎么优化(HTML5 video循环播放多个视频的方法步骤)
- ubuntu16.04开机默认root(新版ubuntu20.04 使用root用户登录系统的详细教程)
- html5怎么设置左边input(HTML5中input输入框默认提示文字向左向右移动的示例代码)
- 优化SQL语句,提高数据库的访问性能
- 有了云服务器还需要服务器吗(为什么云服务器淘汰了传统服务器?)
- 免费的云服务器是什么(云服务器是什么?云服务器贵不贵呢?)
- python format的用法(Python中format格式输出全解)
- docker compose使用方法(docker和docker-compose一键安装教程支持在线和离线)
- webgl api 源码(基于 HTML5 WebGL 实现的医疗物流系统)
- linux怎么恢复删除的数据(Linux利用lsof/extundelete工具恢复误删除的文件或目录)