Question

关于24点的C语言代码，能直接使用的，注释最好多一点，以便理解

（1） 4张牌均为1-10内的数（随机产生）；
（2） 每道题均有答案；
（3） 必要时可以给出一个提示答案。答案格式例子：2+7=9；9*3=27； 27-3=24
谢谢了

Answer 1

这道题目如果没其他较好的办法就采用暴力穷举解决。根据给定的4个数，得出两棵不同构的语法树。
O O
/ \ / \
O O 和 o O
/ \ / \ / \
o o o o o O
/ \
o o
分别得出的逆波兰式为：ooOooOO和ooooOOO，其中o为操作数，O为运算符。然后对这两种形式的逆波兰式进行穷举并计算即可。对于第一种逆波兰式共有4!*4^3=4*3*2*4*4*4=1536种不同情况，第二种逆波兰式也有1536种不同情况。因此，若无解，则共循环测试3072次。
include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <conio.h>
char RPN[7];
char operdata[24][4] = {{0,1,2,3},{0,1,3,2},{0,2,1,3},{0,2,3,1},{0,3,1,2},{0,3,2,1},/*操作数的24种不同排列*/
{1,0,2,3},{1,0,3,2},{1,2,0,3},{1,2,3,0},{1,3,0,2},{1,3,2,0},
{2,1,0,3},{2,1,3,0},{2,0,1,3},{2,0,3,1},{2,3,1,0},{2,3,0,1},
{3,1,2,0},{3,1,0,2},{3,2,1,0},{3,2,0,1},{3,0,1,2},{3,0,2,1}
};
char oper[64][3]={{-1,-1,-1},{-1,-1,-2},{-1,-1,-3},{-1,-1,-4},/*操作符的64种不同排列*/
{-1,-2,-1},{-1,-2,-2},{-1,-2,-3},{-1,-2,-4}, /*-1~-4分别表示:+ - * / */
{-1,-3,-1},{-1,-3,-2},{-1,-3,-3},{-1,-3,-4},
{-1,-4,-1},{-1,-4,-2},{-1,-4,-3},{-1,-4,-4},
{-2,-1,-1},{-2,-1,-2},{-2,-1,-3},{-2,-1,-4},
{-2,-2,-1},{-2,-2,-2},{-2,-2,-3},{-2,-2,-4},
{-2,-3,-1},{-2,-3,-2},{-2,-3,-3},{-2,-3,-4},
{-2,-4,-1},{-2,-4,-2},{-2,-4,-3},{-2,-4,-4},
{-3,-1,-1},{-3,-1,-2},{-3,-1,-3},{-3,-1,-4},
{-3,-2,-1},{-3,-2,-2},{-3,-2,-3},{-3,-2,-4},
{-3,-3,-1},{-3,-3,-2},{-3,-3,-3},{-3,-3,-4},
{-3,-4,-1},{-3,-4,-2},{-3,-4,-3},{-3,-4,-4},
{-4,-1,-1},{-4,-1,-2},{-4,-1,-3},{-4,-1,-4},
{-4,-2,-1},{-4,-2,-2},{-4,-2,-3},{-4,-2,-4},
{-4,-3,-1},{-4,-3,-2},{-4,-3,-3},{-4,-3,-4},
{-4,-4,-1},{-4,-4,-2},{-4,-4,-3},{-4,-4,-4}
};
void Swap(int &a, int &b)
{
int tmp = a;
a = b;
b = tmp;
}
int compute(char *a) //如果是一个解，则返回1，否则返回0，a是一个逆波兰式
{
int stack[10], top = -1, i, s1, s2;
for(i = 0; i < 7; i++)
{
if(a[i] > 0 && a[i] < 11) stack[++top] = a[i];
else {
s1 = stack[top--];
s2 = stack[top--];
if(s1 < s2) Swap(s1, s2);
switch(a[i]) {
case -1: stack[++top] = s1 + s2;
break;
case -2: stack[++top] = s1 - s2;
break;
case -3: stack[++top] = s1 * s2;
break;
case -4: if((s1 && s2) && (s1 % s2 == 0)) stack[++top] = s1 / s2;
else return 0;
}
}
}
return (stack[top] == 24);
}
void cout(char *a)
{
int stack[10], top = -1, i, s1, s2;
for(i = 0; i < 7; i++)
{
if(a[i] > 0 && a[i] < 11) stack[++top] = a[i];
else {
s1 = stack[top--];
s2 = stack[top--];
if(s1 < s2) Swap(s1, s2);
switch(a[i]) {
case -1: stack[++top] = s1 + s2;
printf("%d + %d = %d\t", s1, s2, s1+s2);
break;
case -2: stack[++top] = s1 - s2;
printf("%d - %d = %d\t", s1, s2, s1-s2);
break;
case -3: stack[++top] = s1 * s2;
printf("%d * %d = %d\t", s1, s2, s1*s2);
break;
case -4: if(s1 % s2 == 0) stack[++top] = s1 / s2;
printf("%d / %d = %d\t", s1, s2, s1/s2);
}
}
}
}
void main( )
{
char data[4], i, j, k, ch;
int flag;
srand(time(0));
printf("若退出，请按\'n\'键，否则请按其他键继续\n");
ch = getch( );
while(ch != 'n')
{
flag = 0;
for(i = 0; i < 4; i++)
{
data[i] = rand( ) % 10 + 1;
printf("%d ", data[i]);
}
printf("\n");
for(i = 0; i < 24 && !flag; i++)
{
RPN[0] = data[operdata[i][0]];
RPN[1] = data[operdata[i][1]];
RPN[3] = data[operdata[i][2]];
RPN[4] = data[operdata[i][3]];
for(j = 0; j < 64 && !flag; j++)
{
RPN[2] = oper[j][0];
RPN[5] = oper[j][1];
RPN[6] = oper[j][2];

flag = compute(RPN);
if(flag)
{
cout(RPN);
}
}
RPN[0] = data[operdata[i][0]];
RPN[1] = data[operdata[i][1]];
RPN[2] = data[operdata[i][2]];
RPN[3] = data[operdata[i][3]];
for(j = 0; j < 64 && !flag; j++)
{
RPN[4] = oper[j][0];
RPN[5] = oper[j][1];
RPN[6] = oper[j][2];

flag = compute(RPN);
if(flag)
{
cout(RPN);
}
}
}
if(!flag) printf("无解\n");
printf("若退出，请按\'n\'键，否则请按其他键继续\n");
ch = getch( );
}
}

追问

能不能在代码里面写些注释啊，很多语句不太理解诶，谢谢啦

追答

对于逆波兰式的分析，是根据上面的两棵不同构的语法树而来，而由语法树得到其对应的逆波兰式是对语法树进行后序遍历而得到的。因此两个不同构的语法树就可得到两种不同构的逆波兰式。而每种逆波兰式，根据操作数的不同排列和操作符的不同组合，又可得到1536个的逆波兰式（存在少部分是相同的）。
char RPN[7];用于存放一个逆波兰式，这里选取用char数组，是因为每个操作数都<<127，出于节省存储空间考虑，而没有采用int数组，其实用int数组亦可。数组中的每个元素可能为操作数，也可能为操作符，如果是1~10之间的数，则为操作数，若为-1~-4之间的数，则分别表示：+、-、*、/。题目最终是要对这个逆波兰式求值，看其结果是否为24。
char operdata[24][4]用于存放4个操作数的24中不同的排列。
char oper[64][3]用于存放4个操作符中取其中3个的共64种不同情况取法，因为取操作符是可以重复取，所以共有64种不同取法。
int compute(char *a)该函数用于对含有如上所述的逆波兰式a进行求值，求值时用到一个栈，求值规则是：对a中的元素从前向后逐个读取，若遇到操作数，则将操作数进栈，若遇到操作符@，则将栈中最上两个元素出栈，然后求“大者@小者”，将结果进栈。到最后则返回栈顶的值。若出现除0问题，则返回0。
void cout(char *a)函数用于输出一个解。输出规则与前面的求解规则是一致的。
主函数中的两层for循环用于根据给定的4个操作数生成3072种不同的逆波兰式，依次求解，直到找到一个解时结束，若没有找到则表示“无解”。

追问

请问应该如何改进程序，使之能够输出所有的结果。

追答

还是穷举，这时找到一个解时，不提前退出，而是输出后，继续找下一个解

在三行for语句处都删除 &&!flag即可

追问

谢谢啦

老师您好，请问应如何改进程序，达到以下功能：加入JQK，用链表查询出的题和解题信息，主菜单有提示，查看历史，已出题的难度排序这些功能。我重新提了一个问题，您回答了我就给您分。