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

This article introduces you how to use Python to write algorithm problems, the content is very detailed, interested friends can refer to, hope to be helpful to you.

Topic description

If I give you n matchsticks, how many equations like "A+B=C" can you spell out? A, B, and C in the equation are integers spelled out with matchsticks (if the number is non-zero, the highest bit cannot be 00). The spelling of the number 0-90 − 9 with a matchstick is shown in the figure:

Note:

The plus sign and the equal sign each need two matchsticks

If A ≠ B, then A+B=C and B+A=C are considered to be different equations (A _ Magi B ~ C > = 0)

All the matchsticks must be used

Input format

An integer n (n 0: digit = x% 10c + = num [digit] x = x / / 10 return cresult = [0] * 24for n in range (10,25): # 10 matches are all 0 It is obvious that print ("caculate", n) for i in range (0, 10000): # suppose the maximum value of a single number is 10000 for j in range (0, 10000): if count (I) + count (j) + count (result) = n-4: result [n-1] + = 1print (result)

The above code can not run on my computer for half a day, and the maximum value can be changed to 2000. The same code, which works quickly with Java, is enough to show that Python is not suitable for this kind of problem.

Public class Test {public static void main (String [] args) {int [] result = new int [24]; for (int I = 10; I 0) {int digit = x% 10; c + = num [digit]; x = x / 10;} return c;}}

The final result is {0meme0pence0jor0jor0jor0jor0.0jor0.0jr.0jr.0.0.0.0.0.0.0.0.0.0.0.1.2pr. 8pr. 9jr.6.

But although it is exhaustive, there is a problem with the above code. You have to call count repeatedly every time, just save the count in advance. Although it is still slow to use Python, you can get the results within an acceptable time.

# 0-9 how many matches are needed num = [6, 2, 5, 5, 4, 5, 5, 6, 3, 7, 6] # enter a number Calculate the number of matchsticks def count (x): if x = = 0: return 6c = 0 while x > 0: digit = x% 10c + = num [digit] x = x / / 10 return cCOUNT = [0] * 20000for i in range (0,20000): COUNT [I] = count (I) result = [0] * 24for n in range (10,25): print ("caculate", n) for i in range (0) 10000): for j in range (0, 10000): if COUNT [I] + COUNT [j] + COUNT [iSj] = = n-4: result [n-1] + = 1print (result) method 2: optimize the above method

There is no better way to minimize the number of loops, and it would be easier to know the maximum of a single number.

If you want to spell the maximum number with the least number of matches, you have to spell the maximum number first, because 999 must be smaller than 1111, because a number is at least 2 matches, so for an even number of matches, it must be the largest one like 11111. For example, 10 matches, the maximum number that can be spelled is 11111 matches, and the maximum number that can be spelled is 1111111111.

Assuming that the maximum value is more than 10000, then at least 10 pieces are needed, which can spell 11111, and the remaining 10 pieces are divided into 8 pieces. The two cannot be more than 10000, so the maximum value is no more than 10000.

Assuming that the maximum value may be in [9000, 010, 000), you need at least 12 pieces, which can spell 9111, and the remaining 8 cannot add up to this number.

Assuming that the maximum value may be in [8000 # 9000), at least 13 are needed, let alone impossible.

Assuming that the maximum value may be in [7000Magne8000), you need at least 9, that is, 7111, and the remaining 11 are left. If you divide it into 90002, 2 can only be 1, so 9 must be spelled into 7110, which is not enough.

Suppose that the maximum value may be in [6000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,7,000), at least 12, and not even the remaining 8.

Assuming that the maximum value may be located in [5000 Power6000), at least 11 are needed, and the maximum 4-digit number that the remaining 9 can spell is 7xxx or 1xxx, which cannot add up to 5000. The same is true for [2000,5000,000,000,500).

Assuming that the maximum value may be in [1900 June 2000], then at least 12, 1911 are needed, and the rest cannot be added up to 1911.

According to the analysis in turn, we find that the maximum number can not be greater than 1111. According to the results of the program, the maximum value is 712.

After the improvement, you can AC without turning on the meter.

# 0-9 how many matches are needed num = [6, 2, 5, 5, 4, 5, 5, 6, 3, 7, 6] # enter a number Calculate the number of matchsticks def count (x): if x = = 0: return 6c = 0 while x > 0: digit = x% 10c + = num [digit] x = x / / 10 return cCOUNT = [0] * 713for i in range (0,713): COUNT [I] = count (I) result = 0n = int (input ()) for i in range (0712): for j in range (0) Continue if COUNT [I] + COUNT [j] + COUNT [iSj] = = n-4: result + = 1print (result) so much for sharing on how to write algorithms in Python. I hope the above content can be of some help to you and learn more knowledge. If you think the article is good, you can share it for more people to see.

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.