一个算24点的程序

四 5th, 2009 | Posted by | Filed under 程序设计
发表评论 | Trackback

本文内容遵从CC版权协议, 可以随意转载, 但必须以超链接形式标明文章原始出处和作者信息及版权声明
网址: http://www.penglixun.com/tech/program/24_point_program.html

递归用好了是一种艺术，用不好是一种灾难，这个程序递归用的我觉得还挺好的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97

#include <iostream> 
#include <string> 
#include <cmath> 
#include <cstdlib>
 
using namespace std; 
 
const  double	PRECISION = 1E-6; 
const  int	COUNT_OF_NUMBER  = 4;  
const  int	NUMBER_TO_BE_CAL = 24; 
 
double	number[COUNT_OF_NUMBER]; 
string	expression[COUNT_OF_NUMBER]; 
bool	Judgement = false;	//判断是否有解。
int	count = 0;  
 
void Search(int n) 
{
	if (n==1) { 
		if (fabs(number[0] - NUMBER_TO_BE_CAL) <= PRECISION) {	//对于除法，要小心小数的精确位数  
			cout <<expression[0] <<"\t\t";  
			Judgement = true;
			++count;
			if((count % 3)==0)
				cout <<endl;
		} 
	} 
	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]; //递归之后，n比以前小一位，所以可以不停向前赋值  
 
			expa = expression[i]; 
			expb = expression[j]; 
			expression[j]  =  expression[n - 1]; //递归之后，n比以前小一位，所以可以不停向前赋值
 
			expression[i] = '(' + expa + '+' + expb + ')'; //加法不需要分顺序
			number[i] = a + b; 
			Search(n-1);
 
			expression[i] = '(' + expa + '-' + expb + ')'; //减法应该分顺序，减数以及被减数
			number[i] = a - b; 
			Search(n-1);  
 
			expression[i] = '(' + expb + '-' + expa + ')'; //减法应该分顺序，减数以及被减数
			number[i] = b - a; 
			Search(n-1);  
 
			expression[i] = '(' + expa + '*' + expb + ')'; //乘法不需要分顺序
			number[i] = a * b; 
			Search(n-1);  
 
			if (b != 0) { 
				expression[i] = '(' + expa + '/' + expb + ')'; //除法应该分顺序，除数以及被除数
			    number[i] = a / b; 
			    Search(n-1); 
			}   
			if (a != 0) { 
			    expression[i] = '(' + expb + '/' + expa + ')'; //除法应该分顺序，除数以及被除数
			    number[i] = b  /  a; 
			    Search(n-1); 
			} 
 
			number[i] = a;      //这4句语句是为了防止如果上面几种可能都失败了的话,
			number[j] = b;      //就把原来的赋值撤消回去,以无干扰的正确的进入到下一次
			expression[i] = expa;     //for循环队列中。
			expression[j] = expb;     
      } 
  } 
} 
 
 
int  main() 
{ 
	cout<<"输入四个数:\n";
	for (int i=0; i < COUNT_OF_NUMBER; ++i) { 
		char buffer[20];  
		cout <<"第"<<i+1<<"个数:";
		cin >>number[i];       
		itoa(number[i], buffer, 10);
		expression[i] = buffer; 
	} 
	cout <<endl;
	Search(COUNT_OF_NUMBER) ;
	if(Judgement){ 
		cout <<"\n成功" <<endl; 
		cout <<"求和方法有 " <<count <<" 种" <<endl;
	} 
	else { 
		cout << "失败" << endl; 
	}    
	return 0;
}
标签: , ,
目前还没有任何评论.

​