17. 计算斐波那契数(非递归方法)
题目:
编写非递归函数计算斐波那契数 Fn 。对于每一个斐波那契数,你的代码应该只计算一次。测试你的代码。
思路:
非递归算法,要从正向进行迭代计算。我们统一一下定义:数列从 1 开始,即F(1) = 1, F(2) = 1。
利用三个变量:fib_front,fib_behind, fib。顾名思义,fib_front代表靠前的一个数,fib_behind代表靠后的一个数, fib代表当前的数。每次循环,将靠后的数值给靠前的那个,再将当前数的值给靠后的那个,这样就完成了一次迭代。
代码:
#include <iostream> using namespace std; long long fib_recursion (int n) { if (1 == n || 2 == n) { return 1; } else { return fib_recursion( n - 1 ) + fib_recursion( n - 2 ); } } long long fib_non_recursion(int n) { long long fib_front = 1, fib_behind = 1; long long fib = 0; if (1 == n || 2 == n) { return 1; } for (int i = 3; i <= n; ++i) { fib = fib_front + fib_behind; fib_front = fib_behind; fib_behind = fib; } return fib; } int main() { cout << "Enter n : "; int n; cin >> n; long long result = fib_recursion(n); cout << "result(recursion) : " << result << endl; result = fib_non_recursion(n); cout << "result(non-recursion) : " << result << endl; return 0; }
代码中有几处需要说明:
第一,上面是递归算法,下面是非递归算法,放在一起方便对比。
第二,关于斐波那契数列,我们采用从 1 开始的定义方法。
相关推荐
steeven 2020-11-10
Tips 2020-10-14
nongfusanquan0 2020-08-18
yedaoxiaodi 2020-07-26
清溪算法君老号 2020-06-27
pengkingli 2020-06-25
yishujixiaoxiao 2020-06-25
清溪算法 2020-06-21
RememberMePlease 2020-06-17
nurvnurv 2020-06-05
SystemArchitect 2020-06-02
码墨 2020-05-29
清溪算法 2020-05-27
choupiaoyi 2020-05-27
清溪算法 2020-05-25
bluewelkin 2020-05-19
dbhllnr 2020-05-15
steeven 2020-05-09
baike 2020-05-09