递归算法实例应用五

算24 POJ 2787

Description

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

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

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

又比如对于1142我们怎么都不能得到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判断。
            //情况1a + b
            if (count24(b, m + 1))
                return true;

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

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


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


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

            //情况6b / 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\cdots by\cdots Ss1Two\cdots on\cdots 2023/01/18$$