a24.cpp

计算24点的C++源码

#include <iostream> 
#include <vector> 
#include <cmath> 
#include <algorithm> 

using namespace std; 

const double epsilon = 1E-14; 
const double destination = 24; 

const double CARD_VALUE_MIN = 1; 
const double CARD_VALUE_MAX = 13; 

const char symbol_array[] = {'+','-','*','/'}; 

double max(const double a,const double b); 
bool approx_equal(const double a,const double b); 
double calc_each(const double a,const double b,const int method); 

void insert_element(vector<double> &v,const int pos,const double value); 
bool print_formule(const vector<double> &v,const int formule_id,const int symb_a, 
const int symb_b,const int symb_c); 

void calc_elements(const vector<double> &v); 
void calc_permutation(vector<double> queue,vector<double> to_permute); //只有对于没有重复的数组才能产生正确的全排列 
void calc_permutation_standard(vector<double> queue); 

int rcount = 0; 

int main(int argc,char *argv[]) 
{ 
	if(argc < 5) 
	{ 
		cout << "Calc point 24 verstion 0.1" << endl; 
		cout << "Usage: " << argv[0] << " <card1> <card2> <card3> <card4> " << endl; 
		return 1; 
	} 
	else 
	{ 
		vector<double> card(4); 
		vector<double> helper(1); 

		for(int i = 0; i < 4; i++) 
		{ 
			card[i] = atof(argv[i+1]); 
			if(card[i] < CARD_VALUE_MIN || card[i] > CARD_VALUE_MAX) 
			{ 
				cout << "Invailed value of card!" << endl; 
				return 1; 
			} 
		} 
	
		/*if(card[0] == card[1] && card[0] == card[2] && card[0] == card[3]) 
			calc_elements(card); 
		else 
		{ 
			calc_elements(card); 
			calc_permutation(card,helper); 
		}*/ 
	
		calc_permutation_standard(card); 
		cout << "The total result is " << rcount << endl; 
	} 
	
	return 0; 
} 
	
double max(const double a,const double b) 
{ 
	return a > b ? a : b; 
} 
	
bool approx_equal(const double a,const double b) 
{ 
	if(a == 0) return fabs(b) <= epsilon; 
	if(b == 0) return fabs(a) <= epsilon; 
	
	return fabs(a - b) / max(fabs(a),fabs(b)) <= epsilon; 
} 
	
double calc_each(const double a,const double b,const int method) 
{ 
	if(method == 0) return a + b; 
	if(method == 1) return a - b; 
	if(method == 2) return a * b; 
	if(method == 3 && b != 0) return a / b; 
	return -999; 
} 

void insert_element(vector<double> &v,const int pos,const double value) 
{ 
	v.push_back(0); 
	for(int i = v.size() - 2; i >= pos; i--) 
	v[i+1] = v[i]; 
	v[pos] = value; 
} 

bool print_formule(const vector<double> &v,const int formule_id,const int symb_a, const int symb_b,const int symb_c) 
{ 
	double r1,r2,result = 0; 

	if(formule_id == 0) 
	{ 
		r1 = calc_each(v[0],v[1],symb_a); 
		if(approx_equal(r1,-999)) return false; 
		r2 = calc_each(r1,v[2],symb_b); 
		if(approx_equal(r2,-999)) return false; 
		result = calc_each(r2,v[3],symb_c); 
	} 
	else if(formule_id == 1) 
	{ 
		r1 = calc_each(v[0],v[1],symb_a); 
		if(approx_equal(r1,-999)) return false; 
		r2 = calc_each(v[2],v[3],symb_b);	//symb_c); 
		if(approx_equal(r2,-999)) return false; 
		result = calc_each(r1,r2,symb_c);	//symb_b); 
	} 
	else if(formule_id == 2) 
	{ 
		r1 = calc_each(v[1],v[2],symb_a);	//symb_b); 
		if(approx_equal(r1,-999)) return false; 
		r2 = calc_each(v[0],r1,symb_b);	//symb_a); 
		if(approx_equal(r2,-999)) return false; 
		result = calc_each(r2,v[3],symb_c); 
	} 
	else if(formule_id == 3) 
	{ 
		r1 = calc_each(v[1],v[2],symb_a);//symb_b); 
		if(approx_equal(r1,-999)) return false; 
		r2 = calc_each(r1,v[3],symb_b);//symb_c); 
		if(approx_equal(r2,-999)) return false; 
		result = calc_each(v[0],r2,symb_c);//symb_a); 
	} 
	else if(formule_id == 4) 
	{ 
		r1 = calc_each(v[2],v[3],symb_a);//symb_c); 
		if(approx_equal(r1,-999)) return false; 
		r2 = calc_each(v[1],r1,symb_b);//symb_b); 
		if(approx_equal(r2,-999)) return false; 
		result = calc_each(v[0],r2,symb_c);//symb_a); 
	} 
	
	if(approx_equal(result,-999)) return false; 
	
	if(approx_equal(result,destination)) 
	{ 
		if(formule_id == 0) 
		{ 
			cout << "((" << v[0] << symbol_array[symb_a] << v[1] << ")" << symbol_array[symb_b]	<< v[2] << ")" << symbol_array[symb_c] << v[3] << "=" << destination << endl; 
			return true; 
		} 
		else if(formule_id == 1) 
		{ 
			cout << "(" << v[0] << symbol_array[symb_a] << v[1] << ")" << symbol_array[symb_b] << "(" << v[2] << symbol_array[symb_c] << v[3] << ")=" << destination << endl; 
			return true; 
		} 
		else if(formule_id == 2) 
		{ 
			cout << "(" << v[0] << symbol_array[symb_a] << "(" << v[1] << symbol_array[symb_b] << v[2] << "))" << symbol_array[symb_c] << v[3] << "=" << destination << endl; 
			return true; 
		} 
		else if(formule_id == 3) 
		{ 
			cout << v[0] << symbol_array[symb_a] << "((" << v[1] << symbol_array[symb_b] << v[2] << ")" << symbol_array[symb_c] << v[3] << ")=" << destination << endl; 
			return true; 
		} 
		else if(formule_id == 4) 
		{ 
			cout << v[0] << symbol_array[symb_a] << "(" << v[1] << symbol_array[symb_b] << "(" << v[2] << symbol_array[symb_c] << v[3] << "))=" << destination << endl; 
			return true; 
		} 
	} 
	
	return false; 
} 

void calc_elements(const vector<double> &v) 
{ 
	int i,j,k,l; 
	for(l = 0; l < 5; l++) 
	{ 
		for(i = 0; i < 4; i++) 
		{ 
			for(j = 0; j < 4; j++) 
			{ 
				for(k = 0; k < 4; k++) 
				{ 
					if(print_formule(v,l,i,j,k)) 
					{ 
						rcount++; 
					} 
				} 
			} 
		} 
	} 
} 

void calc_permutation(vector<double> queue,vector<double> to_permute) 
{ 
	if(queue.size() == 0) 
	{ 
		to_permute.pop_back(); 
		calc_elements(to_permute); 
	} 
	else 
	{ 
		vector<double> mir_queue = queue; 
		vector<double> mir_to_permute = to_permute; 
		vector<double> bak_vector; 
		
		double back_value = mir_queue[mir_queue.size() - 1]; 
		
		mir_queue.pop_back(); 
		
		for(int i = 0; i < mir_to_permute.size(); i++) 
		{ 
			bak_vector = mir_to_permute; 
			insert_element(mir_to_permute,i,back_value); 
			calc_permutation(mir_queue,mir_to_permute); 
			mir_to_permute = bak_vector; 
		} 
	} 
} 

void calc_permutation_standard(vector<double> queue) 
{ 
	sort(queue.begin(),queue.end()); 
	calc_elements(queue); 

	while(next_permutation(queue.begin(),queue.end())) 
	{ 
		calc_elements(queue); 
	} 
}