剑指offer面试题9-青蛙跳台阶及其变种问题

「爱情、让人受尽委屈。」 2022-08-22 15:22 123阅读 0赞

在剑指offer这本书里存在这样几个问题，它们是这样描述的：

【问题描述一】:

一只青蛙一次可以跳上1级台阶，也可以跳上两级台阶。求该青蛙跳上一个n级台阶总共有多少种跳法？

拿到这样一道题我们应该如何考虑呢？当然我们首先要考虑的就是简单的方面了！当只有一级台阶时(n=1)，此时青蛙跳一次就可以完成目标；当只有两级台阶时(n=2)，青蛙可以一次跳一级台阶分两次完成也可以一次跳两级台阶，此时有两种跳法使得青蛙可以达成目标；

接下来就让我们来考虑一般的情况吧！当n>2时，此时我们可以把n级台阶的跳法看成是n的函数:f(n)；如果青蛙第一步跳一级台阶，之后的跳法数目就是之后剩余n-1级台阶的跳法数目，即f(n-1)；另一种可能的情况就是青蛙第一步跳两级台阶，之后的跳法数目就是之后剩余的n-2级台阶的跳法数目；所以n级台阶的不同跳法的总数是f(n)=f(n-1)+f(n-2);

分析到这里大家是不是对这个问题有了实质的理解了呢？实际上它就是我们数学中学过的一个公式叫斐波那契数列，下面是我对这个问题的具体分析也可以利用数学归纳法证明，在这里就不证明了。

![Center][]

【问题分析二】:我们可以用2\*1的小矩形横着或者竖着去覆盖更大的矩形；例如用8个2\*1的矩形去覆盖一个2\*8的大矩形，共有多少种方法？

拿到这样一道题如何去分析呢？ 我们知道第一次放置矩形时有两种方法；竖着放时，右边还剩下n-7个矩形；当横着放在左上角时此时左下角必须也横着放置一个矩形，此时右边还剩下n-6个矩形；如果用公式来表达的话就是f(8)=f(7)+f(6),我们发现它依然是斐波那契数列；

通过分析知道要解决以上两个问题，就要实现斐波那契数列，那仫什仫是斐波那契数列呢？在数学中我们为它做如下定义：

![Center 1][]

当然看到这样的数学公式你马上写出了这样的代码：

#define _CRT_SECURE_NO_WARNINGS
    #include<stdio.h>
    #include<stdlib.h>
    int fib(int n)
    {
    	if(n <= 1)
    		return n;
    	else
    		return fib(n-1)+fib(n-2);
    }
    
    int main()
    {
    	int num=0;
    	int ret=0;
    	printf("请输入你要求第几个斐波那契数:");
    	scanf("%d",&num);
    	ret=fib(num);
    	printf("第%d个斐波那契数是:%d\n",num,ret);
    	system("pause");
    	return 0;
    }

为方便起见以后只给出代码的实现部分，那仫这样的代码有没有问题呢？我们知道在这个代码中使用的是递归的方法，递归就是函数调用自身，我们知道此时是有时间和空间的消耗的；每一次函数调用就需要在内存栈中分配空间和保存参数，返回地址及临时变量，而且往栈里压入数据和弹出数据都需要时间，所以递归的效率反而不如循环；

递归也会有很多重复的工作，降低了程序的性能；

递归也存在栈溢出的情况使得程序计算出错误的数据；当递归的次数太多时就会超出栈的容量导致调用栈溢出

下面就让我们就来看看它的效率有多差：计算第40个斐波那契数，系统会计算多少次？

![Center 2][]

可见应用递归的方法效率太低HR也是不会满意的那仫我们是不是有更加高效的方法呢？我的想法是如果我们将求过的斐波那契数存入数组中，那仫当要计算一个斐波那契数时只需要通过下标的方式找到它前两个数字相加就可以了，下面我们就给出代码的实现部分：

int fib(int n)
    {
    	int i=0;
    	int str[100]={0,1};
    	if(n <= 1)
    		return str[n];
    	else
    	{
    		for(i=2;i<=n;i++)
    		{
    			str[i]=str[i-1]+str[i-2];
    		}
    		return str[i-1];
    	}
    }

当你满心欢喜的以为自己终于完成了任务时，HR当然不会满意啦！他会说“你觉得你的代码有问题吗？”，如果你说没问题，那仫恭喜你此次面试至此结束了 ![吐舌头][tongue.gif]；我们知道在上述代码中我们使用了数组的方式，数组的大小是100就是说我们最多能求出第100个斐波那契数，如果我们想继续求100之后的斐波那契数就需要开辟足够大的数组大小，这种以空间换取效率的方式当然也不可能使HR满意了；那仫是不是可以不用存储所有的斐波那契数只需要把我们要求的前两个斐波那契存储下来就可以了呢！当然可以啦，代码实现如下：

int fib(int n)
    {
    	int num1=0;
    	int num2=1;
    	int num3=0;
    	int i=0;
    	for(i=2;i<=n;i++)
    	{
    		num3=num1+num2;
    		num1=num2;
    		num2=num3;
    	}
    	return num3;
    }

那仫此时的代码会不会另HR满意呢？如果此时HR说不允许创建第三个变量呢？好刁钻的HR啊！希望我将来不要遇到这样的面试官。 ![微笑][smile.gif]代码实现如下：

int fib(int n)
    {
    	int num1=0;
    	int num2=1;
    	int i=0;
    	for(i=1;i<=n;i++)
    	{
    		num1=num1+num2;
    		num2=num1-num2;
    	}
    	return num1;
    }
    
    int main()
    {
    	int num=0;
    	int ret=0;
    	printf("请输入你要求第几个斐波那契数:");
    	scanf("%d",&num);
    	ret=fib(num);
    	printf("第%d个斐波那契数是:%d\n",num,ret);
    	system("pause");
    	return 0;
    }

程序分析到这里斐波那契数列的问题解决了吗？当然没有啦！在这里提供一种解决方法就是利用一个生僻的数学公式:

![Center 3][]

有兴趣的同学可以自己下去研究在这里我们就不给代码了，在剑指offer面试题11里面我们再讨论这个公式；

解决了斐波那契数的问题当然青蛙跳台阶的问题也解决了，下面我们为青蛙跳台阶的问题进行扩展:如果此时这只青蛙比较厉害发生了变异，一次可以跳上一级台阶，也可以跳上两级台阶...它也可以跳上n级台阶，此时青蛙跳上n级台阶总共有多少跳法？

同样的我们可以利用上面的方法先分析简单的情况：当只有一级和两级台阶时跳法和前一只青蛙一样，问我为什仫自己下去分析![吐舌头][tongue.gif]；当有三级台阶时这只变异的青蛙比前一只青蛙多一种情况就是直接跳上去，是4;...

台阶数n          可能出现的跳法情况f(n)
      1                           1
      2                           2
      3                           4
      4                           8
      5                          16
      ...                         ...
      n                         2^(n-1)

通过数学归纳法我们可以很容易的得到规律就是f(n)=2^(n-1),实现方法类似斐波那契数，有兴趣的同学可以下去实现，在这里我就不实现了。

通过上述几个简单的实例分析让我们感受到了编程和生活是密不可分的，那仫如果你是一个热爱生活的人那，你就可能会成为一个热爱编程的人。

[Center]: /images/20220722/cd7e6ec722e94ca19b90f4eec2c0c956.png
[Center 1]: /images/20220722/0909649dc2814279b9d8c59bb61cabf0.png
[Center 2]: /images/20220722/b7999928771f4c70be82294a7faf6786.png
[tongue.gif]: /images/20220722/e8f191b9d5184a4599e4d54e2e69a8c7.png
[smile.gif]: /images/20220722/ea9bfb89daf8417590cf66b4abe9f02f.png
[Center 3]: /images/20220722/8fea0ef6abb749d786d3a82a4e8f8cc8.png