平行的宇宙,折射的生命

放手去爱

  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  3 随笔 :: 2 文章 :: 3 评论 :: 0 Trackbacks
给定4个整 数,其中每个数字只能使用一次;任意使用 + - * / ( ) ,构造出一个表达式,使得最终结果为24,这就是常见的算24点的游戏。这方面的程序很多,一般都是穷举求解。本文介绍一种典型的算24点的程序算法,并 给出两个具体的算24点的程序:一个是面向过程的C实现,一个是面向对象的java实现。

基本原理是穷举4个整数所有可能的表达式,然后对表达式求值。

表达式的定义: expression = (expression|number) operator (expression|number)

因为能使用的4种运算符 + - * / 都是2元运算符,所以本文中只考虑2元运算符。2元运算符接收两个参数,输出计算结果,输出的结果参与后续的计算。

由上所述,构造所有可能的表达式的算法如下:

(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列,共有 P(4,2) 种排列。对每一个排列,
(2.1) 对 + - * / 每一个运算符,
(2.1.1) 根据此排列的两个数字和运算符,计算结果
(2.1.2) 改表数组:将此排列的两个数字从数组中去除掉,将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组,重复步骤 2
(2.1.4) 恢复数组:将此排列的两个数字加入数组中,将 2.1.1 计算的结果从数组中去除掉

可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候,这就是表达式的最终结果,此时递归结束。

在程序中,一定要注意递归的现场保护和恢复,也就是递归调用之前与之后,现场状态应该保持一致。在上述算法中,递归现场就是指数组,2.1.2 改变数组以进行下一层递归调用,2.1.3 则恢复数组,以确保当前递归调用获得下一个正确的排列。

括号 () 的作用只是改变运算符的优先级,也就是运算符的计算顺序。所以在以上算法中,无需考虑括号。括号只是在输出时需加以考虑。

#include <iostream>
#include <string>
#include <cmath>

#
using <System.dll>
#
using <System.Configuration.Install.dll>


using namespace std;
using namespace System;
using namespace System::Diagnostics;


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 Search(int n)
{
if (n == 1) {
if ( fabs(number[0- NUMBER_TO_BE_CAL) < PRECISION ) {
cout 
<< expression[0<<" = 24"<< endl;
return true;
else {
return false;
}
}

for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
double a, b;
string expa, expb;


= number[i];
= number[j];
number[j] 
= number[n - 1];

expa 
= expression[i];
expb 
= expression[j];
expression[j] 
= expression[n - 1];

expression[i] 
= '(' + expa + '+' + expb + ')';
number[i] 
= a + b;
if ( Search(n - 1) ) return true;

expression[i] 
= '(' + expa + '-' + expb + ')';
number[i] 
= a - b;
if ( Search(n - 1) ) return true;

expression[i] 
= '(' + expb + '-' + expa + ')';
number[i] 
= b - a;
if ( Search(n - 1) ) return true;


expression[i] 
= '(' + expa + '*' + expb + ')';
number[i] 
= a * b;
if ( Search(n - 1) ) return true;

if (b != 0) {
expression[i] 
= '(' + expa + '/' + expb + ')';
number[i] 
= a / b;
if ( Search(n - 1) ) return true;
}
if (a != 0) {
expression[i] 
= '(' + expb + '/' + expa + ')';
number[i] 
= b / a;
if ( Search(n - 1) ) return true;
}

number[i] 
= a;
number[j] 
= b;
expression[i] 
= expa;
expression[j] 
= expb;
}
}
return false;
}

void main()
{
for (int i = 0; i < COUNT_OF_NUMBER; i++) {
char buffer[20];
int x;
cin 
>> x;
number[i] 
= x;
itoa(x, buffer, 
10);
expression[i] 
= buffer;
}

if ( Search(COUNT_OF_NUMBER) ) {
cout 
<< "Success." << endl;
else {
cout 
<< "Fail." << endl;
}
}



posted on 2009-01-06 15:04 DeEpBLuE222 阅读(1775) 评论(3)  编辑  收藏

评论

# re: 算24点 算法整理和原理说明 2010-03-30 19:47 万二村
怎么没有java的代码  回复  更多评论
  

# re: 算24点 算法整理和原理说明 2010-05-10 13:28 抒寒
取2个数字有6种,运算有6种(减法和除法是有顺序的),第二次取有3种,运算有6种,第三次取有1种,运算有6种,所以一共有6*6*3*6*1*6=3888个表达式,对吗?  回复  更多评论
  

# re: 算24点 算法整理和原理说明[未登录] 2010-05-25 13:36 Blue
@万二村
java 代码很容易改写的吧  回复  更多评论
  


只有注册用户登录后才能发表评论。


网站导航: