首页 > 代码库 > 编程之美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 斐波那契数列