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

本文实例为大家分享了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;　
　　　 }　　　　　　　　　
}

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