递归算法实例应用（五）

算24 （POJ 2787）

Description

给出4个小于10的正整数，你可以使用加减乘除4种运算以及括号把这4个数连接起来得到一个表达式。现在的问题是，是否存在一种方式使得得到的表达式的结果等于24。

这里加减乘除以及括号的运算结果和运算的优先级跟我们平常的定义一致（这里的除法定义是实数除法）。

比如，对于5，5，5，1，我们知道5 * (5 – 1 / 5) = 24，因此可以得到24。

又比如，对于1，1，4，2，我们怎么都不能得到24。

Input

输入数据包括多行，每行给出一组测试数据，包括4个小于10的正整数。

最后一组测试数据中包括4个0，表示输入的结束，这组数据不用处理。

Output

对于每一组测试数据，输出一行，如果可以得到24，输出“YES”；否则，输出“NO”。

Sample Input

5 5 5 1
1 1 4 2
0 0 0 0

Sample Output

YES
NO

算法思想：

同样拿到题之后呢，首先第一个想法依旧是能否将问题分解为规模更小的子问题，然后利用递归解决。

对于问题解决的第一步而言，普遍想法是，先找两个数进行一种加、减、乘、除运算，再将该结果与剩下的n-2个数进行运算，那么此时，问题规模就变为了n-1，因此本题就转变为一个递归问题。

再考虑递归的次数，我们从第一步的初始状态开始不断递归判断是否能满足题设要求，当以此为初始条件均不能满足题设要求时，应继续判定下一初始条件，所以我们应枚举所有可能的第一步的初始状态，即：枚举所有可能的两个数的组合。再以此为初始条件进行递归判断是否为解。

其次考虑递归的边界条件，基于前几题的求边界条件思想，本题的边界情况十分明显，即当问题规模递归减少为1时，仅有一个数，判断与24是否相等，若相等则应返回true，表明找到一组解，若不相等应返回false，表明本次递归的初始条件不能满足题设要求。

详细说明关于在递归时数据的处理：

1. 选出两个数作为初始条件进行加、减、乘、除运算，选取时应取遍所有可能的组合，可通过二重循环实现。
2. 将这两个数（a和b）的运算结果与余下的n-2个数存起来，共n-1个数，存入一个数组中，作为中间变量，在以该中间变量数组进行递归，依次判断a+b、a-b、b-a、a*b、a/b、b/a六种情况，在除法运算中，应保证除数不为0；此时的递归为将临时变量b里的n-1个数来算24,判断是否可以满足题设要求。问题的递归主体及关键也在这里。

代码逻辑：

依据上述算法思想，不难想出应设置一个初始数组存储题设输入的一组数据；因为本题中设计除法相关操作，所以数据可能为浮点类型，但是由于浮点数在计算机中存储采用IEE754标准，存在精度丢失问题，所以对于浮点类型数据是否为0的判定不能使用“==”来判定，所以，还应定义一个函数来实现对浮点数是否为0的一个判断。

1. 在C语言中，进行浮点数为0判断时，一般考虑判断该数的绝对值是否小于一个极小值ε，通常ε选10^-6。

   代码如下：

   #define ESP 1e-6
   
   bool isZero(double num) {
       return fabs(num) <= ESP;
   }

2. 由上述算法思想中分析，设递归函数定义为，bool count24(double a[], int n)，即：对有n个元素的a组数据进行算24操作。

   • 首先进入递归函数时应判断是否满足边界条件，即，当问题规模n=1时，判断该数是否等于24。
   • 在递归主体中，首先声明中间变量数组b，用于存储剩下的n-1个数以实现递归。
   • 通过枚举每一种可能的初始条件，以期寻求所有可能的解。
   • 每找到两个数后，将其与的n-2个数存入中间变量数组b中，再对这两个数进行算法思想中第二点所分析的6种情况进行计算。

   • 假设以a+b为例，其代码可描述为：

     b[m] = a[i] + a[j];
     if (count24(b, m + 1))
         return true;

   • 假设以a/b为例，其中b不为0，其代码可描述为：

     if (!isZero(a[j])) {
         b[m] = a[i] / a[j];
         if (count24(b, m + 1))
             return true;
     }

3. 本题思想逻辑较前几题几乎并无不同，但在代码实现上有更大的难度，主要是对不同的情况做不同的递归处理，同时对于数据的处理也应考虑递归时数据作用域的不同对函数运算结果过的影响。比如用于存储题设输入元素的数组a，应为全局变量，因为在递归处理时，我们以中间变量b来进行运算，但同时也用到了数组a来为b进行赋值。所以在每一层递归中都用到了该变量，与递归层级无关，所以设置为全局变量能更好的进行代码的编写；或者将原始数组a作为形参传入递归函数，但是由于递归操作本来就对函数调用栈有较高的占用率，若再增加没有必要的形参数量，无疑是为函数调用栈带来了更大的负载。
4. 至此，递归章节将告一段落，以上数题基本涵盖了递归在时间和空间复杂度要求不高的情况下能仅用递归能解决问题的几种基本问题模型。

代码整合：

//
// Created by Ss1Two on 2023/1/18.
//

#include "stdio.h"
#include "stdbool.h"
#include "math.h"

#define ESP 1e-6 //

//判断浮点数num是否为0
bool isZero(double num) {
    return fabs(num) <= ESP;
}

//存储题设输入的原始数据
double a[5];

//把数组a中的n个元素进行算24判断
bool count24(double a[], int n) {

    //递归边界条件判定
    if (n == 1) {
        if (isZero(a[0] - 24))
            return true;
        else
            return false;
    }

    //递归时中间变量数组
    double b[5];

    //枚举每一种可能的（先找两个数做运算的）初始条件
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {

            int m = 0;// m作为处理剩下的n-2个数时的下标
            for (int k = 0; k < n; k++) {
                //将非初始条件之外的n-2个数据存入中间变量b数组中
                if (k != i && k != j)
                    b[m++] = a[k];
            }

            //将初始条件的两个值做加法运算，并存入中间变量b数组中
            //其中m+1==n-1
            b[m] = a[i] + a[j];

            //此时问题规模减一，即将b数组中的n-1个数，进行算24判断。
            //情况1：a + b
            if (count24(b, m + 1))
                return true;

            //情况2：a - b
            b[m] = a[i] - a[j];
            if (count24(b, m + 1))
                return true;

            //情况3：b - a
            b[m] = a[j] - a[i];
            if (count24(b, m + 1))
                return true;


            //情况4：a * b
            b[m] = a[i] * a[j];
            if (count24(b, m + 1))
                return true;


            //情况5：a / b ，其中b!=0
            if (!isZero(a[j])) {
                b[m] = a[i] / a[j];
                if (count24(b, m + 1))
                    return true;
            }

            //情况6：b / a ，其中a!=0
            if (!isZero(a[i])) {
                b[m] = a[j] / a[i];
                if (count24(b, m + 1))
                    return true;
            }
        }
    }
    return false;
}

int main() {
    while (true) {
        for (int i = 0; i < 4; i++) {
            scanf("%lf", &a[i]);
        }
        if (isZero(a[0]))break;
        if (count24(a, 4))
            printf("YES\n");
        else
            printf("NO\n");
    }
    return 0;
}

Created by Ss1Two on 2023/01/18