求24问题，即给指定4个1到9之间的数字，使用+、-、*、/和括号经过四则运算得24。
乍一看，这道题没有思路。经过多天的思考和实践后，终于想出一个比较好的解决方法。即动态规划算法思想（动态规划就不介绍了）。
首先，抽象一下问题：即给定数列P(N)(N>=1),使P(N)经过简单的四则运算的到目的结果M。考虑：不管数列P(N)怎么运算，总是2个数先行计算的，在和其他的数运算。因此我们的着手点就在于，从P(N)个数中取2个数（2个数有序）经过简单四则运算后得到结果R，然后把R和剩余的N-2个数形成一个新的数列P（N-1），问题就变为使P(N-1)经过简单四则运算后得到结果M。重复上面步骤，知道最后剩余一个数即P(N)经过一种简单四则运算得到的结果，和M比较，相等即得到目标，否则，换其他四则运算方法。
任意取两个数（有序）算法为:
for I := 0 to N - 1 do
for J := 0 to N - 1 do
if I <> J then
begin
N1 := P(N)[I];
N2 := P(N)[J];
end;
任取一种运算符运算：Opr := + - * /
N1 Opr N2 = NewN
P(N)中去除N1，和N2，并添加NewN形成新的P(N-1);
。。。。。。
直到P(1);
P(1)[0] = R那么得到想要的结果
P(1)[0] <> R 那么首先换其他运算符运算，在得到P(1)比较
。。。。。。
直到得到结果。
在考虑一下效率的问题：这样递归循环肯定要花费大量的时间。
首先我们发现N1，N2进行"+"和"*"，不管N1+N2,还是N2+N1的结果是相同，只是"-"和"/"结果会不一样的，这样我们可以额外定义2个操作符反减"D"和反除"F",N1 D N2 = N2 - N1,这样既不会漏掉结果，又不会重复执行N1 + N2和N2 + N1。
任取2个数(无序)为
for I := 0 to N - 2 do
for J := I + 1 to N - 1 do
if I <> J then
begin
N1 := P(N)[I];
N2 := P(N)[J];
end;
在考虑对于P(N)2次任取的数N1，N2和N3，N4可能相同即N1=N3，N2=N4，所以我们记录一下在P(N)所有取出2个数的情况，然后在新取2个数和历史记录比较，如果这种情况存在，那么我们不用继续往下分析，只要重新取2个数分析就可以了。
在考虑N1=N2的问题，那么我们就不计算反减D和反除F了。
这样求出所有可能得到结果M的等式，可能会有重复的，过滤一下等式完全一样的情况，其他情况当作多种情况考虑。
 #include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;
//该算法是将4个1->9的数字经过数学运算得到24，没有进行优化，大致思路如下：
//1.排列四个数字，参见main()
//2.针对四个数字的每一种排列，排列运算符顺序,参见opSort()
//3.针对四个数字的排列和运算符排列，根据"不同形式"做运算,参见isResult()
//4.如果运算节过能得到24，则按照不同的"运算形式"输出数字排列和运算符排列，参见outputFun*()
float calc(float n1,float n2,int idex)
  ...{
 switch(idex)
  ...{
case 1:
return n1+n2;
break;
case 2:
return n1-n2;
break;
case 3:
return n1*n2;
break;
case 4:
if (n2>0.1||n2<-0.1)
...{
return n1/n2;
 }
else
return -100.0;
break;
default:
return -100.0;
break;
}
 }
char getChar(int idex)
...{
switch(idex)
...{
case 1:
return '+';
break;
case 2:
return '-';
break;
case 3:
return '*';
break;
case 4:
return '/';
break;
}
}
//((n0-n1)-n2)-n3
void outputFun(int *iArray4,int *irArray)
...{
cout<<"(("<<iArray4[0];
for(int i=0; i<3; i++)
...{
switch(irArray[i])
...{
case 1:
cout<<'+';
break;
case 2:
cout<<'-';
break;
case 3:
cout<<'*';
break;
case 4:
cout<<'/';
break;
}
cout<<iArray4[i+1];
if(i != 2)
cout<<')';
}
cout<<endl;
}
//(n0-n1)-(n2-n3)
void outputFun1(int *iArray4,int *irArray)
...{
cout<<"("<<iArray4[0];
for(int i=0; i<3; i++)
...{
switch(irArray[i])
...{
case 1:
cout<<'+';
break;
case 2:
cout<<'-';
break;
case 3:
cout<<'*';
break;
case 4:
cout<<'/';
break;
}
if (i == 1)
...{
cout<<'(';
}
cout<<iArray4[i+1];
if(i%2==0)
cout<<')';
}
cout<<endl;
}
//(n2-n3)-(n0-n1)
void outputFun2(int *iArray4,int *irArray)
...{
cout<<"("<<iArray4[2];
cout<<getChar(irArray[2]);
cout<<iArray4[3]<<")";
cout<<getChar(irArray[1]);
cout<<"("<<iArray4[0];
cout<<getChar(irArray[0]);
cout<<iArray4[1]<<")";
cout<<endl;
}
//(n2-(n0-n1))-n3
void outputFun3(int *iArray4,int *irArray)
...{
cout<<"("<<iArray4[2];
cout<<getChar(irArray[1]);
cout<<"("<<iArray4[0];
cout<<getChar(irArray[0]);
cout<<iArray4[1]<<"))";
cout<<getChar(irArray[2]);
cout<<iArray4[3];
cout<<endl;
}
//n3-(n2-(n0-n1))
void outputFun4(int *iArray4,int *irArray)
...{
cout<<iArray4[3];
cout<<getChar(irArray[2]);
cout<<"("<<iArray4[2];
cout<<getChar(irArray[1]);
cout<<"("<<iArray4[0];
cout<<getChar(irArray[0]);
cout<<iArray4[1]<<"))";
cout<<endl;
}
//n3-((n0-n1)-n2)
void outputFun5(int *iArray4,int *irArray)
...{
cout<<iArray4[3];
cout<<getChar(irArray[2]);
cout<<"(("<<iArray4[0];
cout<<getChar(irArray[0]);
cout<<iArray4[1]<<")";
cout<<getChar(irArray[1]);
cout<<iArray4[2]<<")";
cout<<endl;
}
bool isResult(int *fp,int* ip)
...{
bool bResult=false;
float fr=0.0,fr1=0.0;
//((n0-n1)-n2)-n3
fr=calc((float)*fp,(float)*(fp+1),*ip);
fr=calc((float)fr,(float)*(fp+2),*(ip+1));
fr=calc((float)fr,(float)*(fp+3),*(ip+2));
int ir=(int)fr;
if(fr<24.01&&fr>23.99)//if (ir==24)
...{
outputFun(fp,ip);
bResult=true;
}
//(n0-n1)-(n2-n3)
fr=calc((float)*fp,(float)*(fp+1),*ip);
fr1=calc((float)*(fp+2),(float)*(fp+3),*(ip+2));
fr=calc((float)fr,(float)fr1,*(ip+1));
if (fr<24.01&&fr>23.99)
...{
outputFun1(fp,ip);
bResult=true;
}
//(n2-n3)-(n0-n1)
fr=calc((float)*fp,(float)*(fp+1),*ip);
fr1=calc((float)*(fp+2),(float)*(fp+3),*(ip+2));
fr=calc((float)fr1,(float)fr,*(ip+1));
if (fr<24.01&&fr>23.99)
...{
outputFun2(fp,ip);
bResult=true;
}
//(n2-(n0-n1))-n3
fr=calc((float)*fp,(float)*(fp+1),*ip);
fr=calc((float)*(fp+2),(float)fr,*(ip+1));
fr=calc((float)fr,(float)*(fp+3),*(ip+2));
if(fr<24.01&&fr>23.99)//if (ir==24)
...{
outputFun3(fp,ip);
bResult=true;
}
//n3-(n2-(n0-n1))
fr=calc((float)*fp,(float)*(fp+1),*ip);
fr=calc((float)*(fp+2),(float)fr,*(ip+1));
fr=calc((float)*(fp+3),(float)fr,*(ip+2));
if(fr<24.01&&fr>23.99)//if (ir==24)
...{
outputFun4(fp,ip);
bResult=true;
}
//n3-((n0-n1)-n2)
fr=calc((float)*fp,(float)*(fp+1),*ip);
fr=calc((float)fr,(float)*(fp+2),*(ip+1));
fr=calc((float)*(fp+3),(float)fr,*(ip+2));
if(fr<24.01&&fr>23.99)//if (ir==24)
...{
outputFun5(fp,ip);
bResult=true;
}
return bResult;
}
bool opSort(int *iArray4)
...{
bool bResult=false;
int irArray[3];
for (int p=1;p<5;p++)
...{
for (int q=1;q<5;q++)
...{
for (int r=1;r<5;r++)
...{
irArray[0]=p;
irArray[1]=q;
irArray[2]=r;
if (isResult(iArray4,irArray))
...{
bResult=true;//outputFun(iArray4,irArray);
}
}
}
}
return bResult;
}
void main(int argc, char *argv[])
...{
bool bFind=false;
cout<<"please input 4 numbers"<<endl;
int iArray[4];
cin>>iArray[0]>>iArray[1]>>iArray[2]>>iArray[3];
int iArray4[4];
for (int i=0;i<4;i++)
...{
for (int j=0;j<4;j++)
...{
if (i==j)
continue;
for (int k=0;k<4;k++)
...{
if (i==k||j==k)
continue;
for (int m=0;m<4;m++)
...{
if (i==m||j==m||k==m)
continue;
iArray4[0]=iArray[i];
iArray4[1]=iArray[j];
iArray4[2]=iArray[k];
iArray4[3]=iArray[m];
if (opSort(iArray4))
...{
bFind=true;
}
}
}
}
}
if (!bFind)
...{
cout<<"not find correct calc"<<endl;
}
}
|
