Question

1个关于取4张牌计算24点的问题

编写一个程序，任取四张牌，不考虑花色，只考虑牌上的数字，1～10依次表示本身，J表示11，Q表示12，K表示13，只能采用括号和四则运算，要求计算得到24点，若无解则输出一行NO SOLUTION，若有多种解答，输出其中一种即可。

Answer 1

#include <stdio.h>

void Hello( )
{
puts("\n");

puts(" ##################################################");
puts(" ## ##");
puts(" ## 24点程序 ##");
puts(" ## ##");
puts(" ##################################################");
puts(" ## ##");
puts(" ## 输入4个整数，用它们构造一个算术四则运算， ##");
puts(" ## 使结果等于24。每个数恰好利用一次。 ##");
puts(" ## ##");
puts(" ## 例如，输入为 2 7 10 6 ##");
puts(" ## 输出为（2＋6）x（10－7） ##");
puts(" ## …… ##");
puts(" ## …… ##");
puts(" ## （可输出有重复的全部解） ##");
puts(" ## ##");
puts(" ##################################################");
puts(" ## ##");
puts(" ## 设计者：NotorFast ##");
puts(" ## 时 间：2004-10-16 ##");
puts(" ## ##");
puts(" ##################################################");

puts("\n");
}

const int N = 4; // 操作数的个数/栈的极限高度
#define eps 1E-6 // 浮点精度
inline float abs(float x) { return x >= 0.0 ? x : -x; }

// 栈模板
template <class T, int N> class STACK {
protected:
T a[N]; // 栈的存储体
int n; // 栈的高度/未来栈顶位置

public:
STACK( ) { reset( ); } // 栈初始化
void reset( ) { n = 0; } // 清空栈
void push(T x) { if(n < N) a[n++] = x; else puts("栈上溢"); } // 压入数据到栈顶
T pop( ) { if(n > 0) return a[--n]; else puts("栈下溢"); } // 弹出栈顶数据
// T top( ) { if(n > 0) return a[n-1]; else puts("栈空"); } // 查询栈顶元素
// bool isempty( ) { return n == 0; } // 查询栈是否为空
// int heigth( ) { return n; } // 查询栈的高度
};

const char opr[ ] = "+-*/";
int a[N]; // 输入的4个数
STACK<float, N> opnstk; // 操作数栈

int b[N], K = 0; // a[]的备份/用于生产排列的工作区

void gen(int n, int m) // 生成n个数中取m个数的全排列。m = n时即为n个数的全排列。---
{ // --- 每产生一个排列，放入b[]中。
void gen24( ); // 函数声明
int i;

if(m == 0) {
// for(i = 0; i < K; ++i) printf("%d ", b[i]); putchar('\n'); // 如果只是为了输出排列
gen24( ); // 函数调用
}

else
for(i = 0; i < n; ++i) if(a[i] != '.') {
b[K++] = a[i];
a[i] = '.';
gen(n, m - 1);
a[i] = b[--K];
}
}

// 用后缀表达式计算，用中缀表达式输出。
// --- n表示将一个操作数压栈，#表示进行一步运算。
// --- abcd指操作数的输出顺序，123指运算符的输出顺序。
const char stkmode[5][22] = {
"nnnn### = a3(b2(c1d))",
"nnn#n## = a3((b1c)2d)",
"nnn##n# = (a2(b1c))3d",
"nn#nn## = (a1b)3(c2d)",
"nn#n#n# = ((a1b)2c)3d",
};

void gen24( ) // 用b[]中的4个数产生等于24的算式
{
bool calc(float, char, float, float&); // 函数声明
int i, jn, jo, p0, p1, p2;
char enumopr[3], op;
float a1, a2, c;
const char *p;

// for(i = 0; i < K; ++i) printf("%d ", b[i]); putchar('\n'); // 如果只是为了输出排列

for(i = 0; i < 5; ++i) // 尝试每种栈模式

for(p0 = 0; p0 < 4; ++p0) { enumopr[0] = opr[p0];
for(p1 = 0; p1 < 4; ++p1) { enumopr[1] = opr[p1];
for(p2 = 0; p2 < 4; ++p2) { enumopr[2] = opr[p2];

opnstk.reset( );

for(jn = jo = 0, p = stkmode[i]; *p != ' '; ++p) switch(*p) {
case 'n':
opnstk.push(b[jn++]); break;

case '#':
a2 = opnstk.pop( ); a1 = opnstk.pop( ); op = enumopr[jo++];
if(calc(a1, op, a2, c)) opnstk.push(c); else goto loc_1;
}

if(abs(c - 24) < eps) {
while(*++p != 0) switch(*p) {
case '(':
case ')':
putchar(*p);
break;
case 'a':
case 'b':
case 'c':
case 'd':
printf("%d", b[*p - 'a']);
break;
case '1':
case '2':
case '3':
printf("%c", enumopr[*p - '1']);
break;
}
putchar('\n');
goto loc_2;
}

loc_1: continue;
}}}

loc_2: return;
}

bool calc(float a, char op, float b, float& c)
{
static bool bRet;

switch(bRet = true, op) {
case '+': c = a + b; break;
case '-': c = a - b; break;
case '*': c = a * b; break;
case '/':
if(abs(b) > eps) c = a / b; else bRet = false;
}

return bRet;
}

int main( )
{
Hello( );

while(true) {
printf("请输入%d个整数（用空白分隔。结束程序请输入0）: ", N);
for(int i = 0; i < N; ++i) { scanf("%d", &a[i]); if(a[i] == 0) goto loc_0; }

K = 0; gen(N, N);
}

loc_0: return 0;
}

Answer 2

#include
<stdio.h>
void
Hello(
)
{
puts("\n");
puts("
##################################################");
puts("
##
##");
puts("
##
24点程序
##");
puts("
##
##");
puts("
##################################################");
puts("
##
##");
puts("
##
输入4个整数，用它们构造一个算术四则运算，
##");
puts("
##
使结果等于24。每个数恰好利用一次。
##");
puts("
##
##");
puts("
##
例如，输入为
2
7
10
6
##");
puts("
##
输出为(2+6)x(10-7)
##");
puts("
##
……
##");
puts("
##
……
##");
puts("
##
(可输出有重复的全部解)
##");
puts("
##
##");
puts("
##################################################");
puts("
##
##");
puts("
##
设计者:NotorFast
##");
puts("
##
时
间:2004-10-16
##");
puts("
##
##");
puts("
##################################################");
puts("\n");
}
const
int
N
=
4;
//
操作数的个数/栈的极限高度
#define
eps
1E-6
//
浮点精度
inline
float
abs(float
x)
{
return
x
>=
0.0
?
x
:
-x;
}
//
栈模板
template
<class
T,
int
N>
class
STACK
{
protected:
T
a[N];
//
栈的存储体
int
n;
//
栈的高度/未来栈顶位置
public:
STACK(
)
{
reset(
);
}
//
栈初始化
void
reset(
)
{
n
=
0;
}
//
清空栈
void
push(T
x)
{
if(n
<
N)
a[n++]
=
x;
else
puts("栈上溢");
}
//
压入数据到栈顶
T
pop(
)
{
if(n
>
0)
return
a[--n];
else
puts("栈下溢");
}
//
弹出栈顶数据
//
T
top(
)
{
if(n
>
0)
return
a[n-1];
else
puts("栈空");
}
//
查询栈顶元素
//
bool
isempty(
)
{
return
n
==
0;
}
//
查询栈是否为空
//
int
heigth(
)
{
return
n;
}
//
查询栈的高度
};
const
char
opr[
]
=
"+-*/";
int
a[N];
//
输入的4个数
STACK<float,
N>
opnstk;
//
操作数栈
int
b[N],
K
=
0;
//
a[]的备份/用于生产排列的工作区
void
gen(int
n,
int
m)
//
生成n个数中取m个数的全排列。m
=
n时即为n个数的全排列。---
{
//
---
每产生一个排列，放入b[]中。
void
gen24(
);
//
函数声明
int
i;
if(m
==
0)
{
//
for(i
=
0;
i
<
K;
++i)
printf("%d
",
b[i]);
putchar('\n');
//
如果只是为了输出排列
gen24(
);
//
函数调用
}
else
for(i
=
0;
i
<
n;
++i)
if(a[i]
!=
'.')
{
b[K++]
=
a[i];
a[i]
=
'.';
gen(n,
m
-
1);
a[i]
=
b[--K];
}
}
//
用后缀表达式计算，用中缀表达式输出。
//
---
n表示将一个操作数压栈，#表示进行一步运算。
//
---
abcd指操作数的输出顺序，123指运算符的输出顺序。
const
char
stkmode[5][22]
=
{
"nnnn###
=
a3(b2(c1d))",
"nnn#n##
=
a3((b1c)2d)",
"nnn##n#
=
(a2(b1c))3d",
"nn#nn##
=
(a1b)3(c2d)",
"nn#n#n#
=
((a1b)2c)3d",
};
void
gen24(
)
//
用b[]中的4个数产生等于24的算式
{
bool
calc(float,
char,
float,
float&);
//
函数声明
int
i,
jn,
jo,
p0,
p1,
p2;
char
enumopr[3],
op;
float
a1,
a2,
c;
const
char
*p;
//
for(i
=
0;
i
<
K;
++i)
printf("%d
",
b[i]);
putchar('\n');
//
如果只是为了输出排列
for(i
=
0;
i
<
5;
++i)
//
尝试每种栈模式
for(p0
=
0;
p0
<
4;
++p0)
{
enumopr[0]
=
opr[p0];
for(p1
=
0;
p1
<
4;
++p1)
{
enumopr[1]
=
opr[p1];
for(p2
=
0;
p2
<
4;
++p2)
{
enumopr[2]
=
opr[p2];
opnstk.reset(
);
for(jn
=
jo
=
0,
p
=
stkmode[i];
*p
!=
'
';
++p)
switch(*p)
{
case
'n':
opnstk.push(b[jn++]);
break;
case
'#':
a2
=
opnstk.pop(
);
a1
=
opnstk.pop(
);
op
=
enumopr[jo++];
if(calc(a1,
op,
a2,
c))
opnstk.push(c);
else
goto
loc_1;
}
if(abs(c
-
24)
<
eps)
{
while(*++p
!=
0)
switch(*p)
{
case
'(':
case
')':
putchar(*p);
break;
case
'a':
case
'b':
case
'c':
case
'd':
printf("%d",
b[*p
-
'a']);
break;
case
'1':
case
'2':
case
'3':
printf("%c",
enumopr[*p
-
'1']);
break;
}
putchar('\n');
goto
loc_2;
}
loc_1:
continue;
}}}
loc_2:
return;
}
bool
calc(float
a,
char
op,
float
b,
float&
c)
{
static
bool
bRet;
switch(bRet
=
true,
op)
{
case
'+':
c
=
a
+
b;
break;
case
'-':
c
=
a
-
b;
break;
case
'*':
c
=
a
*
b;
break;
case
'/':
if(abs(b)
>
eps)
c
=
a
/
b;
else
bRet
=
false;
}
return
bRet;
}
int
main(
)
{
Hello(
);
while(true)
{
printf("请输入%d个整数(用空白分隔。结束程序请输入0):
",
N);
for(int
i
=
0;
i
<
N;
++i)
{
scanf("%d",
&a[i]);
if(a[i]
==
0)
goto
loc_0;
}
K
=
0;
gen(N,
N);
}
loc_0:
return
0;
}