24点的三种算法思路及代码(2)

此文所贴代码均为面向过程的C(++)代码，在VC6下编译通过。

第一种思路：
把多元运算转化为两元运算，先从四个数中取出两个数进行运算，然后把运算结果和第三个数进行运算，再把结果与第四个数进行运算。在求表达式的过程中，最难处理的就是对括号的处理，而这种思路很好的避免了对括号的处理。基于这种思路有两种算法：

第二种算法（此算法思想参考了CSDN(penguinMII)–企鹅的算法思想）：
可以寻找所有表达式的规律，得出如下结论：把表达式看成一个函数F(A,B,C,D)=24，可分两种情况F=(((A,B),C),D)和F=((A,B),(C,D))，对其分别计算即可得到答案，算法过程如下：
1)先对第一个数和第二个数进行计算，并保存结果和表达式；
2)对上述结果与第三个数进行计算，并保存结果和表达式；
3)对上述结果与第四个个数进行计算，并保存结果和表达式；
4)判断结果，并输出结果；
5)对第三个数和第四个数进行计算，并保存结果和表达式；
6)对第一个数与第二个数的结果和第三个数与第四个数的结果进行计算，并保存结果和表达式；
7)判断结果，并输出结果；
在这种算法中需要对所有数据进行排列组合，对所有组合进行上述运算过程。

说明：’-‘和’/’有两种情况，’a-b’用’a-b’表示,’b-a’用’a|b’表示，’a/b’用’a/b’表示，’b/a’用’a\b’表示，’\’是转义字符，要用’\\’表示。

程序代码如下：

/********************************/
/* fdream.net */
/* Author:Fdream */
/* 引用此算法请保留此信息 */
/********************************/

#include
#include
#include

using namespace std;

const double PE=1E-6;
const int RESULT = 24;

void main(void){
int com[24][4]={0};
int number[4]={0};
int f,i,j,m,n,k=0,flag=0,s=0,comNum=0;

char buffer[20];
string expa,expb,expression;

//输入数据
for(i=0;i<4;i++)
cin >> number[i];

//生成数据的排列组合
for(i=0;i<4;i++){
for(j=0;j<4;j++){
if(j!=i){
for(m=0;m<4;m++){
if(m!=i&&m!=j){
for(n=0;n<4;n++)
if(n!=i&&n!=j&&n!=m){
flag=1;
//除去重复的排列组合
for(s=0;s if(com[s][0]==number[i]&&com[s][1]==number[j]&&com[s][2]==number[m]&&com[s][3]==number[n]){
flag=0;
}
}
if(flag){
com[k][0]=number[i];
com[k][1]=number[j];
com[k][2]=number[m];
com[k][3]=number[n];
k++;
comNum++;
}
}
}
}
}
}
}

//生成运算符的排列组合
char op[6]={‘+’,’-‘,’|’,’*’,’/’,’\\’};
char opArray[216][3]={‘+’};
k=0;
for(i=0;i<6;i++){
for(j=0;j<6;j++)
for(m=0;m<6;m++){
opArray[k][0]=op[i];
opArray[k][1]=op[j];
opArray[k][2]=op[m];
k++;
}

}

//临时数组，计算时使用
double tempNum[4]={0};

for(i=0;i for(j=0;j<216;j++){
for(f=0;f<4;f++)
tempNum[f]=com[i][f];
k=1;

//判断运算符
for(n=0;n<3;n++){
switch(opArray[j][n]){
case ‘+’:
tempNum[0]=tempNum[0]+tempNum[k];
break;
case ‘-‘:
tempNum[0]=tempNum[0]-tempNum[k];
break;
case ‘|’:
tempNum[0]=tempNum[k]-tempNum[0];
break;
case ‘*’:
tempNum[0]=tempNum[0]*tempNum[k];
break;
case ‘/’:
tempNum[0]=tempNum[0]/tempNum[k];
break;
case ‘\\’:
tempNum[0]=tempNum[k]/tempNum[0];
break;
}
k++;
}

//保存结果
if(k==4&&fabs(tempNum[0]-RESULT) itoa(com[i][0],buffer,10);
expression=buffer;
for(int t=0;t<3;t++){
itoa(com[i][t+1],buffer,10);
expb=buffer;
switch(opArray[j][t]){
case ‘|’:
expression='(‘+expb+’-‘+expression+’)’;
break;
case ‘\\’:
expression='(‘+expb+’/’+expression+’)’;
break;
default :
expression='(‘+expression+opArray[j][t]+expb+’)’;
break;
}
}
cout << expression << endl;
}
}
}
}

系列文章：
24点的三种算法思路及代码(1)
24点的三种算法思路及代码(2)
24点的三种算法思路及代码(3)