趣味编程：24点算法实现

24点游戏规则：任取1－9之间的4个数字，用＋－＊／（）连结成算式，使得式子的计算结果为24。估计很多人都玩过用扑克牌玩的那种，印象中10也算在内的，两人各出2张牌，谁先算出来谁赢，赢家收回已经算过的4张牌。最后看谁手里的牌多。
这个程序实现使用穷举的方法，将所有可能的排列穷举出来，最后将每个排列中计算出结果。计算结果时，将前两个作为一组、后两个数作为一组，分别计算出各组的结果，再对获得的两个组结果进行计算。由于是排列，分前后两组进行计算就可满足所有可能的计算。

改进后的代码见回复中。

package fun.twentyfour;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class TwentyFour {
	public static void main(String[] args){
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String line;
		try{
			while((line=br.readLine())!=null){
				try{
					if ("exit".equals(line)) break;
					
					String[] s=line.split("\\s");
					int[] v=new int[4];
					for(int idx=0;idx<4;idx++) {
						v[idx]=Integer.parseInt(s[idx]);
						if (v[idx]<=0||v[idx]>=10) throw new Exception("Input error.");
					}
					evaluate(v);
					
				}catch(Exception ex){
					ex.printStackTrace();
				}
			}
		}catch(Exception ex){
			ex.printStackTrace();
		}
	}
	
	public static void evaluate(int[] v){
		int idx=0;
		for(int a=0;a<4;a++)
			for(int b=0;b<4;b++)
				for (int c=0;c<4;c++)
					for (int d=0;d<4;d++){
					if (a!=b && a!=c && a!=d && b!=c && b!=d && c!=d){
						idx++;
						check(v,new int[]{a,b,c,d});
					}
				}
	}
	static char[] op={'+','-','*','/'};
	public static void check(int[] v,int[] idx){
		
		for(int o=0;o<4;o++){
			for(int p=0;p<4;p++){
				for(int t=0;t<4;t++){
					if (op(op[p],op(op[o],v[idx[0]],v[idx[1]]),op(op[t],v[idx[2]],v[idx[3]]))==24){
						System.out.println(String.format("(%1$d %2$c %3$d) %4$c (%5$d %6$c %7$d)",
								v[idx[0]],op[o],v[idx[1]],op[p],v[idx[2]],op[t],v[idx[3]]));
					}
				}
			}
		}
	}

	public static int op(char op,int v1,int v2){
		switch(op){
		case '+':
			return v1+v2;
		case '-':
			return v1-v2;
		case '*':
			return v1*v2;
		case '/':
			if (v2==0) return -111;
			if (v1%v2!=0) return -111;
			return v1/v2;
		default:
				return 0;
		}
	}
}

如果保证算术符号只用一次 算法就会麻烦很多了

我有一点不太明白，题目的条件是“任取1－9之间的4个数字，用＋－＊／（）连结成算式”，为什么楼主要把数字分成两组？？这不就改了条件吗？而且这样一来，运算的优先级以及最终算式的格式就被固定下来了，难度也就大幅降低了。但是会有算式被漏算掉的情况。
比如取四个数为：3 6 1 9，你的程序结果：
(3 - 6) * (1 - 9)
(6 - 3) * (9 - 1)
(1 - 9) * (3 - 6)
(9 - 1) * (6 - 3)
但是很显然，3*(6-1)+9这个合法的组合就不在其中。

你说得正确，这个算法是有问题的。回头改正。

穷举法，能否优化一下？

偶以前写的，c++。翻出来共享一下。好像也是穷举啊，考虑了（）×（）了

#pragma once

#include "iostream"
#include<vector>
using namespace std;  

//排列生成器
//给一串数,返回各种排列
template <class T>
class ArrangeGenerator
{
public:
	ArrangeGenerator(const vector<T> & av) : current_(0)
	{
		Arranges(av, Result_);
	}

	bool haveNext()
	{
		return Result_.size() != current_;
	}

	vector<T> next()
	{
		return Result_[current_++];
	}

private:
	vector<vector<T> > Result_;
	int current_;

	void Arranges(const vector<T>& Source, vector<vector<T> >& Result)
	{
		vector<T> temp;
		vector<vector<T> > temp2;

		typedef vector<T>::const_iterator vi;
		typedef vector<vector<T> >::iterator vvi;


		Result.clear();
		if (Source.size() == 2)
		{
			temp.push_back(Source[0]);
			temp.push_back(Source[1]);
			Result.push_back(temp);

			temp.clear();
			temp.push_back(Source[1]);
			temp.push_back(Source[0]);
			Result.push_back(temp);
		}
		else
		{
			for (vi i = Source.begin(); i != Source.end(); ++i)
			{
				vector<T> temp(Source.size() - 1);

				copy(Source.begin(), i, temp.begin());
				copy(i + 1, Source.end(), temp.begin() + (i - Source.begin()));

				//递归
				Arranges(temp, temp2);

				for (vvi j = temp2.begin(); j != temp2.end(); ++j)
				{
					vector<T> temp3(Source.size());
					temp3[0] = *i;
					copy(j->begin(), j->end(), temp3.begin() + 1);
					Result.push_back(temp3);
				}
			}
		}
	}

};

class OpBase
{
public:
	virtual int operator()(int a, int b) = 0;
	virtual void out(ostream& o) = 0;
};

ostream& operator<<(ostream& o, OpBase& ob);

class Plus : public OpBase
{
public:
	virtual int operator()(int a, int b);
	virtual void out(ostream& o);
};

class Minus : public OpBase
{
public:
	virtual int operator()(int a, int b);
	virtual void out(ostream& o);
};
class Minus2 : public OpBase
{
public:
	virtual int operator()(int a, int b);
	virtual void out(ostream& o);
};

class Multi : public OpBase
{
public:
	virtual int operator()(int a, int b);
	virtual void out(ostream& o);
};

class Devide : public OpBase
{
public:
	virtual int operator()(int a, int b);
	virtual void out(ostream& o);
};
class Devide2 : public OpBase
{
public:
	virtual int operator()(int a, int b);
	virtual void out(ostream& o);
};


namespace removeMulti
{
struct rmAux
{
	int num1;
	int num2;
	int res;
};
bool operator <(const rmAux& a,const rmAux& b)
{
	return (a.num1 < b.num1) || (a.num1 >= b.num1 && a.num2 < b.num2);
}
}

#include "stdafx.h"
#include "iostream"
#include <vector>
#include <algorithm>
#include <map>
#include "point24.h"
using namespace std;

typedef map<pair<int , int > , int > Map;

bool canForm24(int num[]);


int main()
{
	Map map1;

	int n[]={3,3,8,9};
//	cout<<canForm24(n);

	for ( int i=0;i<10;++i)
	for ( int i2=0;i2<10;++i2)
	for ( int i3=0;i3<10;++i3)
	for ( int i4=0;i4<10;++i4)
	{
		n[0]=i;
		n[1]=i2;
		n[2]=i3;
		n[3]=i4;
		sort(n,n+4);
		if(canForm24(n))
		{
			map1[make_pair(n[0],n[1])] = map1[make_pair(n[0],n[1])] + 1 ;
			map1[make_pair(n[0],n[2])] = map1[make_pair(n[0],n[2])] + 1 ;
			map1[make_pair(n[0],n[3])] = map1[make_pair(n[0],n[3])] + 1 ;
			map1[make_pair(n[1],n[2])] = map1[make_pair(n[1],n[2])] + 1 ;
			map1[make_pair(n[1],n[3])] = map1[make_pair(n[1],n[3])] + 1 ;
			map1[make_pair(n[2],n[3])] = map1[make_pair(n[2],n[3])] + 1 ;
		}

	}

	Map::iterator p;
//	copy(map1.begin(),map1.end(),ostream_iterator<pair<int , int > , int  >(cout,"\n"));

	/*
	map<removeMulti::rmAux, int> rmMap;
	map<removeMulti::rmAux, int> rmMap2;
	map<removeMulti::rmAux, int> rmMap3;


	int num[4] ;
	num[0] = 0;
	while (num[0] < 10)
	{
		rmMap.clear();
		rmMap2.clear();
		rmMap3.clear();

		cin >> num[0] >> num[1] >> num[2] >> num[3];

		int arr[] =
		{
			0, 1, 2, 3
		};
		vector<int> arrange(arr, arr + 4);


		Plus p;Minus m; Multi mu; Devide d;Minus2 m2; Devide2 d2;
		OpBase* ops[] =
		{
			&p, & m, & mu, & d, & m2, & d2
		};

		int count = 0;

		ArrangeGenerator<int> ag(arrange);
		while (ag.haveNext())
		{
			arrange = ag.next();
			for (unsigned int j = 0; j < 6 * 6 * 6; ++j)
			{
				OpBase& op1 = *ops[j % 6];
				OpBase& op2 = *ops[(j / 6) % 6];
				OpBase& op3 = *ops[(j / 36) % 6];
				try
				{
					if (op3(op2(op1(num[arrange[0]], num[arrange[1]]),
								num[arrange[2]]),
							num[arrange[3]]) ==
						24)
					{
						removeMulti::rmAux rmaux =
						{
							min(num[arrange[0]], num[arrange[1]]),
							max(num[arrange[0]], num[arrange[1]]),
							op1(num[arrange[0]], num[arrange[1]])
						};

						if (rmMap[rmaux] == 0)
						{
							std::cout << "((" << num[arrange[0]] << op1
								<< num[arrange[1]] << ")" << op2
								<< num[arrange[2]] << ")" << op3
								<< num[arrange[3]] << std::endl;
							count ++;

							rmMap[rmaux] = 1;
						}
					}


					//()+()
					if (op2(op1(num[arrange[0]], num[arrange[1]]),
							op3(num[arrange[2]], num[arrange[3]])) == 24)
					{
						removeMulti::rmAux rmaux =
						{
							min(num[arrange[0]], num[arrange[1]]),
							max(num[arrange[0]], num[arrange[1]]),
							op1(num[arrange[0]], num[arrange[1]])
						};
						removeMulti::rmAux rmaux2 =
						{
							min(num[arrange[2]], num[arrange[3]]),
							max(num[arrange[2]], num[arrange[3]]),
							op3(num[arrange[2]], num[arrange[3]])
						};

						if (rmMap2[rmaux] == 0 && rmMap2[rmaux2] == 0)
						{
							std::cout << "(" << num[arrange[0]] << op1
								<< num[arrange[1]] << ")" << op2 << "("
								<< num[arrange[2]] << op3 << num[arrange[3]]
								<< ")" << std::endl;
							count ++;
							rmMap2[rmaux] = 1;
						}
					}
				}
				catch (int)
				{
				}
			}
		}

		cout << count << endl;
	};
	return 0;*/
}


/**********************************************************************************************************************************
/*********************************************************************************************************************************/

ostream& operator<<(ostream& o, OpBase& ob)
{
	ob.out(o);
	return o;
}

int Plus::operator()(int a, int b)
{
	return a + b;
}
void Plus::out(ostream& o)
{
	o << '+';
}


int Minus::operator()(int a, int b)
{
	return a - b;
}	
void Minus::out(ostream& o)
{
	o << '-';
}

int Minus2::operator()(int a, int b)
{
	return b - a;
}	
void Minus2::out(ostream& o)
{
	o << "-_";
}


int Multi::operator()(int a, int b)
{
	return a * b;
}	
void Multi::out(ostream& o)
{
	o << '*';
}


int Devide::operator()(int a, int b)
{
	if (b == 0)
		throw int(0);
	if (a % b != 0)
		throw int(0);
	return a / b;
}	
void Devide::out(ostream& o)
{
	o << '/';
}

int Devide2::operator()(int a, int b)
{
	if (a == 0)
		throw int(0);
	if (b % a != 0)
		throw int(0);
	return b / a;
}	
void Devide2::out(ostream& o)
{
	o << "/_";
}

bool canForm24(int num[])
{
			//cin >> num[0] >> num[1] >> num[2] >> num[3];

		int arr[] =
		{
			0, 1, 2, 3
		};
		vector<int> arrange(arr, arr + 4);


		Plus p;Minus m; Multi mu; Devide d;Minus2 m2; Devide2 d2;
		OpBase* ops[] =
		{
			&p, & m, & mu, & d, & m2, & d2
		};

		int count = 0;

		ArrangeGenerator<int> ag(arrange);
		while (ag.haveNext())
		{
			arrange = ag.next();
			for (unsigned int j = 0; j < 6 * 6 * 6; ++j)
			{
				OpBase& op1 = *ops[j % 6];
				OpBase& op2 = *ops[(j / 6) % 6];
				OpBase& op3 = *ops[(j / 36) % 6];
				try
				{
					if (op3(op2(op1(num[arrange[0]], num[arrange[1]]),
								num[arrange[2]]),
							num[arrange[3]]) ==
						24)
					{
						return true;
					}


					//()+()
					if (op2(op1(num[arrange[0]], num[arrange[1]]),
							op3(num[arrange[2]], num[arrange[3]])) == 24)
					{
						return true;
					}
				}
				catch (int)
				{
				}
			}
		}

		return false;

}

拿去研究一下。。。。。。

好吧，既然C++都来了，偶也就来一个Python 版本，带记忆的（不会重复搜索），带打印结果的
也是穷举，理论上支持任意长度和任意目标值的

operations = [(lambda a, b: a + b, lambda a, b: "( " + str(a) + " + " + str(b) + " )"),
			  (lambda a, b: a - b, lambda a, b: "( " + str(a) + " - " + str(b) + " )"),
			  (lambda a, b: b - a, lambda a, b: "( " + str(b) + " - " + str(a) + " )"),
			  (lambda a, b: a * b, lambda a, b: "( " + str(a) + " * " + str(b) + " )"),
			  (lambda a, b: a // b, lambda a, b: "( " + str(a) + " / " + str(b) + " )"),
			  (lambda a, b: b // a, lambda a, b: "( " + str(b) + " / " + str(a) + " )")]

targetNumber = 24
resultMap = dict()

def search(numSet):
	if len(numSet) <= 1:
		return numSet[0] == targetNumber and " " + str(targetNumber) + " " or None
	numSet.sort();
	if tuple(numSet) in resultMap:
		return resultMap[tuple(numSet)];
	
	for a in range(0, len(numSet) - 1):
		for b in range(a + 1, len(numSet)):
			for op in operations:
				try:
					newList = [n for n in numSet if n != numSet[a] and n != numSet[b]]
					newList.append(op[0](numSet[a], numSet[b]))
					res = search(newList)
					if res:
						res = res.replace(" " + str(op[0](numSet[a], numSet[b])) + " ", op[1](numSet[a], numSet[b]), 1)
						resultMap[tuple(numSet)] = res
						return res
					newList.pop()
				except ZeroDivisionError:
					pass
	resultMap[tuple(numSet)] = None
	return None

if __name__ == "__main__":
	print(search([2, 2, 2, 2]))
	print(search([3, 4, 5, 6, 7]))

改进后的24点算法，也还有缺点，未处理重复组合。使用了类似逆波兰表达式的机制（未考虑算符优先级）。
输入 3 6 1 9后输出为：

3 6 1 9

((3*(6-1))+9)
(((3-1)*9)+6)
(6+((3-1)*9))
((6-3)*(9-1))
(((6-1)*3)+9)
(6*(1+(9/3)))
(6+(9*(3-1)))
(6*((9/3)+1))
(((1+9)*3)-6)
((1+(9/3))*6)
(9+(3*(6-1)))
((9*(3-1))+6)
(((9/3)+1)*6)
(9+((6-1)*3))
(((9+1)*3)-6)
((9-1)*(6-3))

package fun.twentyfour;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Stack;

public class TwentyFour {
	public static void main(String[] args){
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		String line;
		try{
			while((line=br.readLine())!=null){
				try{
					if ("exit".equals(line)) break;
					
					String[] s=line.split("\\s");
					int[] v=new int[4];
					for(int idx=0;idx<4;idx++) {
						v[idx]=Integer.parseInt(s[idx]);
						if (v[idx]<=0||v[idx]>=10) throw new Exception("Input error.");
					}
					evaluate(v);
					
				}catch(Exception ex){
					ex.printStackTrace();
				}
			}
		}catch(Exception ex){
			ex.printStackTrace();
		}
	}
	
	public static void evaluate(int[] v){
		for(int a=0;a<4;a++)
			for(int b=0;b<4;b++){
				if (a==b) continue;
				for (int c=0;c<4;c++){
					if (a==c||b==c) continue;
					for (int d=0;d<4;d++){
						if (a==d || b==d || c==d ) continue; 
						check(v,new int[]{a,b,c,d});
					}
				}
			}
		evaluate(new int[]{v[0],v[1],v[2],v[3]},new char[]{'+','+','+'});
		evaluate(new int[]{v[0],v[1],v[2],v[3]},new char[]{'*','*','*'});
	}
	static char[] op={'+','-','*','/'};
	public static void check(int[] v,int[] idx){
		
		for(int i=0;i<4;i++){
			for(int j=0;j<4;j++){
				for(int k=0;k<4;k++){
					if (i==j && j==k) continue;
					evaluate(new int[]{v[idx[0]],v[idx[1]],v[idx[2]],v[idx[3]]},new char[]{op[i],op[j],op[k]});
				}
			}
		}
	}

	/**
	 * 计算四个数字排列与操作符的运算结果
	 * @param num  数字排列
	 * @param op  操作符排列
	 */
	public static void evaluate(int[] num,char[] op){
		MyStack stack=new MyStack();
		//要入栈的操作数个数1-4
		int dataNum=0;
		if (op[0]==op[1] && op[0]==op[2]) dataNum=num.length - 1;
		for(;dataNum<num.length;dataNum++){
			//要入栈的操作符个数1-3
			int opNum=0;
			if (dataNum+1==num.length) opNum=op.length-1;
			int maxOpNum=dataNum;
			if (dataNum==0) maxOpNum=1;
			repeat:
			for(;opNum<maxOpNum;opNum++){
				int numCount=0;
				int dataIndex=0;
				int opIndex=0;

				stack.clear();
				
				while(dataIndex<num.length || opIndex<op.length){
					//操作数入栈
					for(int i=0;dataIndex<num.length && i<dataNum+1;i++){
						stack.push(num[dataIndex]);
						dataIndex++;
						numCount++;
					}
					//操作符入栈
					for(int k=0;opIndex<op.length && k<opNum+1;k++){
						if (numCount>1){
							stack.push(op[opIndex]);
							if (stack.isStop()) break repeat;
							opIndex++;
							numCount--;
						}
					}
				}
				if ((Integer)stack.pop()==24){
					System.out.println(stack.toString());
				}
			}
		}
	}

	public static class MyStack extends Stack{
		boolean stop=false;
		Stack stack=new Stack();
		
		public String toString(){
			return getExpression();
		}
		
		public boolean isStop(){
			return stop;
		}
		public String getExpression(){
			Object v=stack.pop();
			if (v instanceof Character){
				String right=getExpression();
				String left=getExpression();
				return "("+left+v+right+")";
			}
			return v.toString();
		}
		public void clear(){
			super.clear();
			stack.clear();
                        stop=false;
		}
		
		public Object push(Object v){
			stack.push(v);
			if (v instanceof Character){
				Integer v1=(Integer)pop();
				Integer v2=(Integer)pop();
				Integer v3=0;
				switch((Character)v){
				case '+': 
					v3=v2+v1;break;
				case '-':
					v3=v2-v1;
					if (v3<0) stop=true;
					break;
				case '*':
					v3=v2*v1;break;
				case '/':
					if (v1!=0 && v2%v1==0){
						v3=v2/v1;
					}else{
						stop=true;
					}
					break;
				}
				return super.push(v3);
			}else{
				return super.push(v);
			}
			
		}
	}
}