Counting 24 points: Principle, the process-oriented C implementation, object-oriented Java implementation
1 Overview
A given 4 integers, each of which can only be used once; use - * / (), construct an expression, making the final result of 24, which is a common 24 points game. There are many procedures in this regard, usually exhausted. This article describes a typical 22-point program algorithm and gives two specific 24 points: one is a process-oriented C implementation, one is an object-oriented Java implementation.
2. Basic principle
Basic principles are exhaustive 4 integers, and then evaluate the expression.
Definition of expressions: expression = (expression | Number) Operator (Expression | Number)
Because the four operators - * / are 2 yuan operators, only 2 yuan operators are considered herein. The 2 yuan operator receives two parameters, outputs the results, and the results of the output are participated in the subsequent calculation.
The algorithm for constructing all possible expressions as described above is as follows:
(1) Putting 4 intenses into the array (2) Take two numbers in the array, and there are P (4, 2) arrangements. For each arrangement, (2.1) to - * / each operator, (2.1.1), according to two numbers and operators of this arrangement, the calculation results (2.1.2) turn list: two two The number is removed from the array, putting the result of the 2.1.1 calculation into the array (2.1.4) to the new array, repeat step 2 (2.1.4) recovery array: add two numbers of this arrangement to the array Remove the results calculated by copies 2.1.1 from the array
It can be seen that this is a recursive process. Step 2 is the recursive function. When only one number is left in the array, this is the final result of the expression, and the recursive ends.
In the program, be sure to pay attention to the recursive field protection and recovery, that is, after recursive calls, the field state should be consistent. In the above algorithm, the recursive site is an index group, 2.1.2 changes the array to perform the next layer recursive call, 2.1.3 restore an array to ensure that the current recursive call is obtained.
The role of parentheses is only to change the priority of the operator, that is, the order of calculation of the operator. Therefore, in the above algorithm, there is no need to consider parentheses. Brackets are only considered when the output is output.
3, the process-oriented C realization
This is the code of the 9CBS algorithm forum front moderator, the program is very concise, exquisite:
#include
#include
#include
Using namespace std;
Const Double precision = 1e-6;
Const int count_of_number = 4;
Const int Number_to_be_cal = 24;
Double Number [count_of_number];
String expness [count_of_number];
Bool Search (int N)
{
IF (n == 1) {
IF (FABS (Number [0] - Number_to_be_cal) COUT << Expression [0] << ENDL; Return True; } else { Return False; } } For (int i = 0; i Double A, B; String EXPA, EXPB; A = Number [i]; B = Number [J]; Number [J] = Number [n - 1]; EXPA = Expression [i]; ExpB = expression [j]; Expression [J] = Expression [N - 1]; Expression [i] = '(' EXPA ' ' EXPB ')'; Number [i] = a b; IF (SEARCH (N - 1)) Return True; Expression [i] = '(' EXPA '-' EXPB ')'; Number [i] = a - b; IF (SEARCH (N - 1)) Return True; Expression [i] = '(' EXPB '-' EXPA ')'; Number [i] = b - a; IF (SEARCH (N - 1)) Return True; Expression [i] = '(' EXPA '*' EXPB ')'; Number [i] = a * b; IF (SEARCH (N - 1)) Return True; IF (b! = 0) { Expression [i] = '(' EXPA '/' EXPB ')'; Number [i] = a / b; IF (SEARCH (N - 1)) Return True; } IF (a! = 0) { Expression [I] = '(' EXPB '/' EXPA ')'; Number [i] = b / A; IF (SEARCH (N - 1)) Return True; } Number [i] = a; Number [J] = B; Expression [I] = EXPA; Expression [J] = EXPB; } } Return False; } void main () { For (int i = 0; i Char buffer [20]; INT X; CIN >> X; Number [i] = x; ITOA (X, Buffer, 10); Expression [I] = Buffer;} IF (Search (count_of_number) { Cout << "Success." << Endl; } else { COUT << "fail." << endl; } } Compile with any C compiler. The algorithm of this program is basically the same as 2, the algorithms described in the basic principles. Where BOOL Search (int N) is a recursive function, Double Number [] is an array. An important part of the program is explained as follows: (1) String Expression [] Store the expression generated by each step, and the last output is used. Expression [] is similar to Number [], which is also the on-site recursive call, and must be changed before the next layer recursive call, and recovered after the next layer recursive call. (2) Number [] array length is only 4. In Search (), each time you take two numbers, use local variables A, B to save these two numbers, and add the calculation results in the array, and adjust the array to arrange the valid number in front of the array. After the next layer is recursive, the entire array is restored by local variables A and B. Treatment with Expression [] is similar to Number []. (3) Because * satisfies the exchange rate - / unsatisfactory, the program generates two numbers from the array, for (int i = 0; I (4) This procedure only finds the first solution. When the first solution is obtained, the result is returned and output through the layer RETURN TRUE, and then the program ends. (5) Solving by Double, definition accuracy, is used to determine if it is 24. Consider (5-1 / 5) * 5 This expression knows the reason. (6) When outputting, brackets are added to each expression. 4, object-oriented Java implementation The algorithm is still 2, the basic principle. The benefits of using objects are clearer, and the function is expanded is more convenient. Of course, efficiency is lower than the structured program. The object is designed as follows: Method Classes class variables contained in the instructions contained Numberdouble valueString toString () This expression clearly express the recursive definition Expression extends NumberNumber leftNumber rightchar operatorString toString () CalculatorNumber [] numbersExpression [] expressionsadd () clear () // operation numberscalculate () Permutor Permutor () Java Program The primary class, implementation algorithm Permutorint i, jboolean next () Arrangement generator, similar to Iterator, generate two elements from a specified array Complete source code, please see http://sliant.vicp.net/programming/expression.zip. This is a simple 24-point calculation program and an expression parsed evaluation program. Please refer to the readme.txt in the method. You can see many benefits of object-oriented design: (1) When outputting an expression, just overwritten Number.toString () and Expression.toString (). In order to output the necessary parentheses, remove unnecessary parentheses, as long as Expression.toString () can be rewritten. (2) Permutor arrangement generator makes the process structure greatly simplified. (3) Good packaging, generate three arranging, in theory, only need to change the internal implementation of Permutor (4) Good reuse, Number, Expression can be reused in other places, such as in the expression parser. Of course, this is just an exemplary code, and there are many packages, simplified places. It is a very convenient thing to make a modification on the framework of the class. Copyright Notice: 9CBS is this BLOG managed service provider. If this paper involves copyright issues, 9CBS does not assume relevant responsibilities, please contact the copyright owner directly with the article Author. Published on March 09, 2004 10:17 AM comment # Reply: 22 points: principle, process-oriented C realization, object-oriented Java implementation 2004-10-13 10:07 PM temple #include #include #include Using namespace std; Const Double precision = 1e-6; Const int count_of_number = 4; Const int Number_to_be_cal = 24; Double Number [count_of_number]; String expness [count_of_number]; Bool Search (int N) { IF (n == 1) { IF (FABS (Number [0] - Number_to_be_cal) COUT << Expression [0] << ENDL; Return True; } else { Return False; } } For (int i = 0; i For (int J = i 1; j Double A, B; String EXPA, EXPB; A = Number [i]; B = Number [J]; Number [J] = Number [n - 1]; EXPA = Expression [i]; ExpB = expression [j]; Expression [J] = Expression [N - 1]; Expression [i] = '(' EXPA ' ' EXPB ')'; Number [i] = a b; IF (SEARCH (N - 1)) Return True; Expression [i] = '(' EXPA '-' EXPB ')'; Number [i] = a - b; IF (SEARCH (N - 1)) Return True; Expression [i] = '(' EXPB '-' EXPA ')'; Number [i] = B - A; IF (SEARCH (N - 1)) Return True; Expression [i] = '(' EXPA '*' EXPB ')'; Number [i] = a * b; IF (SEARCH (N - 1)) Return True; IF (b! = 0) { Expression [i] = '(' EXPA '/' EXPB ')'; Number [i] = a / b; IF (SEARCH (N - 1)) Return True; } IF (a! = 0) { Expression [I] = '(' EXPB '/' EXPA ')'; Number [i] = b / A; IF (SEARCH (N - 1)) Return True; } Number [i] = a; Number [J] = B; Expression [I] = EXPA; Expression [J] = EXPB; } } Return False; } void main () { For (int i = 0; i Char buffer [20]; INT X; CIN >> X; Number [i] = x; ITOA (X, Buffer, 10); Expression [I] = buffer; } IF (Search (count_of_number) { Cout << "Success." << Endl; } else { COUT << "fail." << endl; } } Can't run, # Reply: 22 points: principle, process-oriented C realization, object-oriented Java implementation 2004-11-19 2:35 PM A knife Big Brother is not, you are too complicated, I only used a four-layer nesting loop, and I solved it, and I can output all algorithms that can be composed of 24, but I have written it in Turboc using C. I will translate him into C . The code is also attached.
