Getting Started with Interesting Algorithms in Python Develop Paper

please call me 2022-11-08 03:33:31 阅读数:368


Problem description

Ancient Chinese mathematician Zhang Qiujian proposed a famous "hundred-money-hundred-chicken problem" in his "Suanjing": a rooster is worth five coins, a hen is worth three coins, and three chicks are worth three coins.It's worth a penny, and now I want to buy a hundred chickens with a hundred dollars. How many roosters, hens, and chicks are there?


This is also a classic problem. In mathematics, it is just a system of multivariate linear equations.If we use cock to represent the number of roosters, hen to represent hens, and chicken to represent chickens, the equations can be listed as follows:

\left\{\begin{matrix} cock + hen + chicken=100\\ 5*cock+3*hen+\frac{chicken}{3}=100 \end{matrix}\right.

If you use computer thinking, because the amount of data is small (less than 100), you can use the exhaustive method to use three levels of nested loops to represent the number of roosters, hens, and chicks from the outside to the inside, and then judge the three in turn.Whether the value of either satisfies the above two equations at the same time.

Because 100 dollars can buy at most 100\div 5=20 a rooster, 100\div 3=33hen, 100\ast 3=300a chicken, so the upper limits of these three variables are 20, 33,300.But at the same time, you can't use all the money to buy roosters, hens, and chickens - because the number is wrong, the values ​​are up to 19, 32, and 297 respectively (the number of chickens must be divisible by 3), so you can write the code as follows:

for cock in range(20):for hen in range(33):for chicken in range(298):if cock+hen+chicken=100 and 5*cock+3*hen+chicken/3==100:print(f"Buy {cock} rooster, {hen} hen, {chicken} chick"

Of course, this is just an exhaustive method under the most basic computer thinking. If we substitute a little mathematical knowledge, we will find that any one of cock, hen, chicken can be obtained from the other two, such as

img alt="chicken = 100-cock-hen" class=mathcode src="//">, so there is no need for three layers of loops at all, as long asKnowing cock and hen, the number of chickens can be obtained according to Equation 1.In addition, since the upper limit of chicken is the largest (297), eliminating the loop of chicken will greatly reduce the number of loops and improve efficiency. Therefore, the code can be modified as follows:

for cock in range(20):for hen in range(33):chicken = 100-cock-henif 5*cock+3*hen+chicken/3==100:print(f"Buy {cock} rooster, {hen} hen, {chicken} chick"

The answer is the same, indicating that the program achieves the same effect, but the efficiency is greatly improved.

It's not over yet.

Through mathematical thinking, we can further find that the variable chicken can be eliminated by multiplying both sides of Equation 2 by 3 and then subtracting Equation 1.

\left\{\begin{matrix} cock + hen + chicken=100\\ 15*cock+9*hen+chicken=300 \end{matrix}\right.

Get a new equation: 14*cock+8*hen=200

Divide both sides by 2 to get: 7*cock+4*hen=100

The number of hens can then be obtained from the number of roosters: hen=25-\frac{7}{4}*cock, and the second layer of loop can also be omitted.

At the same time, looking at this hen equation, the right side is the number of roosters divided by 4, and common sense tells us that the number of hens must be

  1. is an integer
  2. greater than 0

Therefore, the number of cocks must be an integer multiple of 4, and \frac{7}{4}*cock\leqslant 25.The number of cock itself must also be an integer, so the value range of cock is 0\leqslant cock\leqslant 14

Therefore, we can write code to only exhaustively enumerate the number of cocks in this range, the number is greatly reduced, 0, 4, 8, 12, and the computational efficiency is greatly improved.The only thing to note is that because of the introduction of division (7/4), the result obtained automatically becomes floating-point data. Even if it can be divided evenly, the result is displayed as x.0.And we want to output an integer, so here we can use int() to convert the calculation result to an integer type, or use the integer division operator (//) directly.

for cock in range(0,14,4):hen = 25-int(cock*7/4):chicken = 100-cock-henif 5*cock+3*hen+chicken/3==100:print(f"Buy {cock} rooster, {hen} hen, {chicken} chick"


Buy 0 roosters, 25 hens, 75 chicksBuy 4 roosters, 18 hens, 78 chicksCan buy 8 roosters, 11 hens, 81 chicksBuy 12 roosters, 4 hens, 84 chicks

Actually, when we use mathematical knowledge to manually complete the above calculations, the obtained solutions (the number of roosters 0, 4, 8, 12) must be reasonable, and no further verification is required. It can be seen that the code is used here.Instead, it seems superfluous and superfluous.This is the difference between computer thinking and mathematical thinking.Computer thinking seems simple, but it is better than the speed of operation, and mathematical thinking can always find solutions to problems faster and more subtly, sometimes without even using computer thinking.What we need to do is to combine the two when faced with different problems, learn from each other's strengths and complement each other's weaknesses, and strive to solve the problem with the highest efficiency.

版权声明:本文为[please call me]所创,转载请带上原文链接,感谢。