C language implements the classical 24 point algorithm

The example of this paper shares the specific implementation code of C language classic 24-point algorithm for your reference. The specific content is as follows

1, an overview of the

Given four integers, each of which can be used only once; Use + - * / () to construct an expression that gives a final result of 24. This is a common game of counting 24 points. There are many programs in this area, usually exhaustive solution. This paper introduces a typical program algorithm for calculating 24 points, and gives two specific programs for calculating 24 points: one is process-oriented C implementation, and the other is object-oriented java implementation.

2. Rationale

The basic principle is to enumerate all possible expressions of four integers and then evaluate the expression.

Definition of expression: expression = (expression|number) operator (expression|number)

Because the four operators + - * / that can be used are all 2-element operators, only 2-element operators are considered in this article. The 2-element operator receives two parameters, outputs the calculated result, and the output results participate in subsequent calculations.

As described above, the algorithm for constructing all possible expressions is as follows:

(1) Put 4 integers into the array

(2) take two number permutations in the array. There are a total of P(4,2) permutations. For each permutation,

(2.1) For each operator + - * /,

(2.1.1) Calculate the result according to the two Numbers and operators arranged in this order

(2.1.2) Change the table array: remove the two Numbers of this arrangement from the array, and put the result calculated in 2.1.1 into the array

(2.1.3) Repeat step 2 for the new array

(2.1.4) Restore the array: Add the two Numbers of this arrangement to the array, and remove the result calculated by 2.1.1 from the array

So this is a recursion. Step 2 is the recursive function. When there is only one number left in the array, this is the final result of the expression, and the recursion ends.

In the program, 1 must pay attention to the recursive site protection and recovery, that is, before and after the recursive call, the site state should remain 1. In the above algorithm, the recursive scene is the exponential group. 2.1.2 changes the array to make the next recursive call, and 2.1.3 restores the array to ensure that the current recursive call gets the next correct arrangement.

The parentheses () only change the precedence of the operators, which is the order in which they are evaluated. So in the above algorithm, the parentheses are not considered. Parentheses only need to be taken into account in the output.

3. Implementation of PROCESS-oriented C

This is the code of Starfish, the former moderator of csdn algorithm forum. The program is very simple and 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　expression[COUNT_OF_NUMBER];　
bool　Search(int　n)　
{　
　　　 if　(n　==　1)　{　
　　　　　　　 if　(　fabs(number[0]　-　NUMBER_TO_BE_CAL)　<　PRECISION　)　{　
　　　　　　　　　　　 cout　<<　expression[0]　<<　endl;　
　　　　　　　　　　　 return　true;　
　　　　　　　 }　else　{　
　　　　　　　　　　　 return　false;　
　　　　　　　 }　
　　　 }　
　　　 for　(int　i　=　0;　i　<　n;　i++)　{　
　　　　　　　 for　(int　j　=　i　+　1;　j　<　n;　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　<　COUNT_OF_NUMBER;　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;　
　　　 }　　　　　　　　　
}

Use any 1 c++ compiler to compile.

The algorithm of this program is basically the same as that described in 2. Where bool Search(int n) is a recursive function and double number[] is an array. The important parts of the program are explained as follows:

(1) string expression[] stores the expressions generated in each step and is used in the final output. expression[], like number[], is the site of a recursive call and must be changed before the next recursive call and restored after the next recursive call.

(2) The number[] array is only 4. In search(), each time two Numbers are fetched, the local variable a is used, b holds the two Numbers, adds the result of the operation to the array, and adjusts the array so that the valid Numbers are arranged in front of the array. After the recursive call at the next level, the entire array is restored using the local variables a, b. expression[] is treated similarly to number[].

(3) Since + * satisfies the exchange rate but - / does not, the program generates two permutations of Numbers from an array,

for (int i = 0; i < n; i++) {

for (int j = i + 1) j < n; j++) {

Its inner loop j is from i+1 - > n, not from 0- > n, because for the exchange rate, the order of the two Numbers doesn't matter. Of course, special treatment is done to - / within the loop, and four cases of ES106en-ES108en-ES109en a/b b/a are calculated.

(4) This procedure only finds the first solution. When the first solution is found, the layer by layer return true returns and outputs the result, and the program ends.

(5) double was used to solve the problem and the precision was defined to determine whether it was 24. So if you look at the expression 5 minus 1/5 times 5, you'll see why you did that.

(6) When output, parentheses are added for each expression.