数据结构课程设计（一）---24点_数据结构24点

一、计算24点
1、任务简述：
一副扑克牌的每张牌表示一个数（J、Q、K分别表示11、12、13，两个司令不用）。任取4张牌，即得到1-13的数，请添加运算符（规定为加、减、乘、除四种）使之成为运算式。每个数只能参与一次运算，4个数顺序可以任意组合，4个运算符任意取3个且可以重复取。运算遵从一定有限级别，可加括号控制，最终使运算结果为24.请输出一种解决方案的表达式，用括号表示运算优先。如果没有解决方案，则输出-1表示无解。

要求：
（1）输入说明：输入采用随机生成4个整数，每个整数取值范围是[1, 13].
（2）输出说明：输出一种解决方案的表达式，用括号表示运算优先，如果没有解决方案，则输出-1。
（3）测试用例： 输入 2 3 12 12 输出 （（3-2）*12）+12
（4）可选要求：输出要求输出该4个整数所有可能的解决方案。

2、算法描述：
采用思维上最简单的方法，就是遍历所有可能性，如果可以算出24就输出，并且让变量flag++来记录算法个数，如果flag是0，则输出-1，表示这四个数字无法算出24点。我的代码中必要有优势的去重的方法为check函数，这个函数是针对输入的数据a,b,c,d进行处理，找出他们之中相同的个数，一共有五种情况：1.都不相同，那么不做调整；2.有且仅有两个相同，那么把相应的相同的元素放在c和d 的位置；3.有两组数字分别相同(比如a=c,b=d,但是a,b不等)，那么把相同的放在一起；4.有三个相同，那么把他们发在b,c,d的位置；5.全部相同，那么不做调整。根据不同的情况，去遍历所有的可能性，一来成功去重，二来减少了运算的次数（就是比如：2，3，12，12可以认为第一个12只会在第二个之前）。

3、源代码

#include <iostream>  
using namespace std; 
int flag=0;
int Calculate(float x,float y,float z,float w);//a b c d的所有排列组合情况 
int check(int *a,int *b,int *c,int *d);

int main()  
{ 
	int a,b,c,d;  
	m_ret: //做标记  
	cout<<"请输入4个数据"<<endl;  
	cout<<" 第一个数：";  
	cin>>a;  
	cout<<" 第二个数：";  
	cin>>b;  
	cout<<" 第三个数：";  
	cin>>c;  
	cout<<" 第四个数：";  
	cin>>d;  
	cout<<"输出所有算法如下："<<endl;  
	if ((a<0)||(a>13)||(b<0)||(b>13)||(c<0)||(c>13)||(d<0)||(d>13))  
	{ 
		cout<<"你输入的输入不对，重新输入"<<endl;  
		goto m_ret; 
	} // 返回标记，重复输入 
	if(check(&a,&b,&c,&d)==0)//分成五种情况，都不想等，有两个相等(两种)，有三个相等，有四个相等 ,并且把相等的往后放 
	{
		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)  //只有一组一样的，即交换后的c和d 
	{
		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)  //有两组一样的，即交换后的a和b    c和d
	{
		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<<"一共有"<<flag<<"种算法"<<endl;
	return 0;
}  

int Calculate(float x,float y,float z,float w) //运算表达式的所有情况,里面的x,y,z,w位置相对固定，所以所有情况，靠主函数里面对他们进行排序 
{   
    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)//把相同的放一起，往后放 
{
	int temp;
	if((*a)!=(*b)&&(*a)!=(*c)&&(*a)!=(*d)&&(*b)!=(*c)&&(*b)!=(*d)&&(*c)!=(*d))//都不相等，则不做调整 
		return 0;
	else if((*a)==(*b)&&(*a)==(*c)&&(*a)==(*d))//都相等，也不做调整 
		return 4;
	else if((*a)==(*b)&&(*a)==(*c)&&(*a)!=(*d)) //其中三个相等 
	{
		temp=(*d);
		(*d)=(*a);
		(*a)=temp;
		return 3;
	}
	else if((*a)==(*b)&&(*a)==(*d)&&(*a)!=(*c)) //其中三个相等 
	{
		temp=(*c);
		(*c)=(*a);
		(*a)=temp;
		return 3;
	}
	else if((*a)==(*c)&&(*a)==(*d)&&(*a)!=(*b)) //其中三个相等 
	{
		temp=(*b);
		(*b)=(*a);
		(*a)=temp;
		return 3;
	}
	else if((*b)==(*c)&&(*b)==(*d)&&(*b)!=(*a)) //其中三个相等 
		return 3;
	else if((*a)==(*b)&&(*a)!=(*c)&&(*a)!=(*d)&&(*c)!=(*d)) //其中两个相等 
	{
		temp=(*c);
		(*c)=(*a);
		(*a)=temp;
		temp=(*d);
		(*d)=(*b);
		(*b)=temp;
		return 1;
	}
	else if((*a)==(*c)&&(*a)!=(*b)&&(*a)!=(*d)&&(*b)!=(*d))//其中两个相等
	{
		temp=(*d);
		(*d)=(*a);
		(*a)=temp;
		return 1;
	}
	else if((*a)==(*d)&&(*a)!=(*b)&&(*a)!=(*c)&&(*b)!=(*c))//其中两个相等
	{
		temp=(*c);
		(*c)=(*a);
		(*a)=temp;
		return 1;
	}
	else if((*b)==(*c)&&(*b)!=(*a)&&(*b)!=(*d)&&(*a)!=(*d))//其中两个相等
	{
		temp=(*d);
		(*d)=(*b);
		(*b)=temp;
		return 1;
	}
	else if((*b)==(*d)&&(*b)!=(*a)&&(*b)!=(*c)&&(*a)!=(*c))//其中两个相等
	{
		temp=(*c);
		(*c)=(*b);
		(*b)=temp;
		return 1;
	}
	else if((*c)==(*d)&&(*c)!=(*a)&&(*c)!=(*b)&&(*a)!=(*b))//其中两个相等
		return 1;
	else if((*a)==(*b)&&(*c)==(*d)&&(*a)!=(*c))//其中两组两个相等
		return 2;
	else if((*a)==(*c)&&(*b)==(*d)&&(*a)!=(*b))//其中两组两个相等
	{
		temp=(*b);
		(*b)=(*c);
		(*c)=temp;
		return 2;
	}
	else   //其中两组两个相等
	{
		temp=(*b);
		(*b)=(*d);
		(*d)=temp;
		return 2;
	}
}//204行 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204

4、运行结果
1.测试1：2，3，12，12：

2.测试2：1，2，2，3

我们发现是没有相应的运算式的，可以验证：

3.测试3：1，2，3，4

4.输入非法数据

并且由于我加了一个m_ret: 来做标记，可以返回重新输入。
5、总结
性能分析：
时间复杂度：因为最坏情况下随机序列(此时四个数字完全不同)的全排列个数是有限的，为4！3！种排列结果，因此时间复杂度O©
空间复杂度：O©
遇到的问题与解决方法：
容易出现表达式重复的现象，所以为了在一定程度上减少重复输出，所以我采用了对原始数据进行了一个简单的预处理，具体方法思路如上，这里就不做赘述了。
心得体会：
从结果上来看，程序代码是正确的，但是虽然长得完全一样的表达式是不会出现了，但是也只能做到这个最基本的判重，对于比如：2+3和3+2，我写的代码还是认为他们是不一样的，但在实际中，他们应该是一样的，即应该去重，不过这个实现较为困难，虽然有思路——可以采用排序和字符串比较来实现，但是那样代码长度会太长，所以只实现到了这样。
我感觉我对于数据的原始处理是写的不错的，可以根据数据的不同特征，做出不同的处理方式，一旦相同的原始，那么处理步数就会减少，那么效率就提高了。并且我可以统计出算24点的方法的数量并给出。
存在问题和改进方法：
即使我对数据进行了预处理，保证不可能出现完全一样的表达式，但是由于+和具有交换性，所以，其实2+1和1+2应该认为是等价的，即是相同的表达式，但是由于篇幅问题，我没有展开来处理，但是我有以下思路来进行处理：思路①：用二叉树的结构，叶子节点放带计算的数字，然后他们的父节点先放运算符，然后用计算后的值替换，所以当某两个数字共同的父节点是+或者x时，我们可以交换左右孩子的值，看此时父节点算出来的值是否一样，如果一样就可以只输出其中某一个。思路①：和上面大致相同，但是对左右孩子的值做一个要求，即对于父节点是+或者x的，右孩子的值要大于等于左孩子的值，这样也可以做到去重。