计算斐波那契数的算法方法
5.00/5 (3投票s)
一些用于计算斐波那契数的算法建议，涉及迭代、递归和函数式编程范例
解释
又一个斐波那契数列算法？
是的，这是我正在撰写的一系列数学文章中的第二篇，斐波那契数列不可或缺。
但是，我将采用不同的方法来计算它：
- 如何计算整个数列；
- 如何通过其位置获取特定元素；
- 如何实现迭代、递归和函数式编程范例。
引言
请注意下面的数值序列
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89,144, 233, ...
请注意，除了前两个项之外，所有其他项都可以使用前两个项的总和来计算，根据以下公式，其中 M 是一维数组
公式 #1
M(1) = 1;
M(2) = 1;
M(n) = M(n-1) + M(n-2)，对于 n > 2。
可以用递归方式描述这个公式
公式 #2
F(1) = 1;
F(2) = 1;
F(n) = F(n-1) + F(n-2)，对于 n > 2。
还有比奈公式，允许通过它在序列中的位置来计算元素
公式 #3
比奈公式，对于 n >= 0。
但最终，为什么这些数字如此重要？ 显然，它没有什么实际用途。
下面，让我们回答这个问题...
一点历史
莱昂纳多·斐波那契（Leonardo of Pisa），也被称为斐波那契（Bonaccio之子），生活在十二世纪的意大利。
作为一位伟大商人的儿子，他一生大部分时间都在旅行和与阿拉伯人一起学习数学，这导致出版了一些关于代数和算术的书籍，其中我们特别感兴趣的是题为“Liber Abbaci”的作品，其中包含著名的兔子问题
"如果每个月每对兔子都会产下一对新的兔子，而新生兔子从第二个月开始就可以繁殖，那么一年内将会产生多少对兔子？"
莱昂纳多根据下表进行了计算
继续推论，表明我们在 12 个月后将有 144 对兔子。
后来，其他数学家研究了这个序列，发现它存在于其他自然现象中。 其中，我们重点介绍以下使用它的科学领域：
- 光线的反射；
- 在某些植物和动物的研究中；
- 在几何学中，计算黄金分割
公式 公式 #3 中描述的比奈公式最初由莱昂哈德·欧拉于 1765 年发表，但一直被遗忘，直到 1843 年被法国数学家雅克·比奈重新发现。
作为对斐波那契一生的最终观察，我们可以说，他是欧洲数学家中最公开代数的人，极大地促进了代数的普及……
背景
为了测试这里提出的算法，我建议使用以下工具
C / C++ 语言
Pascal 语言
Haskell 语言
使用代码
毫无疑问，处理斐波那契数的最简单和最快的方法是通过比奈公式，特别是当我们只需要一个元素时。
要获得整个序列，最常用的方法是迭代法，因为它只执行求和运算。
现在让我们考虑一下C、Pascal 和 Haskell 中迭代、递归和函数式方法的算法实现...
用于计算整个序列的算法
迭代方法（公式 #1）
// Purpose: Computing the fibonacci numbers in a Iterative way
// Language: C
// Author: Jose Cintra (jose.cintra@html-apps.info)
main() {
unsigned long int n, current = 1, last = 0, penult = 1, count;
printf("The Fibonacci Numbers\n");
printf("\nEnter the number of elements: ");
scanf("%d",&n);
for (count = 1; count <= n; count++) {
current = last + penult;
penult = last;
last = current;
printf("%d ",current);
}
}
关注点
请注意，三个主要变量中的值已初始化。 因此，可以计算所有元素，而无需速度较慢的条件结构。
通过其位置获取特定元素的算法
递归方法（公式 #2）
{
Purpose: Get a Fibonacci number in a recursive way
Linguagem: Pascal
Author: Jose Cintra (jose.cintra@html-apps.info)
}
var
index : integer;
function Fibo(index : integer) : integer;
begin
if index < 3 then
Fibo := 1
else
Fibo := Fibo(index - 1) + Fibo(index - 2);
end;
begin
writeln('The Fibonacci Numbers');
write('Enter the element''s position: ');
readln(index);
writeln('The element in this position is: ',Fibo(index));
end.
函数式方法（公式 #1）
Purpose: Get a Fibonacci number in a functional way
Linguagem: Haskell
Author: Jose Cintra (jose.cintra@html-apps.info)
fibo :: Int -> Int
fibolist :: [Int]
fibolist = 0 : 1 : zipWith (+) fibolist (tail fibolist)
fibo n = fibolist!!n
比奈公式（公式 #3）
// Purpose: Get a Fibonacci number through the Binet's Formula
// Linguagem: C++
// Author: Jose Cintra (jose.cintra@html-apps.info)
#include <iostream>
#include <stdlib.h>
#include <math.h>
using namespace std;
int main() {
int i,f;
cout << "The Fibonacci Numbers\n";
cout << "Enter the element's position: ";
cin >> i;
f = round((pow((1+sqrt(5))/2,i)-pow((1-sqrt(5))/2,i))/ sqrt(5));
cout << "The element in this position is: " << f;
}
结论
就是这样了！
与往常一样，当我们使用传统语言实现算法时，需要考虑的一点是，斐波那契数的值往往会快速增长，导致结果溢出。 解决方案是采用支持任意精度数的库或语言。 函数式语言通常没有这种缺陷。
希望这有帮助。 欢迎提出问题和评论。
再见..