算24点程序:面向过程与面向对象的C++
1.概观
给定4个整数,每个数只能用一次;用any+-*/()构造一个表达式,使最终结果为24,这是常见的算24分的游戏。这方面的方案很多,一般都是面面俱到的。介绍了一个计算24分的典型程序算法,给出了两个计算24分的具体程序:一个是面向过程的C实现,一个是面向对象的Java实现。
2.基本原则
基本原理是枚举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)
0条评论