# Course Design of Data Structure--24 Points

1. Calculating 24 Points
1. Task brief:
Each card in a deck of poker cards represents a number (J, Q, K represent 11, 12, 13, respectively, not used by two commanders).To pick four cards, you get a number of 1-13. Add an operator (specified as plus, minus, multiply, divide) to make it an expression.Each number can only participate in one operation, four number orders can be arbitrarily combined, four operators can be arbitrarily chosen three and can be repeated.The operation obeys a certain limited level and can be controlled by parentheses, resulting in a result of 24. Output an expression for a solution, using parentheses to indicate that the operation takes precedence.If there is no solution, the output-1 indicates no solution.

Requirement:
(1) Input description: Input uses random generation of four integers, each of which has a range of [1, 13].
(2) Output description: Output an expression of a solution, with parentheses indicating that the operation takes precedence, and output-1 if there is no solution.
(3) Test case: Input 231212 Output ((3-2)*12) +12
(4) Optional requirements: Output requires output of all possible solutions for the four integers.

2. Algorithmic description:
The simplest way to think about it is to iterate through all the possibilities, and let the variable flag++ record the number of algorithms if 24 can be calculated. If flag is 0, the output-1 means that the four numbers cannot calculate 24 points.The necessary and advantageous method of weight removal in my code is the check function, which processes the input data a,b,c,d to find out the same number of them. There are five cases: 1. If they are all different, then no adjustment is made; 2. If there are only two identical elements, then put the corresponding identical elements in the position of C and d; 3. There are two sets of numbers that are identical (e.g., a=c,b=d, but a,b is not equal), then put the same together; 4. Three are the same, then send them to b,c,d; 5. All are the same, so no adjustment is made.Depending on the situation, traverse through all the possibilities, successful weight removal, and reduced number of operations (i.e., 2, 3, 12, 12 can assume that the first 12 will only precede the second). 3. Source Code

``````#include <iostream>
using namespace std;
int flag=0;
int Calculate(float x,float y,float z,float w);//All permutations and combinations of a b c d
int check(int *a,int *b,int *c,int *d);

int main()
{
int a,b,c,d;
m_ret: //Mark
cout<<"Please enter 4 data"<<endl;
cout<<" First number:";
cin>>a;
cout<<" Second number:";
cin>>b;
cout<<" Third number:";
cin>>c;
cout<<" Fourth number:";
cin>>d;
cout<<"Output all algorithms are as follows:"<<endl;
if ((a<0)||(a>13)||(b<0)||(b>13)||(c<0)||(c>13)||(d<0)||(d>13))
{
cout<<"The input you entered is incorrect. Re-enter"<<endl;
goto m_ret;
} // Return tag, repeat input
if(check(&a,&b,&c,&d)==0)//There are five cases in which you don't want to be equal, two are equal (two), three are equal, four are equal, and put the equality back
{
Calculate(a,b,c,d); Calculate(a,b,d,c); Calculate(a,c,d,b);
Calculate(a,c,b,d); Calculate(a,d,b,c); Calculate(a,d,c,b);
Calculate(b,a,c,d); Calculate(b,a,d,c); Calculate(b,c,a,d);
Calculate(b,c,d,a); Calculate(b,d,c,a); Calculate(b,d,a,c);
Calculate(c,a,b,d); Calculate(c,a,d,b); Calculate(c,b,d,a);
Calculate(c,b,a,d); Calculate(c,d,a,b); Calculate(c,d,b,a);
Calculate(d,a,b,c); Calculate(d,a,c,b); Calculate(d,b,c,a);
Calculate(d,b,a,c); Calculate(d,c,a,b); Calculate(d,c,b,a);
}
else if(check(&a,&b,&c,&d)==1)  //Only one group is the same, that is, c and d after exchange
{
Calculate(a,b,c,d);
Calculate(a,c,d,b);
Calculate(a,c,b,d); Calculate(a,d,c,b);
Calculate(b,a,c,d); Calculate(b,c,a,d);
Calculate(b,c,d,a);
Calculate(c,a,b,d); Calculate(c,a,d,b); Calculate(c,b,d,a);
Calculate(c,b,a,d); Calculate(c,d,a,b); Calculate(c,d,b,a);
}
else if(check(&a,&b,&c,&d)==2)  //There are two groups of the same, a and B C and d after exchange
{
Calculate(a,b,c,d); Calculate(a,c,d,b); Calculate(a,c,b,d);
Calculate(c,a,b,d); Calculate(c,a,d,b); Calculate(c,d,a,b);
}
else if(check(&a,&b,&c,&d)==3)
{
Calculate(a,b,c,d);Calculate(b,a,c,d);
Calculate(c,b,a,d);Calculate(d,b,c,a);
}
else
Calculate(a,b,c,d);
if(flag==0)
cout<<"-1"<<endl;
else
cout<<"Total"<<flag<<"Algorithm"<<endl;
return 0;
}

int Calculate(float x,float y,float z,float w) //All cases of an expression, where x,y,z,w are relatively fixed, so all cases are sorted by the main function inside
{
if (x+y+z+w==24) {cout<<x<<"+"<<y<<"+"<<z<<"+"<<w<<"=24"<<endl;flag++;}
else if (x+y+z-w==24) {cout<<x<<"+"<<y<<"+"<<z<<"-"<<w<<"=24"<<endl;flag++;}
else if ((x+y)*(z+w)==24) {cout<<"("<<x<<"+"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;flag++;}
else if ((x-y)*(z+w)==24) {cout<<"("<<x<<"-"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;flag++;}
else if ((x-y)*(z-w)==24) {cout<<"("<<x<<"-"<<y<<")*("<<z<<"-"<<w<<")=24"<<endl;flag++;}
else if ((x+y+z)*w==24) {cout<<"("<<x<<"+"<<y<<"+"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x-y-z)*w==24) {cout<<"("<<x<<"-"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x+y-z)*w==24) {cout<<"("<<x<<"+"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x-y+z)*w==24) {cout<<"("<<x<<"-"<<y<<"+"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x*y*z)/w==24) {cout<<"("<<x<<"*"<<y<<"*"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x*y)*(z+w)==24) {cout<<"("<<x<<"*"<<y<<")*("<<z<<"+"<<w<<")=24"<<endl;flag++;}
else if ((x*y)*(z-w)==24) {cout<<"("<<x<<"*"<<y<<")*("<<z<<"-"<<w<<")=24"<<endl;flag++;}
else if ((x*y)*z-w==24) {cout<<"("<<x<<"*"<<y<<")*("<<z<<")-"<<w<<"=24"<<endl;flag++;}
else if ((x*y)*z+w==24) {cout<<"("<<x<<"*"<<y<<")*("<<z<<")+"<<w<<"=24"<<endl;flag++;}
else if (x*y*z*w==24) {cout<<x<<"*"<<y<<"*"<<z<<"*"<<w<<"=24"<<endl;flag++;}
else if ((x+y)+(z/w)==24) {cout<<"("<<x<<"+"<<y<<")+("<<z<<"/"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x+y)*(z/w)==24) {cout<<"("<<x<<"+"<<y<<")*("<<z<<"/"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)+z+w==24) {cout<<"("<<x<<"*"<<y<<")+"<<z<<"+"<<w<<"=24"<<endl;flag++;}
else if ((x*y)+z-w==24) {cout<<"("<<x<<"*"<<y<<")+"<<z<<"-"<<w<<"=24"<<endl;flag++;}
else if ((x*y)-(z/w)==24) {cout<<"("<<x<<"*"<<y<<")-("<<z<<"/"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)+(z/w)==24) {cout<<"("<<x<<"*"<<y<<")-("<<z<<"/"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)-z-w==24) {cout<<"("<<x<<"*"<<y<<")-"<<z<<"-"<<w<<"=24"<<endl;flag++;}
else if ((x*y)+(z*w)==24) {cout<<"("<<x<<"*"<<y<<")+("<<z<<"*"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)-(z*w)==24) {cout<<"("<<x<<"*"<<y<<")-("<<z<<"*"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)/(z*w)==24) {cout<<"("<<x<<"*"<<y<<")/("<<z<<"*"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)/(z-w)==24) {cout<<"("<<x<<"*"<<y<<")/("<<z<<"-"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y)/(z+w)==24) {cout<<"("<<x<<"*"<<y<<")/("<<z<<"+"<<w<<")"<<"=24"<<endl;flag++;}
else if ((x*y+z)/w==24) {cout<<"("<<x<<"*"<<y<<"+"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x*y-z)/w==24) {cout<<"("<<x<<"*"<<y<<"-"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x/y+z)/w==24) {cout<<"("<<x<<"/"<<y<<"+"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x/y-z)/w==24) {cout<<"("<<x<<"/"<<y<<"-"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x+y*z)/w==24) {cout<<"("<<x<<"+"<<y<<"*"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x+y/z)/w==24) {cout<<"("<<x<<"+"<<y<<"/"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x-y*z)/w==24) {cout<<"("<<x<<"-"<<y<<"*"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x-y/z)/w==24) {cout<<"("<<x<<"-"<<y<<"/"<<z<<")/"<<w<<"=24"<<endl;flag++;}
else if ((x-y)*z+w==24) {cout<<"("<<x<<"-"<<y<<")"<<"*"<<z<<"+"<<w<<endl;flag++;}
else if ((x-y)*z-w==24) {cout<<"("<<x<<"-"<<y<<")"<<"*"<<z<<"-"<<w<<endl;flag++;}
else if ((x+y)*z+w==24) {cout<<"("<<x<<"+"<<y<<")"<<"*"<<z<<"+"<<w<<endl;flag++;}
else if ((x+y)*z-w==24) {cout<<"("<<x<<"+"<<y<<")"<<"*"<<z<<"-"<<w<<endl;flag++;}
else if ((x-y)/z-w==24) {cout<<"("<<x<<"-"<<y<<")"<<"/"<<z<<"-"<<w<<endl;flag++;}
else if ((x+y)/z-w==24) {cout<<"("<<x<<"+"<<y<<")"<<"/"<<z<<"-"<<w<<endl;flag++;}
else if ((x-y)/z+w==24) {cout<<"("<<x<<"-"<<y<<")"<<"/"<<z<<"+"<<w<<endl;flag++;}
else if ((x+y)/z+w==24) {cout<<"("<<x<<"+"<<y<<")"<<"/"<<z<<"-"<<w<<endl;flag++;}
else if ((x/y-z)*w==24) {cout<<"("<<x<<"/"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x/y+z)*w==24) {cout<<"("<<x<<"/"<<y<<"+"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x*y-z)*w==24) {cout<<"("<<x<<"*"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;flag++;}
else if ((x*y-z)*w==24) {cout<<"("<<x<<"*"<<y<<"-"<<z<<")*"<<w<<"=24"<<endl;flag++;}
return 0;
}

int check(int *a,int *b,int *c,int *d)//Put the same together, put it back
{
int temp;
if((*a)!=(*b)&&(*a)!=(*c)&&(*a)!=(*d)&&(*b)!=(*c)&&(*b)!=(*d)&&(*c)!=(*d))//Not equal, no adjustment
return 0;
else if((*a)==(*b)&&(*a)==(*c)&&(*a)==(*d))//Equal without adjustment
return 4;
else if((*a)==(*b)&&(*a)==(*c)&&(*a)!=(*d)) //Three of them are equal
{
temp=(*d);
(*d)=(*a);
(*a)=temp;
return 3;
}
else if((*a)==(*b)&&(*a)==(*d)&&(*a)!=(*c)) //Three of them are equal
{
temp=(*c);
(*c)=(*a);
(*a)=temp;
return 3;
}
else if((*a)==(*c)&&(*a)==(*d)&&(*a)!=(*b)) //Three of them are equal
{
temp=(*b);
(*b)=(*a);
(*a)=temp;
return 3;
}
else if((*b)==(*c)&&(*b)==(*d)&&(*b)!=(*a)) //Three of them are equal
return 3;
else if((*a)==(*b)&&(*a)!=(*c)&&(*a)!=(*d)&&(*c)!=(*d)) //Two of them are equal
{
temp=(*c);
(*c)=(*a);
(*a)=temp;
temp=(*d);
(*d)=(*b);
(*b)=temp;
return 1;
}
else if((*a)==(*c)&&(*a)!=(*b)&&(*a)!=(*d)&&(*b)!=(*d))//Two of them are equal
{
temp=(*d);
(*d)=(*a);
(*a)=temp;
return 1;
}
else if((*a)==(*d)&&(*a)!=(*b)&&(*a)!=(*c)&&(*b)!=(*c))//Two of them are equal
{
temp=(*c);
(*c)=(*a);
(*a)=temp;
return 1;
}
else if((*b)==(*c)&&(*b)!=(*a)&&(*b)!=(*d)&&(*a)!=(*d))//Two of them are equal
{
temp=(*d);
(*d)=(*b);
(*b)=temp;
return 1;
}
else if((*b)==(*d)&&(*b)!=(*a)&&(*b)!=(*c)&&(*a)!=(*c))//Two of them are equal
{
temp=(*c);
(*c)=(*b);
(*b)=temp;
return 1;
}
else if((*c)==(*d)&&(*c)!=(*a)&&(*c)!=(*b)&&(*a)!=(*b))//Two of them are equal
return 1;
else if((*a)==(*b)&&(*c)==(*d)&&(*a)!=(*c))//Two of the groups are equal
return 2;
else if((*a)==(*c)&&(*b)==(*d)&&(*a)!=(*b))//Two of the groups are equal
{
temp=(*b);
(*b)=(*c);
(*c)=temp;
return 2;
}
else   //Two of the groups are equal
{
temp=(*b);
(*b)=(*d);
(*d)=temp;
return 2;
}
}//204 lines
``````

4. Running results
1.Test 1:2, 3, 12, 12: 2. Test 2:1, 2, 2, 3 We find that there is no corresponding expression and we can verify that: 3. Test 3:1, 2, 3, 4 4. Enter illegal data And because I added an m_ret: To mark, you can return to re-enter.
5. Summary
Performance analysis:
Time Complexity: Because at worst the number of full permutations of a random sequence (when the four numbers are completely different) is limited, at 4!3!Sort arrangement result, therefore time complexity O_
Spatial Complexity: O_
Problems encountered and solutions:
It is easy to duplicate expressions, so in order to reduce duplicate output to some extent, I used a simple pre-processing of the original data, the specific method ideas as above, do not go into details here.
Experience:
From the result, the program code is correct, but although the expression that looks exactly the same will not appear, it can only achieve this basic weight. For example: 2+3 and 3+2, the code I write still thinks they are different, but in reality, they should be the same, that is, they should be weighted, but this implementation is more difficult, although there are ideas- Sorting and string comparisons can be used, but the code length would be too long, so this is the only way to do it.
I feel that my original processing of data is well written, and I can make different processing methods according to the different characteristics of the data. Once the same original, the number of steps will be reduced and the efficiency will be improved.And I can count the number of methods for calculating 24 points and give them.
Problems and improvements:
Even though I've preprocessed the data, I'm sure it's not possible to have the exact same expression, but because + and

In fact, 2+1 and 1+2 should be considered equivalent, that is, the same expression. However, due to the size problem, I did not expand to deal with it, but I have the following ideas to deal with it: idea 1: use the structure of binary trees, leaf nodes with calculated numbers, then their parent nodes put operators first, and then replace them with calculated values, so whenWhen a parent node with two numbers in common is + or x, we can swap the values of the left and right children to see if the parent node calculates the same value at this time, and if it does, only one of them can be output.Thought 1: The same as above, but there is a requirement for the left and right children's value, that is, for the parent node is + or x, the right child's value is greater than or equal to the left child's value, so it can also achieve weight loss.

Added by fri3ndly on Wed, 24 Jun 2020 03:52:54 +0300