Calculate 24
He Zhidan
Problem Description:
There are four integers (0 to 10), and the operator only has addition and subtraction, there are parentheses, each number can be used once, requiring to judge whether there is 24 in the results of these expressions, if there is, the output process, the format is as follows :
4 * 6 * 1 * 1. (Allow parentheses).
note:
1. The intermediate results allow for scores such as (5 - 1/5) * 5;
2, there is no extra brackets.
3, no two negative numbers, such as (1-4) * (1-9), see the repetition (4-1) * (9-1), no 8-8 * (2-4 ).
4. Avoid repetition caused by the exchange law.
5 to avoid repetition caused by combined law.
6. Due to the same repetition is not allowed, there are two 2.
analysis:
# 1, # 2, # 3 represents operators, A, B, C, D represents the number of operations, and there are six possibilities depending on the order of operations for expression a # 1 b # 2 c # 3 d.
1, the order of operation: # 1, # 2, # 3 ((a # 1 b) # 2 c) # 3 d
2, the order of operation: # 1, # 3, # 2 (a # 1 b) # 2 (C # 3 D)
3, the order of operation: # 2, # 3, # 1 a # 1 ((b # 2 c) # 3 d)
4, calculation order: # 2, # 1, # 3 (a # 1 (b # 2 c)) # 3 d
5 Order Sequence: # 3, # 1, # 2 (a # 1 b) # 2 (C # 3 D)
6 Order Order: # 3, # 2, # 1 a # 1 (B # 2 (C # 3 D))
Among them, there are 64 related relationships.
There are 24 kinds of arithmetic relationships.
Consider 6 / (5/4 -1) = 24 Custom Data Type CDATA, including the shaping molecule, and the mother.
Finally, the repetition (output is compared to the string)
1. Due to the same number of operations, it will be directly compared.
2, the question of the exchange rate:
((A # 1 b) # 2 c) # 3 d
If # is or *
Then
((B # 1 a) # 2 c) # 3 d
(C # 2 (a # 1 b)) # 3 d
D # 3 (C # 2 (a # 1 b))
Adjustment makes no decimal plus (multiplication) large number, then compare it, pay attention to the same result, but also the process, the operator before the calculation, such as: (2 4) * 6 instead of 6 * (2 4). All operators also guarantee the uniqueness of the order.
3. The dispensing law does not consider repetition.
4, combined law, such as: A B -C = a - c b; because only three operators, only two operators will appear the combination of the following law and the combination of the three operators. We will first / Become multiplying, all of which are added (multiplying) combined processes. A- (B * C), A- (B / C), A / (B C), A / (BC) is not good Add a marker. Total three operators, and the combination is at least two operators, so B, C will no longer contain operators.
CDATA structure:
Left pointer molecular molecular symbol (addition and subtraction) right pointer
When the number of arithmeters, the symbol is a character #, the pointer is empty.
When the symbol is symbol, the molecules and denominters represent the result, and the left and right pointers points to the calculation, pay attention to the final adjustment makes large on the left (multiplied by flow).
Such as: (5-1) * (2 4), the whole process is:
The pointer of each node is replaced by arrows. In order to avoid repetition caused by the exchange, it adjusts it into (2 * 4) * (5-1). Sorry, the arrow is lost.
The function of CDATA is:
Constructor: The default constructor, the configuration function of the configuration function, the constructor constructor, the constructor of the constructor (denominator defaults to 1).
Destructor.
Overload operators: 1, - * / 2, <,>, == only compare molecules and denominates, do not compare pointers 3, = the parameters on the right can be shaped
Yuefen is simplified to make molecules and denominters do not contain the number of conventions, and it is also negative.
OUTPUT converts data into a string expression, pay attention to excess parentheses.
Adjust1 adjustment makes *, the number of arithmeters on the left is greater than the right, avoiding repetition caused by the exchange law.
Adjust2 Adjusts to avoid two negative numbers.
Adjust3 avoids the repetition of combination.
First turn reduction into equivalents.
Discussion on the situation:
1, the same three operators.
2, the operator and the left.
2, the operator is the same as the right.
4, the two operators of the left branch are the same (recursive processing)
5. The two operators of the right are the same (recursive processing).
For the same operators, from the order of the large to small. Can not be large from small to large. Otherwise, there is an appearance of -1 0 5 * 5;
Add it directly.
void changeSubToadd (); convert subtraction into corresponding addition
Void undoosubtoadd (); will subtract reduction
INT getOperand (cdata ** data); // Returns the number of operands and points the DATA element to each operand
Bool Isopersame (CHAR CH); / / Operator and left and right operators are CH
INT getaddsubcount (); // Return the total number of addresses, good judgment is not required to consider the law
INT getMuldivcount (); // Returns the total number of multi-multiplies, it is a good judgment that it does not need to consider the combination law.
Void changeivTomul (); // Removing
Void undodivtomul (); // Refers to the reduction
Main module function profile and call relationship
CDATA CAL (CData Data1, Int Op, CData Data2)
The first and last parameters are the number of arithmetic calculations, and the OP represents the operators 0 to 3 represent - * /, which calls the addition and subtraction and subtraction of the CDATA class.
Void Add (CData Data)
It adjusts DATA (avoid repetition), then call the Output of the CDATA class to convert the content into a string, and then add this string to the global variable result (not repeated).
Void do (int NData [4], int OP [3])
When the number of arithmeters is fixed, the operator is fixed, and the addition of the ADD will be added in.
Void Cal24Point (Int Input [4])
Voluntary all possible: the correspondence between operands and operators, and then call DO. There is no connection between the three operators, the number of operations can only be used once.
Test Data:
(1), 1, 5, 5, 5 (2) 3, 8, 8, 8 (3), 1, 2, 3, 4 (4), 2, 4, 5, 6
(4), 4, 2, 2, 5 (5) 1, 2, 2, 6 (6), 4, 2, 8, 8 (4), 0, 3, 8, 8
Randomly select several sets of data.
