【剑指offer】——由斐波拉契数列引发的递归循环问题

01斐波拉契数列

题目描述

思路：斐波拉切的公式为：
F(0) = 0;
F(1) = 1;
F(n) = F(n-1)+F(n-2);(n>=2)

方法一：用递归解决。但是用递归的话系统会报错说调用的层次太多，因为递归的时间复杂度是O(2^n)是指数级别的，效率太低，一般不使用

int Fibonacci(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else
		return Fibonacci(n - 1) + Fibonacci(n - 2);
}

由于递归函数的缺陷，一般我们采用迭代的方式实现：

int Fibonacci(int n)
{
	if (n == 0)
		return 0;
	else if (n == 1)
		return 1;
	else
	{
		int a = 0, b = 1;
		int m = 0;
		for (int j = 2; j <= n; j++)
		{
			m = a + b;
			a = b;
			b = m;
		}
		return m;
	}
}
int main()
{
	cout << Fibonacci(30) << endl;
}

02跳台阶问题

题目描述

思路：
a.当只有一个台阶的时候，就只有一种跳法f(1) = 1；当只有两个台阶的时候，分为一次跳两阶和两阶跳一次的两种跳法f(2) = 2。
b、假设第一次跳的一阶，那么剩下的n-1个台阶的跳法为f(n-1)
c、假设第一次跳的是两阶，那么生下来的n-2个台阶的跳法是f(n-2)
d、由b,c假设可以得出跳台阶的算法f(n) = f(n-1)+f(n-2);

代码实现：

int jumpFloor(int number) {
	if (number == 1)
		return 1;
	else if (number == 2)
		return 2;
	else
		return jumpFloor(number - 1) + jumpFloor(number - 2);
}

03变态跳台阶

题目描述

思路：
关于这道题，我的想法是，最后一阶肯定是要跳的，但是n-1阶梯里面，跳与不跳都有两种结果，所以总结出的算法公式为
f(n) = 2f(n-1);
代码实现

int jumpFloorII(int number) {
        if(number < 0)
            return -1;
        else if(number == 1)
            return 1;
        else
            return 2*jumpFloorII(number-1);

    }
}

当然我的见解还是很片面的，来看一看用数学分析法分析的吧~

04矩形覆盖

题目描述：


**思路：**采用数学归纳法，如下图，本质上都是对n-1种方法的扩展。所以得出公式：f(n) = f(n-1) + f(n-2);

代码实现：

int rectCover(int number) {
        if( number <= 0)
            return 0;
        else if(number == 1 || number == 2)
            return number;
        else 
            return rectCover(number-1)+rectCover(number-2);
    }

05兔子繁殖问题

问题描述：

有一对兔子，从出生后第3个月起每个月都生一对兔子，小兔子长到第三个月后每个月又生一对兔子，假如兔子都不死，问每个月的兔子总数为多少？

思路：

分析可以得到：
f(1) = 1
f(2) = 1
f(n) = f(n - 1) + f(n - 2)

代码实现：

int fun(int month) {
	if (month <= 0)
		return 0;
	else if (month == 1 || month == 2)
		return 1;
	else
		return fun(month - 1) + fun(month - 2);
}