游戏规则： 一副牌中去掉大小王，在剩下的52张牌中任意取四张。使用四则运算，使其最后结果为24.其中每张牌只能使用一次且A=1,J=11，Q=12，K=13。
譬如 2,4,6,8 ------> 结果为 6/(4-2)*8=24;
算法思考： 首先，从宏观上说，这种问题都是遍历穷举。再看看运算符，其中+，* 都是没有顺序的。即（a*b=b*a）, 但是 -、/ 是有顺序的。那么假设都有顺序的。那么就可以统一处理了（最多效率低点，先解决问题。再考虑优化）。那么遍历所有a,b,c,d 以及 三次运算 。即A(4,4) *4*4*4 就是该算法的复杂度。（事实证明我错了。后面会讲到。）
微观上，由于中间有除法，那么不能用int类型来储存数据了。需要用double或者float.每次运算都只有两个数运算。
24点游戏编程具体算法思想可以参考《编程之美》，下面给出自己根据文中算法改写的C语言算法：
|
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
|
#include <stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>const
double
Threshold = 1E-6;
#define CardsNumber 4const
int
ResultValue = 24;
double
NumberCard[CardsNumber];
char
*result[CardsNumber];
char
*oprate(char
*expa,char
*expb,char
op)
{ //char *c=r;
char
*c=(char
*)malloc(sizeof(char)*50);
char
*b="(";
char
*a=")";
strcpy(c,b);
strcat(c,expa);
strcat(c,&op);
strcat(c,expb);
strcat(c,a);
return
c;
}int
PointGame(int
n)
{ int
i,j,k;
double
a,b;
char
expa[50]={‘0‘};
char
expb[50]={‘0‘};
char
op;
if
(n == 1)
{
if
(fabs(NumberCard[0]-ResultValue) < Threshold)
{
printf("%s\n",result[0]);
return
-1;
}
else
{
return
0;
}
}
else
{
for
(i = 0;i < n;i++)
{
for
(j = i+1;j < n;j++)
{
a = NumberCard[i];
b = NumberCard[j];
NumberCard[j] = NumberCard[n-1];
/* 因为需要删去两个已经进行过运算的数，所以在此利用NumberCard[i]保存运算结果，
利用NumberCard[j]保存最后一个数
*/
for
(k=0;k<strlen(result[i]);k++)
{
expa[k]=result[i][k];
}
expa[k]=‘\0‘;
for
(k=0;k<strlen(result[j]);k++)
{
expb[k]=result[j][k];
}
expb[k]=‘\0‘;
strcpy(result[j],result[n-1]);
op = ‘+‘;
result[i]=oprate(expa,expb,op);
NumberCard[i] = a+b;
if
(PointGame(n-1))
return
-1;
op = ‘-‘;
result[i]=oprate(expa,expb,op);
NumberCard[i] = a-b;
if
(PointGame(n-1))
return
-1;
op = ‘-‘;
result[i]=oprate(expb,expa,op);
NumberCard[i] = b-a;
if
(PointGame(n-1))
return
-1;
op = ‘*‘;
result[i]=oprate(expa,expb,op);
NumberCard[i] = a*b;
if
(PointGame(n-1))
return
-1;
if
(b != 0)
{
op = ‘/‘;
result[i]=oprate(expa,expb,op);
NumberCard[i] = a/b;
if
(PointGame(n-1))
return
-1;
}
if
(a != 0)
{
op = ‘/‘;
result[i]=oprate(expb,expa,op);
NumberCard[i] = b/a;
if
(PointGame(n-1))
return
-1;
}
NumberCard[i] = a;
NumberCard[j] = b;
strcpy(result[i],expa);
strcpy(result[j],expb);
}
}
}
return
0;
}int
main()
{ int
x;
int
i;
char
buffer[4][100]={‘0‘};
for
(i = 0;i < CardsNumber;i++)
{
printf("the %d number:\n",i);
scanf("%d",&x);
NumberCard[i]=x;
itoa(x,buffer[i],10);
result[i]=buffer[i];
}
i=PointGame(CardsNumber);
if
(i!=0)
{
printf("Success!\n");
}
else
{
printf("Fail\n");
}
system("pause");
return
0;
} |