This is the 13th day of my participation in the Gwen Challenge in November. Check out the details: The last Gwen Challenge in 2021″

Recently, I want to review C language, so I will update an article about C language in nuggets every day! Freshmen who are just learning C, and those who want to review C /C++, don’t miss it! Solid foundation, slow down is fast!

Requirements:

A frog can jump up one step or two at a time. Find the total number of jumps that the frog can take up a n step.

-> can be considered Fibonacci sequence

Train of thought

Case 1: If there is only one step: obviously there is only one way to jump Case 2: If there are two steps, then there are two ways to jump. One is to jump in two. 3. If the step progression is greater than 2, set it to N. In this case, we regard the jump of n steps as a function of time n, denoted by f(n). There are two different choices for the first jump: First, the number of hops at the first step is equal to the number of hops at the remaining N-1 steps, namely f(n-1); second, the number of hops at the first step is equal to the number of hops at the remaining N-2 steps, namely F (n-2). Therefore, the total number of different hops at the n steps is: F (n) = f(n-1) + f(n-2), which is Fibonacci numbers.

Mathematical function expression:

According to the above function, we can write the code easily!

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

Copy the code

Yanshen 1: You can jump three steps at a time

1. When N=1, there is one way; 2. When N=2, there are two ways. 3. When N=3, the frog can choose the first step to jump 1 step, 2 steps or 3 steps, there are four methods: (1, 1, 1), (1, >2), (2, 1), (3); 4. When N=4, the frog chooses the method of N= 3 when the first step is 1 layer and the remaining three steps are 1 layer; When the frog jumps 2 floors in the first step, the method of n=2 is > 2 steps left. When the frog jumps 3 floors in the first step, the remaining step is the method of n=1. So all the ways when n=4 are: all the ways when n=3 + all the ways when n=2 + all the ways when n=1; In this way, when >N= N, the method of N steps is: n-1 layer method + n-2 layer method + N-3 layer method;

#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; }Copy the code

Extension 2: you can jump k steps at a time

Let’s go further down. What if a frog can jump k steps at a time?

Obviously, after the above discussion, this problem has become less complicated, we just need to calculate how many ways the frog jumps 1 step > until the frog jumps K steps, using recursion, it will be easy to get the result.

int frog(int n, int k) { if(n == 1) { return 1; } if(n == 2) { return 2; }... . if(n == k) { return ? / / jump k steps method} return frog frog (n - 1) + (n - 2) +... +frog(n-k); }Copy the code

That’s all for today. Thank you for seeing us! Hope to help you! You are welcome to click on this topic and subscribe! At the same time, welcome the bigwigs to criticize and correct!