C语言实例之9斐波那契数列实现

news/2024/11/27 15:42:11/

1. 斐波那契数列简介

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家莱昂纳多・斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为 “兔子数列”。
它的特点是从第三项开始，每一项都等于前两项之和，数列的前两项通常定义为 0 和 1（也有从 1 和 1 开始的定义方式，这里以 0 和 1 为例），即：
在这里插入图片描述

该数列的前几项依次为：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144……
斐波那契数列在自然界、计算机科学、数学等诸多领域都有广泛的应用，比如某生长模式、某算法优化等。
以下是不同方式输出斐波那契数列前20项的值

2. 实例代码之递归实现

需要注意的是，递归实现方式在计算较大项数时效率会很低，因为存在大量重复计算。

#include <iostream>// 递归函数计算斐波那契数列
int fibonacciRecursive(int n) {if (n == 0) {return 0;} else if (n == 1) {return 1;} else {return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2);}
}int main() {std::cout << "斐波那契数列（递归实现）前20项的值为：" << std::endl;for (int i = 0; i < 20; ++i) {int result = fibonacciRecursive(i);std::cout << result << " ";}std::cout << std::endl;return 0;
}

3. 实例代码之for循环实现

该实现方式相对递归实现效率更高，尤其在计算较大项数时优势明显。

#include <iostream>// 迭代函数计算斐波那契数列
int fibonacciIterative(int n) {if (n == 0) {return 0;} else if (n == 1) {return 1;}int a = 0, b = 1, c;for (int i = 2; i <= n; ++i) {c = a + b;a = b;b = c;}return b;
}int main() {std::cout << "斐波那契数列（迭代实现）前20项的值为：" << std::endl;for (int i = 0; i < 20; ++i) {int result = fibonacciIterative(i);std::cout << result << " ";}std::cout << std::endl;return 0;
}

4. 实例代码之数组实现

这种实现方式在需要多次访问数列不同项时可能会更方便，因为已经计算过的项都存储在数组中了。

#include <iostream>// 使用数组计算斐波那契数列
int fibonacciArray(int n) {if (n == 0) {return 0;} else if (n == 1) {return 1;}int fibArray[n + 1];fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i) {fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray[n];
}int main() {std::cout << "斐波那契数列（数组存储实现）前20项的值为：" << std::endl;for (int i = 0; i < 20; ++i) {int result = fibonacciArray(i);std::cout << result << " ";}std::cout << std::endl;return 0;
}