首页 > 代码库 > 编程之美2.9 斐波那契数列
编程之美2.9 斐波那契数列
斐波那契数列是我们在学习C语言的时候,在递归那一章的经典实例,当然,还会有汉诺塔的例子。
这个问题时这样定义的:
0 (x <= 0)
f(x) = 1 (x == 1)
f(x - 1) + f(x - 2) (x > 1)
看到这个递推公式后,我们很容易可以写出如下的代码:
函数声明:
typedef long long ll;
ll DutFibonacci_1(int);
函数定义:
/*经典的斐波那契数列的递归解法,而且每个人都知道这种方法效率很低*/ ll DutFibonacci_1(int n) { if (n <= 0) return 0; else if (n == 1) return 1; else return DutFibonacci_1(n - 1) + DutFibonacci_1(n - 2); }
不过,当你输入一个比较大的 x 值后,你会发现,你等了很久,还是没有任何输出,这就是递归效率低的问题。递归是利用栈的思想,一次次的入栈算它的前一个值,然后在一次次的出栈算它的后一个值,最后,得到最终的值(最后一个值)。那么,我们可以知道,其实这里需要保存函数的地址,各个参数的值等等一系列的操作,肯定是浪费了大量的时间和资源,所以,我们需要寻求另外一种方法解决这个问题。
大多数递归的问题都是可以利用循环去解决的,所以,我们可以尝试的写出如下的循环求解代码:
函数声明:
ll DutFibonacci_2(int);
函数定义:
ll DutFibonacci_2(int n) { if (n <= 0) return 0; else if (n == 1) return 1; ll one = 1; ll two = 0; ll result = 0; /*非递归解法也很简单,利用两个中间数,计算“曾经”出现的值就可以了*/ for (int i = 2; i <= n; ++i) { result = one + two; two = one; one = result; } return result; }
编程之美2.9 斐波那契数列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。