关于24点算法的思想和代码实现

http://chimf.bloghome.cn/posts/49570.html

先简单介绍一下24点游戏：
给出4个1-9之间的自然数，其中每个数字只能使用一次；任意使用 + - * / ( ) ，构造出一个表达式，使得最终结果为24，这就是常见的算24点的游戏。比如两道比较经典的题目：1，5，5，5和3，3，8，8，先自己试试，答案贴在文章最后^_^

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

解决这个问题一般使用穷举法，即穷举4个整数所有可能的表达式，然后对表达式求值。下面的两种思路（三种算法）均是基于穷举法，各有优劣。

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

第一种算法：
(1) 将4个整数放入数组中，
(2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列，
(2.1) 对 + - * / 每一个运算符，
(2.1.1) 根据此排列的两个数字和运算符，计算结果，
(2.1.2) 改表数组：将此排列的两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中，
(2.1.3) 对新的数组，重复步骤 2，
(2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉。

可以看出，步骤2是一个递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。

这个是程序代码，源代码为csdn 算法论坛前版主海星所作，我修改了部分变量。此程序只能求出第一个解，无法求出全解。

引用内容：（略有修改，VC++ 2005下测试）

#include<iostream>  
#include<string>  
#include<cmath>
using namespace std;
const double PRECISION = 1E-6;
const int COUNT = 4;
const int RESULT = 24;
double number[COUNT];        //这里一定要用double,看看第一题的答案就知道为什么了    
string expression[COUNT];    //保存表达式
bool Test(int n){
	//递归结束
	if(1 == n){
		if(fabs(number[0]-RESULT)<PRECISION){
			// 避免输出前后括号
			for (int i = 1; i < expression[0].length() - 1; i++)
			{
				cout<<expression[0][i];
			}
			cout<<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]填补
			number[j]=number[n-1];
			expa=expression[i];
			expb=expression[j];
			// 删除expression[j]元素，用expression[n-1]填补
			expression[j]=expression[n-1];
			
			// 加法
			expression[i]='(' + expa + '+' + expb + ')';
			number[i]=a+b;
			if(Test(n-1))
				return true;
			//减号有两种情况,a-b与b-a
			expression[i]='('+expa+'-'+expb+')';
			number[i]=a-b;
			if(Test(n-1))
				return true;
			expression[i]='('+expb+'-'+expa+')';
			number[i]=b-a;
			if(Test(n-1))
				return true;
			// 乘法
			expression[i]='('+expa+'*'+expb+')';
			number[i]=a*b;
			if(Test(n-1))
				return true;
			//除法也有两种情况,a/b与b/a
			if(b!=0){
				expression[i]='('+expa+'/'+expb+')';
				number[i]=a/b;
				if(Test(n-1))
					return true;
			}
			if(a!=0){
				expression[i]='('+expb+'/'+expa+')';
				number[i]=b/a;
				if(Test(n-1))
					return true;
			}
			//恢复数组
			number[i]=a;
			number[j]=b;
			expression[i]=expa;
			expression[j]=expb;
		}
	}
	return false;
}
void main(void){
	for(int i=0;i<COUNT;i++){
		char buffer[20];
		int x;
		cin >> x;
		number[i]=x;
		_itoa_s(x,buffer,10);
		expression[i]=buffer;
	}
	if(Test(COUNT))
		cout << "Success" << endl;
	else
		cout << "Fail" << endl;
}

附：

(5-(1/5))*5 = 24

8/(3-(8/3)) = 24

秒客网

关于24点算法的思想和代码实现

相关文章