Do you have any interesting places to go during the National Day holiday?

Niuniu because of playing badminton ankle sprain, can only look at at home, before also worried about being pulled to a variety of relatives to visit, the fact is that I think too much 😭😭😭

Niuniu also had to turn grief and anger as power, liver at home, today warm a field, to the algorithm, to see if everyone’s skills are unfamiliar!

Origin story

One day, there is a bag of peaches in the forest 🍑. Five monkeys come.

The first monkey divided the pile of peaches into five halves, one too many. The monkey threw away the extra one and took one.

The second monkey divided the remaining peaches into five pieces, and there was one more. He threw the other away and took one away.

The third, fourth and fifth monkeys were also in the same situation. How many peaches were in the bag?

The peach distribution of each monkey


The first reaction to this question should be — it’s a math problem.

So we’re going to solve the math problem mathematically. Niuniu below deduce with everyone.

Let’s say I had x peaches and I had y left.

The first monkey threw one, and took 1/5 of the remaining (x-1) peaches, which equals 1/5(x-1)+1;

The number of peaches left y = 4/5(x-1);

The second monkey came and did the same, so the total number of peaches removed was: 1/5(4/5(x-1)-1)+1;

The number of peaches left is: y = 4/5(4/5(x-1)-1)

.

See a pattern?

For each monkey, the number of peaches left is subtracted by 1 and multiplied by 4/5. There are 5 monkeys, so the number of peaches left is:

Let’s tidy it up and get the formula:

Since x and y are both positive integers, x plus 4 must be a multiple of 5×5×5×5.

And they want the smallest x, so x plus 4 is equal to 5 to the fifth, so x is equal to 3125 minus 4 is equal to 3121. There were at least 3,121 peaches to start with and 1,020 peaches left.

Application method

Let’s look at how to solve this problem in the world of programming.

According to the problem, we only know one number, and that is five monkeys.

So the peaches were divided 5 times, and each time there were 5 more peaches and 1 more peaches, but I don’t know how many peaches each was.

This is the hardest part of this problem, because the number of peaches per serving is not certain, and the number of peaches after each peach is divided is not certain.

But reading the question, we found that each monkey did the same thing, with the number of peaches -1, then took away 1/5 of the peaches, leaving 4/5, and the next monkey would do the same thing again.

This is repeated five times. What do you think?

This is the loop in the program! It was done five times.

So let’s do a loop:

I = 1; While I <= 5: // divide the peach operation...... i++Copy the code

So how do you figure out how to divide a peach? Well, according to the analysis above, you take a number, minus 1, and multiply it by 4/5, and that number has to be a positive integer.

Call it peach. If peach is divisible by 5 * 4, add an if condition: Peach % 5 == 1.

The overall code is as follows:

If I = 1 while I <= 5: # 1 peach % 5 == 1: Peach = peach // 5 * 4 I += 1Copy the code

The only challenge now is how much peach to initialize.

Inner OS: I don’t know what the number is. If I knew, I wouldn’t need to figure it out…

Don’t worry, since you don’t know, let’s follow the program’s logic and try peach one at a time, starting at 1 and finding a number that satisfies the loop condition five times.

So Peach will be a circular process again. This results in the following code:

I = 1 peach = 1 while I <= 5: #-1 peach = 1 while I <= 5: #-1 peach = 1 Peach = peach // 5 * 4 I += 1 Continue I += 1 peach += 1Copy the code

But on closer inspection, the code is flawed.

The loop must satisfy a peach % 5 == 1 and update peach = peach // 5 * 4 as I change from 1 to 5.

When a peach % 5 == 1 peach % 5 == 1 peach % 5 == 1 peach % 5 == 1 peach % 5 == 1 peach % 5 == 1 peach % 5 == 1

So for changing I, either +1 or reset to 1 in a loop, but Peach tries to work its way up from the first number.

So we want to have a number to record the number of peaches we have tried, we define it as count, so the final code is as follows:

Def sum_peach(): I = 1 peach = 1 count = 1 while I <= 5: # 1 if peach % 5 == 1 Peach = peach // 5 * 4 I += 1 else: I = 1 count += 1 peach = count return countCopy the code

So we ended up with count of 3121, so there were at least 3,121 peaches on the beach.

This problem solving idea is actually using the violence of the program to solve, according to the limited conditions of the problem, a number of a number to try to judge, which number can meet the meaning of the question on behalf of the value found.

Peach peach’s analyse

As we mentioned before, most algorithms can be solved by brute force, greedy algorithm and dynamic programming. Many friends spend a lot of time studying the latter two, but brute force is also very important, and some algorithms can only be solved in such a simple and crude way.

The so-called avenue to the simple, as long as we do enough preparation, to really encountered in the interview can only use violence to solve the problem, do not doubt, believe in their own judgment!