趣味编程：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;
		}
	}
}

评论

5 楼 zeeeitch 2009-01-09  

偶以前写的，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);
}
}

4 楼 zeeeitch 2009-01-09  

穷举法，能否优化一下？

3 楼 qdzheng 2009-01-09  

plisking 写道

我有一点不太明白，题目的条件是“任取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这个合法的组合就不在其中。

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

2 楼 plisking 2009-01-09  

我有一点不太明白，题目的条件是“任取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这个合法的组合就不在其中。

1 楼 xypro 2009-01-09  

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