javascript用三种不同的方法来求斐波那契数

valiant小东

2024-04-30 帮助1人

前言：

本文主要讲三种算法：

迭代法

递归法

公式法

正文对概念部分不做多余讲解。

文章末尾有使用方法讲解，哪怕是小白，也会让代码运行起来！

如果觉得写的不错，就点个赞支持一下把！

学新通

今天在网上看到一个关于求第n个斐波那契数的题，虽然是个很简单的问题，分享给大家。希望看完这篇文章的你能够有所收获，原题是这样的：

用 JavaScript 实现斐波那契数列函数,返回第n个斐波那契数。 f(1) = 1, f(2) = 1 等

什么是斐波那契数列？

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……在数学上，斐波那契数列以如下被以递推的方法定义：F(0)=0，F(1)=1, F(n)=F(n - 1) F(n - 2)(n ≥ 2，n ∈ N*)。

简单点来说，斐波那契数列中的数要满足如下的通项公式：

$学新通$

开始解题

分别使用递归法、迭代法和公式法，这三种方法来求斐波那契数。下面直接copy源码加注释，对于三种方法的原理。此处就不再讲解。

方法一：递归法

递归的基线条件就是用户输入的n，递归条件就是f(n-1) f(n-2)。

function fibonacci(n) {
if(n == 0){
// f(0) == 0
return 0;
}else if(n == 2 || n == 1){
// f(1或者2) == 1
return 1;
}else if(n > 2){
// 大于2 递归
return fibonacci(n-1) fibonacci(n-2);
}else{
// 不合法输入提示
alert("please give me a right number !");
}
}
// 获取用户输入
let select = prompt("what is the Fibonacci number you ask for?");
// 输出最终结果
let result = fibonacci(select);
alert(result);

输入测试：

输入：42

输出：267914296

执行耗时：1582.166015625 ms

方法二：迭代法

function fibonacci(n) {
if (n == 0) {
// f(0) == 0
return 0;
} else if (n == 1 || n == 2) {
// f(1或者2) == 1
return 1;
} else if (n > 2) {
// 大于2 开始迭代
let fA = 0; // 第一个数
let fB = 1; // 第二个数
let result = 0; // 结果
// 开始循环从2开始循环循环执行一次，3 执行两次(再2的基础上在执行一次)，......
for (let i = 0; i < n - 1; i ) {
result = fA fB;
fA = fB;
fB = result;
}
return result;
} else {
// 不合法输入提示
alert("please give me a right number !");
}
}
// 获取用户输入
let select = prompt("what is the Fibonacci number you ask for?");
// 输出最终结果
let result = fibonacci(select);
alert(result);

输入测试：

输入：42

输出：267914296

执行耗时：0.260009765625 ms

方法三：通项公式法

$学新通$

(斐波那契数列通项公式)

function fibonacci(n) {
if (n >= 0) {
// 直接使用公式
// js的精度问题使用round方法进行四舍五入取整（会有误差）
let result = Math.round((Math.pow((1 Math.sqrt(5)) / 2, n) - Math.pow((1 - Math.sqrt(5)) / 2, n)) / Math.sqrt(5));
return result;
} else {
// 不合法输入提示
alert("please give me a right number !");
}
}
// 获取用户输入
let select = prompt("what is the Fibonacci number you ask for?");
// 输出最终结果
let result = fibonacci(select);
alert(result);

输入测试：

输入：42

输出：267914296

执行耗时：0.23583984375 ms

总结

递归法耗时多无误差
迭代法耗时少无误差
通项公式法耗时少有误差

使用方法

第一步：在你的桌面新建一个HTML格式的文件

学新通

第二步：使用你的记事本，把下面这个框架复制到新建的文本文档中并保存

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Document</title>
</head>
<body>
<script>
</script>
</body>
</html>

第三步：将文中你想尝试的方法直接复制到下图中标出的部分，保存后直接双击点开文件即可

学新通

创作不易，希望能支持一下！

什么是支持呢？

(ﾉ∇︎〃 )

点个赞，收藏一下，点个关注之类的。

如果你有更好的想法或者发现文章的不足之处，望大家不吝赐教！

这篇好文章是转载于：学新通技术网

javascript用三种不同的方法来求斐波那契数

什么是斐波那契数列？