算法-程序实现“24”点算法

Question

不限程序，说说思路。并简述下复杂程度
用程序实现24点，即：任给4个整数，可以用加减乘除，算出最后公式为24的公式，如果不能得出24则打印“false”；
如：13,13,6,4 得出公式：4+13+13-6=24
如：11,10,8，,1 得出供述：false

Answer 1

先简单分析下，我采用典型的枚举法，任意四个数算24点，一共需要填入3个运算符，并且每两个数字之间的运算符有4种选择，就是加减乘除。在编程中，我是用循环来填入各种运算符，然后再判断算式是否成立。同时需要保证填入除号时，右侧数不能为0，且乘除优先级别要高于加减。其中定义了left和right两个变量，left用于保存上一步运算结果，right用于保存下一步运算结果。
我的代码是：

#include <stdio.h>
int main()
{
int j,i[5]; //循环变量 ，数组i用来表示4个运算符
int sign;//累加运算时的符号
int result=24;
int count=0;
int num[5]; //保存操作数
float left,right; //保存中间结果
char oper[5]={' ','+','-','*','/'}; //运算符
printf("请输入4个数：");
for(j=1;j<=4;j++)
scanf("%d",&num[j]);
for(i[1]=1;i[1]<=4;i[1]++)//循环4种运算符，1表示+，2表示-,3表示*，4表示/
{
if((i[1]<4) || (num[2]!=0))//运算符若是/,则第二个运算数不能为0
{
for(i[2]=1;i[2]<=4;i[2]++)
{
if((i[2]<4) || (num[3]!=0))
{
for(i[3]=1;i[3]<=4;i[3]++)
{
if((i[3]<4) || num[4]!=0)
{

left=0;
right=num[1];
sign=1;
for(j=1;j<=3;j++)
{
switch(oper[i[j]])
{
case '+':
left=left+sign*right;
sign=1;
right=num[j+1];
break;
case '-':
left=left+sign*right;
sign=-1;
right=num[j+1];
break;
case '*':
right=right*num[j+1];
break;
case '/':
right=right/num[j+1];
break;
}
}
if(left+sign*right==result)
{
count++;
printf("%3d：",count);
for(j=1;j<=3;j++)
printf("%d%c",num[j],oper[i[j]]);
printf("%d=%dn",num[4],result);
}
}
}
}
}
}

}
if(count==0)
printf("没有符合要求的方法！n");
getch();
return 0;
}

若输入 13 13 6 4
则答案如图：

Answer 2

http://blog.csdn.net/hackbuteer1/article/details/6712385
最直接的想法就是采用穷举法，因为运算符号只有4种，每个数字只能使用一次，所以通过穷举4个数所有可能的表达式，并分别计算出各表达式的值，就可以得到答案。那么如何穷举所有可能的表达式呢？

先不考虑使用括号，可以做出如下分析：

每个数只能使用一次，对4个整数进行全排列，总共有4!=4321=24中排列。4个数的四则运算中总共需要3个运算符，同一运算符可以重复出现，那么对于每一个排列，总共可有444中表达式。因此在不考虑括号的情况下，总共可以得到4!444=1536中表达式。

接下来再考虑加上括号后的情况，对于4个数而言，总共会有以下5种加括号的方式：

(A(B(CD)))、(A((BC)D))、((AB)(CD))、((A(BC))D)、(((AB)C)D)。

所以需要遍历的表达式数最多有4!4445=7680种。即使采用逆波兰表达式，其总数也不变。

通过上面的分析，得到了一种解24点的基本思路，即遍历运算符、数字和括号的所有排列组合形式，接下来，我们将更加细致地讨论这种解法的一个具体实现。

假设给定的4个数组成的集合为A={1,2,3,4}，定义函数f(A)为对集合A中的元素进行所有可能的四则混合运算所得到的值。

首先从集合A中任意取出两个数，如取出1和2，A=A-{1,2}，对取出来的数分别进行不同的四则运算，1+2=3,1-2=-1,1/2=0.5,1*2=2，将得到的结果再分别加入集合A，可得到B={3,3,4}，C={-1,3,4}，D={0.5,3,4}，E={2,3,4}四个新的集合，那么f(A)= f(B)+f(C)+f(D)+f(E)，通过以上的计算就达到了分而治之的目的，问题规模就从4个数降到了3个数，成了3个数的4个子问题之和。综上所述，可以得到递归解法如下：

将给定的4个数放入数组Array中，将其作为参数传入函数f中，伪代码如下所示：

f(Array)
{
if(Array.Length < 2)
{
if(得到的最终结果为)
输出表达式
else 输出无法构造符合要求的表达式
}
foreach(从数组中任取两个数的组合)
{
foreach(运算符(+, -, *, /))
{
1、计算该组合在此运算符下的结果
2、将该组合中的两个数从原数组中移除，并将步骤的计算结果放入数组
3、对新数组递归调用f。如果找到一个表达式则返回
4、将步骤的计算结果移除，并将该组合中的两个数重新放回数组中对应的位置
}
}
}

具体代码如下所示：

 #include "iostream"
#include "cmath"
#include "string"
using namespace std;

const double Threshold = 1E-6; //容差值
const int CardsNumber = 4;
const int ResultValue = 24;
double number[CardsNumber]; //输入的4个整数
string result[CardsNumber]; //保存表达式

bool PointsGame(int n)
{
if(n == 1)
{
//由于浮点数运算会有精度误差，所以用一个很小的数1E-6来做容差值
if(fabs(number[0] - ResultValue) < Threshold)
{
cout << result[0] << " == 24" << endl;
return true;
}
else
{
return false;
}
}
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++) //从数组中任取两个数的组合
{
double a, b;
string expa, expb;

a = number[i];
b = number[j];
number[j] = number[n-1]; //任取两个数并将其结果放入数组后，原数组的个数减少一个

expa = result[i]; //保存表达式中的数字
expb = result[j];
result[j] = result[n-1];

result[i] = '(' + expa + '+' + expb + ')'; //任取的两个数在“+”运算符下的结果
number[i] = a + b; //将该运算符下的运算结果放入数组中
if(PointsGame(n - 1))
return true;

result[i] = '(' + expa + '-' + expb + ')'; //任取的两个数在“-”运算符下的结果
number[i] = a - b;
if(PointsGame(n - 1))
return true;

result[i] = '(' + expb + '-' + expa + ')'; //任取的两个数在“-”运算符下的结果
number[i] = b - a;
if(PointsGame(n - 1))
return true;

result[i] = '(' + expa + '*' + expb + ')'; //任取的两个数在“*”运算符下的结果
number[i] = a * b;
if(PointsGame(n - 1))
return true;
if(b != 0)
{
result[i] = '(' + expa + '/' + expb + ')'; //任取的两个数在“/”运算符下的结果
number[i] = a / b;
if(PointsGame(n - 1))
return true;
}
if(a != 0)
{
result[i] = '(' + expb + '/' + expa + ')'; //任取的两个数在“/”运算符下的结果
number[i] = b / a;
if(PointsGame(n - 1))
return true;
}
number[i] = a; //将刚开始任取的两个数重新放回数组中对应的位置
number[j] = b;
result[i] = expa;
result[j] = expb;
}
}
return false;
}

int main(void)
{
int i,x;
for(i = 0; i < CardsNumber; i++)
{
char buffer[20];
cout << "Please input the " << i+1 << "th number:";
cin >> x;
number[i] = x; //保存输入的4个整数的浮点型数组
itoa(x, buffer, 10); //把输入的4个整数按10进制转化为字符串
result[i] = buffer;
}
if(PointsGame(CardsNumber) )
{
cout << "Success." << endl;
}
else
{
cout << "Fail." << endl;
}
system("pause");
return 0;
}