Recursion frog jumping steps problem

Catalog

Caption （ Preface ）

One 、 Ideas

Two 、 Code

3、 ... and 、 expand

summary

---

Preface ：

A frog can jump at a time 1 A step or jump 2 Stepped steps , for example : There is only one way to jump up the first step : Jump directly 1 Level 2 . Jump up two steps , There are two ways to jump : Each jump 1 level , Jump twice ; Or a jump 2 level . Ask to jump to the n How many jumps are there on the steps ?

---

One 、 Ideas ：

Recursion usually transforms a large and complex problem layer by layer into a smaller problem similar to the original problem , The recursion strategy only needs a few programs to describe the repeated calculation needed in the process of solving problems , Greatly reduces the amount of code in the program ;

According to the idea of recursion, we might as well set the number of steps as N

1. When N=1 when , There is a way for frogs to jump up the steps ;

2. When N=2 when , The frog jumped up the steps , You can skip two levels at a time or one level twice , There are two methods

3. When N=3 when , Suppose the number of steps the frog jumps on for the first time is 1, There are two jumping methods for the remaining two steps ; If the number of steps jumped for the first time is 2, There is only one jumping method for the remaining step ; To make a long story short , Namely N=1 The number of hours +N=2 The number of hours .

4. When N=4 when , Suppose the first step the frog jumps on is 1, be left over 3 A stair , That is, the method of jumping three steps ; If you jump two steps for the first time , There are two steps left , That is, the method of jumping two steps  

To sum up, we can deduce the law ： When the number of steps is N when , The frog jumps on the steps ：（N-1） Methods +（N-2） Methods

---

Two 、 Code ：

#include<stdio.h>
int frog(int n)
{
   if(n == 1)
   {
      return 1;
   }
   if(n == 2)
   {
      return 2;
   }
   return frog(n-1) + frog(n-2);
}
int main()
{
   int n;
   scanf("%d",&n);
   int ways = frog(n);
   printf("%d\n",ways);
   return 0;
}

---

3、 ... and 、 expand

If a frog can jump more than one step at a time （ Greater than 2）, Then jump at this time N How many jumping methods are there for steps ; Also follow the above steps to analyze

1. When N=1 when , There is a way for frogs to jump up the steps ;

2. When N=2 when , The frog jumped up the steps , You can skip two levels at a time or one level twice , There are two methods

3. When N=3 when , Suppose the number of steps the frog jumps on for the first time is 1, There are two jumping methods for the remaining two steps ; If the number of steps jumped for the first time is 2, There is only one jumping method for the remaining step ; Or just jump once 3 A stair .

4. When N=4 when , Suppose the first step the frog jumps on is 1, be left over 3 A stair , That is, the method of jumping three steps ; If you jump two steps for the first time , There are two steps left , That is, the method of jumping two steps ; If you jump three times for the first time , There is a step left , That is the way to jump a step .

To sum up, we can deduce the law ： When the number of steps is N when , The frog jumps on the steps ：（N-1） Methods +（N-2） Methods +（N-3） Methods

#include<stdio.h>
int frog(int n)
{
	if (n == 1)
	{
		return 1;
	}
	if (n == 2)
	{
		return 2;
	}
	if (n == 3)
	{
		return 4;
	}
	return frog(n - 1) + frog(n - 2) + frog(n - 3);
}
int main()
{
	int n;
	scanf("%d", &n);
	int ways = frog(n);
	printf("%d\n", ways);
	return 0;
}

---

summary ： Empathy , If a frog can jump at once n A stair , It can also be analyzed according to the above ideas .