算24算法实现

 

1、 概述

      给定4个整数，其中每个数字只能使用一次；任意使用 + - * / ( ) ，构造出一个表达式，使得最终结果为24，这就是常见的算24点的游戏。这方面的程序很多，一般都是穷举求解。本文介绍一种典型的算24点的程序算法，并 给出两个具体的算24点的程序：一个是面向过程的C实现，一个是面向对象的java实现。

2、基本原理

      基本原理是穷举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 则恢复数组，以确保当前递归调用获得下一个正确的排列。

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

 

3、面向过程的C实现

      这是 csdn 算法论坛前版主海星的代码，程序非常简练、精致：(由busycai注释)

 

/*****
*
*算 24点（包括小数）
*输出计算过程
*
*****/
#include <iostream>
#include <string>
#include <cmath>
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 Search(int n)
{
    /*n==1表示一次计算结束，number[0]中即为计算的结果*/
   if (n == 1)
       { if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) 
         { /*expression[0]中保存了求解过程*/
           cout << expression[0] << 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; 
                    a = number[i];
                    b = number[j];
                    /**********************************
                     *将剩下的有效数字往前挪，
                     *由于两数计算结果保存在number[i]中，
                     *所以将数组末元素覆盖number[j]即可
                     **********************************/
                    number[j] = number[n - 1];
                    expa = expression[i]; 
                    expb = expression[j];
                    expression[j] = expression[n - 1];
                    /*计算a+b*/
                    expression[i] = '(' + expa + '+' + expb + ')'; 
                    number[i] = a + b; 
                    if ( Search(n - 1) ) return true;
                    /*计算a-b*/
                    expression[i] = '(' + expa + '-' + expb + ')'; 
                    number[i] = a - b; 
                    if ( Search(n - 1) ) return true;
                    /*计算b-a*/
                    expression[i] = '(' + expb + '-' + expa + ')';
                    number[i] = b - a;
                    if ( Search(n - 1) ) return true;
                    /*计算(a*b)*/
                    expression[i] = '(' + expa + '*' + expb + ')';
                    number[i] = a * b;
                    if ( Search(n - 1) ) return true;
                    /*计算(a/b)*/
                    if (b != 0) {
                        expression[i] = '(' + expa + '/' + expb + ')';
                        number[i] = a / b;
                        if ( Search(n - 1) ) return true;
                        }
                    /*计算(b/a)*/
                        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;
           }
} 

 

使用任一个 c++ 编译器编译即可。

4、Java实现

       这里的Java实现只是本人模仿C++代码编写，面向对象的版本再进一步补充。

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class TwentyFourWithoutGUI {

	private static final int COUNT_OF_NUMBER = 4;
	private static final int NUMBER_TO_REATCH = 24;
	// 精度
	private static final double PRECISION = 1E-6;
	// 存放计算的表达式串
	private static String[] expression = new String[COUNT_OF_NUMBER];
	// 四个实数，计算24点，因为可能有小数
	private static double[] number = new double[COUNT_OF_NUMBER];

	static boolean searchResult(int n) {
		// 递归结束条件
		if (n == 1)
			return (Math.abs(number[0] - NUMBER_TO_REATCH) < PRECISION);

		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) { // 进行组合
				double opNumber1 = number[i]; // 保存起来，在方法最后再恢复，以便继续计算
				double opNumber2 = number[j]; // 保存起来，在方法最后再恢复，以便继续计算
				number[j] = number[n - 1]; // 将最后一个数挪过来
				String exp1 = expression[i]; // 保存起来，在方法最后再恢复，以便继续计算
				String exp2 = expression[j]; // 保存起来，在方法最后再恢复，以便继续计算
				expression[j] = expression[n - 1]; // 将最后一个式子挪过来
				expression[i] = "(" + exp1 + " + " + exp2 + ")"; // 看看加法能否算出
				// 将运算结果放在number[i]中
				number[i] = opNumber1 + opNumber2;
				if (searchResult(n - 1))
					return true;
				expression[i] = "(" + exp1 + " - " + exp2 + ")"; // 看看减法能否算
				number[i] = opNumber1 - opNumber2;
				if (searchResult(n - 1))
					return true;
				expression[i] = "(" + exp2 + " - " + exp1 + ")";
				number[i] = opNumber2 - opNumber1;
				if (searchResult(n - 1))
					return true;
				expression[i] = "(" + exp1 + " * " + exp2 + ")"; // 看看乘法能否算
				number[i] = opNumber1 * opNumber2;
				if (searchResult(n - 1))
					return true;
				if (opNumber2 != 0) {
					expression[i] = "(" + exp1 + " / " + exp2 + ")"; // 看看除法能否算
					number[i] = opNumber1 / opNumber2;
					if (searchResult(n - 1))
						return true;
				}
				if (opNumber1 != 0) {
					expression[i] = "(" + exp2 + " / " + exp1 + ")";
					number[i] = opNumber2 / opNumber1;
					if (searchResult(n - 1))
						return true;
				}
				number[i] = opNumber1; // 恢复
				number[j] = opNumber2;
				expression[i] = exp1;
				expression[j] = exp2;
			}
		}
		return false;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		String oneLine = reader.readLine();
		String[] nums = oneLine.split(" ");
		
		// 仅仅是演示，确保输入4个不为0的正整数
		for (int i = 0; i < COUNT_OF_NUMBER; i++) {
			number[i] = Integer.parseInt(nums[i]);
			expression[i] = nums[i];
		}
		searchResult(COUNT_OF_NUMBER);
		System.out.println(expression[0]);
	}
}

 注意：main方法中的代码并未对输入异常等进行处理，仅仅是演示。

 

 

评论

1 楼 fy616508150 2010-08-14  

我想知道有括号参加运算怎么办