C语言实现经典24点算法-创新互联

本文实例为大家分享了C语言经典24点算法的具体实现代码,供大家参考,具体内容如下

创新互联公司主营长洲网站建设的网络公司,主营网站建设方案,成都app软件开发,长洲h5重庆小程序开发公司搭建,长洲网站营销推广欢迎长洲等地区企业咨询

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; 
    }         
}

另外有需要云服务器可以了解下创新互联建站www.cdcxhl.com,海内外云服务器15元起步,三天无理由+7*72小时售后在线,公司持有idc许可证,提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案,具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势,专为企业上云打造定制,能够满足用户丰富、多元化的应用场景需求。


分享文章:C语言实现经典24点算法-创新互联
文章来源:http://myzitong.com/article/phedg.html