24点算法

 

#include <iostream>
#include <vector>
#include <math.h>

//c1:	(((A,B),C),D)
//c2:	((A,B),(C,D))

std::vector< std::vector<double> > permutaionSet;

void swap(double* left, double* right){
	double temp;
	temp = *left;
	*left = *right;
	*right = temp;
}

int  permutaion(double *input,int depth, int len){

	if(depth > len){
		std::cout << "input error!" << std::endl;
		return -1;
	}

	if(depth == len){
		std::vector<double> temp(input,input+len);
		permutaionSet.push_back(temp);
		return permutaionSet.size();
	}

	for(int i=depth; i<len; i++){
		swap(input+depth,input+i);
		permutaion(input,depth+1,len);
		swap(input+depth,input+i);
	}
	return -2;
}

char op[] = {'+', '-', '*', '/'};
double calculator(double left, double right, char op){
	switch (op)
	{
	case '+':
		return left+right;
	case '-':
		return left-right;
	case '*':
		return left*right;
	case '/':
		return left/right;
	default:
		return 0;
	}
}

//c1:	(((A,B),C),D)
double operatoration(int first_op, int second_op, int third_op,std::vector<double>& numbers){
	return calculator(
				calculator(
					calculator(numbers[0],numbers[1],op[first_op]),
						numbers[2],op[second_op]),
							numbers[3],op[third_op]);
}

//c2:	((A,B),(C,D))
double operatoration2(int first_op, int second_op, int third_op,std::vector<double>& numbers){
	return calculator(
		calculator(numbers[0],numbers[1],op[first_op]),
		calculator(numbers[2],numbers[3],op[third_op]),
		op[second_op]);
}

#define EPSSLON 0.000001

bool judge(const int itorator){

	std::vector<double> temp(permutaionSet[itorator]);
	for(int i=0; i<4; i++)
		for(int j=0; j<4; j++)
			for(int k=0; k<4; k++)
				if(		(fabs(24-operatoration(i,j,k,temp)) <= EPSSLON ) 
						|| (fabs(24-operatoration2(i,j,k,temp)) <= EPSSLON )	)
					return true;
	return false;
}

bool Game24Points(int a, int b, int c, int d){
	double input[4];
	double *ptr = input;
	*ptr++ = a, *ptr++ = b, *ptr++ = c, *ptr++ = d;
	permutaionSet.clear();
	permutaion(input,0,4);

	for(size_t i=0; i<permutaionSet.size(); i++)
		if(judge(i))
			return true;
	return false;
}


int _tmain(int argc, _TCHAR* argv[]){
	

	std::cout << Game24Points(7,7,7,7) << " "<< Game24Points(1,2,3,4) << " " << Game24Points(7,2,1,10);

	system("pause");
	return 0;
}

 算法的思想是：

 

24点算法是4个数字之间通过,加、减、乘、除、括号使得最终的结果为24.

先将4个数字进行一次全排列，这个全排列包括了4个数字的所有出现顺序。

选择一种排列，对这4个数字进行括号操作，总共有一下两种括号操作形式：

//c1:    (((A,B),C),D)
//c2:    ((A,B),(C,D))最后将上面两个式子中加上运算符（式子中逗号的位置换上运算符），判断结果是否为24