文章目录

前言

一、题目

二、解析

1.题目分析

2.解题思路

三、代码实现

1.递归

2.非递归

总结

前言

本文会带大家从题目剖析一步步找到解题思路，并通过递归和非递归两种方式实现问题的解决。

一、题目

  一只青蛙跳一次只能跳1级台阶或跳2级台阶。
  求:该青蛙跳上第n级台阶总共有多少种跳法？
  例如:青蛙想跳至第二级台阶可以有两种跳法，一种是先跳一级再跳一级，另一种是直接跳两级台阶。 

二、解析

1.题目分析

  拿到这个题目我们可以提取出最关键的点就是青蛙一次只能跳一级或两级台阶，拿到这个条件我们可以简单的通过画图求出青蛙跳前几级有几种跳法。我们不妨设n为“青蛙要跳上第n级台阶”，func（n）为“跳上第n级总共有几种跳法”。

画图:

可以容易得到：

  那么我们该怎么思考才能求出跳第n级的跳法总数呢？

2.解题思路

我们可以这样想：

  青蛙一次只能跳一级或两级阶梯，那么青蛙第一次跳时是不是就只有两种可能，一种是跳到第一级，另一种是跳到第二级；

  假设青蛙要跳上第4级台阶，求跳上第4级有几种跳法（ func(4) ）。那完成第一次跳后的青蛙就只有两种情况，#一种是还剩3级台阶，另一种是还剩2级台阶。

#这时候求的问题就可以巧妙的转换成：求青蛙跳上第3级有多少种跳法+青蛙跳上第2级有多少种跳法( func(3)+func(2) )。我们通过以知的数据可以证得 func(4)=func(3)+func(2)

                                                                                                   5     =     3    +    2

所以我们延伸这个思想，可以得到当n>2时求跳上第n级台阶有多少种跳法有：

func（n）=func（n-1）+func（n-2）

通过得到的结论可以完善表格:

三、代码实现

1.递归

代码如下：

//递归实现
int func(int n)
{
	if (n == 1)
		return 1;
	else if (n == 2)
		return 2;
	else //n大于2的情况才可以进入
		return func(n - 1) + func(n - 2);//满足条件进入递归求n=n-1与n=n-2的情况
}

int main()
{
	int input = 0;

	scanf("%d", &input);
	int ret = func(input);
	printf("func(%d)=%d\n",input, ret);

	return 0; 
}

运行结果正确：

可能会有朋友不理解这个递归是怎么运行起来的呢，我们用一个图来加深对递归过程的理解：

  怎么去理解这个图呢，第一个框就是第一次进入func函数，n=5满足第三个条件                          返回func(4)+func(3)；跟着n=4,n=3分别进入函数返回func(3)+func(2)和func(2)+func(1),以此类推最终都会以func(2)与func(1)进行返回。

即func(5)=  func(4)  +  func(3)

               =  func(3)+func(2)  +  func(2)+func(1) 

               =  func(2)+func(1) +2 +  2     +   1 

               =  2+1+2+2+1

               =  8

2.非递归

代码如下：

//非递归
int func(int n)
{
	int a = 1;
	int b = 2;
	int tmp = 0;

	if (n == 1)
		return a;
	else if (n == 2)
		return b;
	else //n>2时满足条件进入
	{
		while (n - 2)
		{
			tmp = a + b;
			a = b;
			b = tmp;
			n--;
		}
		return tmp;
	}
}

int main()
{
	int x = 0;

	scanf("%d", &x);
	int ret = func(x);
	printf("func(%d)=%d\n", x, ret);

	return 0;
}

运行结果正确：

非递归的思想是什么呢，我们可以知道func（n）=func（n-1）+func（n-2）这个结论，那么也就是func（n-2）+func（n-1）= func（n），所以我们想得到func(n)时只需从初始条件开始推             func(1)+func(2)=func(3),  func(2)+func(3)=func(4),  ...  ,  func(n-2)+func(n-1)=func(n)                       1            2            3     ，    2           3          5      ，...  ，就可以一步步推出最后的结果。 

那么程序要进行几次呢，我们发现当n>2时，循环要进行n-2次。所以每进行一次循环就n--，当    n-2=0的时候就会从while循环中跳出。最后返回的tmp就是求的结果。

总结

要解决这道题最重要的是怎么从题目中提取出循环思想，怎么思考是做题的关键。感谢大家阅读到这，觉得这篇文章有用的话请还多多三连支持o~