现在的位置: 首页 > 编程语言 > 正文

C语言实现经典24点算法

2020年02月13日 编程语言 ⁄ 共 3830字 ⁄ 字号 评论关闭

本文实例为大家分享了C语言经典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 算法论坛前版主海星的代码,程序非常简练、精致:

#include  #include  #include  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) {     if (n == 1) {         if ( fabs(number[0] - NUMBER_TO_BE_CAL) < PRECISION ) {             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[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;     }         }

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

  这个程序的算法与 2、基本原理所述的算法基本相同。其中 bool Search(int n) 就是递归函数,double number[] 就是数组。程序中比较重要的地方解释如下:

  (1) string expression[] 存放每一步产生的表达式,最后的输出中要用到。expression[] 与 number[] 类似,也是递归调用的现场,必须在下一层递归调用前改变、在下一层递归调用后恢复。

  (2) number[] 数组长度只有4。在 search() 中,每次取出两个数后,使用局部变量 a, b 保存这两个数,同时数组中加入运算结果,并调整数组使得有效的数字都排列在数组前面。在下一层递归调用后,利用局部变量 a, b 恢复整个数组。对 expression[] 的处理与 number[] 类似。

  (3) 因为 + * 满足交换率而 - / 不满足,所以程序中,从数组生成两个数的排列,

  for (int i = 0; i < n; i++) {

  for (int j = i + 1; j < n; j++) {

  其内层循环 j 是从 i+1 -> n,而非从 0->n ,因为对于交换率来说,两个数字的顺序是无所谓的。当然,循环内部对 - / 做了特殊处理,计算了 a-b b-a a/b b/a 四种情况。

  (4) 此程序只求出第一个解。当求出第一个解时,通过层层 return true 返回并输出结果,然后程序结束。

  (5) 以 double 来进行求解,定义精度,用以判断是否为 24 。考虑 (5-1/5)*5 这个表达式就知道这么做的原因了。

  (6) 输出时,为每个表达式都添加了括号。

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

本文标题: C语言实现经典24点算法

以上就上有关C语言实现经典24点算法的相关介绍,要了解更多C语言,24点算法内容请登录学步园。

抱歉!评论已关闭.