Shulou(Shulou.com)06/01 Report--

Editor to share with you how C language to solve the problem of frog jumping steps, I believe that most people do not know much about it, so share this article for your reference, I hope you will learn a lot after reading this article. Let's learn about it!

1. Description of basic problem title

A frog can jump up one step or two steps at a time. Find out how many ways the frog can jump on an n-step step.

No, just like down there.

Problem-solving ideas

In fact, as soon as I saw this problem, I was confused. I didn't know where to start the analysis, so let's start with the simplest situation.

If n = 1, there is one step, and obviously there is only one way to jump.

Jump one step at a time

If n = 2, there are two steps and there are two ways to jump.

Jump one step, jump one more step.

Skip step 2

Suppose n = 3, there are three jumps.

Jump 1 step, jump 1 step, jump 1 step again

Jump one step, then two steps.

Jump two steps, then one step.

(note: I found this process diagram from the Internet, it is really rare to draw.)

Through the above analysis, we can think about the problem like this.

For the last step at the top of the stairs, jump either step 1 or step 2

Suppose f (n) is the total jump number of n steps.

So if you choose to jump one step for the first time, the number of jumps of the remaining nmur1 steps will be f (n − 1).

If you skip two steps for the first time, the remaining step jump of nmuri 2 is f (n − 2).

Now frogs can only jump one or two levels at a time, so we can derive the following formula:

Why, isn't this our Fibonacci number?

It's just a little different that the Fibonacci series is usually 1, 1, 1, 2, 3, 5, 5, 13. It started.

And we are using 1, 2, 3, 5, 8, 13. At the beginning, the first one is missing.

Code implementation

The above process is a bit similar to Fibonacci, but not exactly, so let's take a look at the main code first.

# include int jump (int n) {if (n)

< 3) { //假设n的范围是[0, 3] return n; } else { //n>

3 when return jump (n-1) + jump (n-2);}} int main () {int num = 0; printf ("Please enter a number of steps: >"); scanf ("% d", & num); int ret = jump (num); printf ("Little Frogs have% d jumps\ n", ret); return 0;}

Running result

But let's look at the process of calculation.

In order to calculate f (6), it is necessary to calculate subproblems f (5) and f (4).

Then to calculate f (5), we have to calculate the subproblems f (4) and f (3), and so on.

The recursive tree is not terminated until f (2) and f (1).

Therefore, the time complexity of the frog jump step and recursive solution is equal to O (1) * O (2) = O (2).

If you look closely at this recursive tree, you will find that there is a lot of double counting.

For example, f (4) has been calculated twice and f (3) has been repeated three times. So the reason for the inefficiency of this recursive algorithm is that there are a lot of repeated calculations!

So we can optimize the code.

Recursive upgrade

On the basis of the recursive method, a new array of length n is built, which is used to store the digital values from f (0) to f (n) during recursion, and when a number is encountered repeatedly, it is taken directly from the array, which avoids repeated recursive calculation.

So we set up an array to hold the jump (n) that computes a certain n for the first time.

Every time you want to calculate a jump (n), check to see if there is a value in the subscript n in the array. If so, you can get the result value directly from the array without calling jump (n). Otherwise, calculate jump (n).

Code implementation

# include long int f [1000] = {0}; int jump (int n) {/ / when there is only one step, there is only one way up the step. / / when there are two steps, there are two ways to climb the steps, one at a time, and the other two steps at a time. / / now there are n steps, if n > 2, there should be (jump one step first) + (jump two steps first) / / if you jump one step first, then there is a jump (nMel 1) way. If you jump 2 steps first, then there is a jump (nMel 2) mode. / / so you can know that there are jump (nmur1) + jump (nMur2) ways. If (n = 2) {f [1] = 1; return f [1];} if (n = 0) {f [0] = 1; return f [0];} if (n = 2) {f [2] = 2; return f [2] } else {if (f [n-1]! = 0) {if (f [n-2]! = 0) {return (f [n-1] + f [n-2]);} else {f [n-2] = jump (NMu2) Return (f [n-1] + f [n-2]);}} else {if (f [n-2]! = 0) {f [n-1] = jump (n Must1); return (f [n-1] + f [n-2]) } else {f [n-1] = jump (n Mau1); f [n-2] = jump (n Mel 2); return (f [n-1] + f [n-2]);} int main () {int num = 0 Printf ("Please enter a number of steps: >"); scanf ("% d", & num); int ret = jump (num); printf ("Little Frogs have% d jumps\ n", ret); return 0;}

Running result

Dynamic programming solution

I soon found that I didn't have to remember all the records.

Suppose I have three stairs, I only need to know the number of methods to jump two steps and one step, and I can calculate the method number to jump three steps.

Therefore, it is necessary to retain only the number of methods of n − order 1 and n − 2 order each time.

Code implementation

# when include int jump (int n) {/ / n is 0,1,2, return n directly to if (n)

< 3) { return n; } //第一个数为1 int one = 1; //第二个数为2 int two = 2; //用于存放前两个数之和 int sum = 0; while (n >

2) {sum = one + two; one = two; two = sum; n Murray;} return sum;} int main () {int num = 0; printf ("Please enter a number of steps: >"); scanf ("% d", & num); int ret = jump (num); printf ("Little Frogs have% d jumps\ n", ret); return 0;}

Running result

two。 Problem escalation topic description

A frog can jump one step at a time, or two steps at a time. You can also jump n steps to find out how many jumps it takes for the frog to jump up an n step.

Problem-solving ideas

If a frog wants to jump to the n steps, it can go from the first step to the second level. That is to say, you can jump from any level to n

When the step is 1, f (1) = 1

When the step is 2, f (2) = 1 / 2 / 2

When the step is 3, f (3) = f (1) + f (2) + 1x 4

When the step is 4, f (4) = f (1) + f (2) + f (3) + 1x 8

When the step is 5, f (5) = f (1) + f (2) + f (3) + f (4) + 1x 16

So we can easily think of the recursive formula: F (n) = f (n − 1) + f (n − 2) +. + f (2) + f (1) + f (0)

The last f (0) can be removed, because level 0 equals no jump, so f (0) = 0.

Then we remove f (0) and convert it: F (n − 1) = f (n − 2) + f (n − 3) +. + f (2) + f (1)

Derivation process

We list two equations:

① f (n) = f (n − 1) + f (n − 2) + f (n − 3) + … + f (2) + f (1)

② f (n − 1) = f (n − 2) + f (n − 3) + … + f (2) + f (1)

From ①-②, f (n) = 2f (n − 1)

Code implementation

Recursive method

Code example

Int jump (int n) {if (n = 1) {return 1;} else {return 2 * jump (n-1);}} int main () {int num = 0; printf ("Please enter a number of steps: >"); scanf ("% d", & num); int ret = jump (num); printf ("Little Frog has% d jumps\ n", ret) Return 0;}

Running result

Non-recursive method

Of course, it can also be implemented in a non-recursive way.

So how to think about non-recursion?

It can be understood as follows:

Then use the function pow (2Jing n-1), which requires a header file.

But we can do it here without using library functions, and we can introduce you to a magical operation.

Code example

Int jump (int n) {if (n = = 1) {return 1;} else {return 1

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.