题解 | #24点游戏算法#

加了一个分数类解决小数精度带来的问题

#include<stdio.h>
typedef struct frac_tag {
    int up;
    int down;
}frac;
frac op(frac a, char oper, frac b) {
    frac res;
    if (a.down == 0 || b.down == 0) {
        res.down = 0;
        return res;
    }
    if (oper == '+' || oper == '-') {
        a.up *= b.down;
        b.up *= a.down;
        res.up = oper=='+'?a.up + b.up:a.up-b.up;
        res.down = a.down * b.down;
        return res;
    }
    if (oper == '*') {
        res.up = a.up * b.up;
        res.down = a.down * b.down;
        return res;
    }
    else {
        if (b.up == 0) {
            res.down = 0;
            return res;
        }
        res.up = a.up * b.down;
        res.down = a.down * b.up;
        return res;
    }
}
void cal(frac* a, int* ser, int step, int* pflag) {
    if (*pflag == 1)return;
    if (step == 4) {
        if (a[0].down
            && a[0].up / a[0].down == 24
            && a[0].up % a[0].down == 0) {
            *pflag = 1;
        }
        return;
    }
    else {
        frac a0 = a[0];
        a[0] = op(step == 1 ? a[ser[step]] : a[0], '*', a[ser[step+ 1]]);
        cal(a, ser, step + 1, pflag);
        a[0] = a0;
        a[0] = op(step == 1 ? a[ser[step]]:a[0], '+', a[ser[step + 1]]);
        cal(a, ser, step + 1, pflag);
        a[0] = a0;
        a[0] = op(step == 1 ? a[ser[step]]:a[0], '-', a[ser[step + 1]]);
        cal(a, ser, step + 1, pflag);
        a[0] = a0;
        a[0] = op(step == 1 ? a[ser[step]]:a[0], '/', a[ser[step + 1]]);
        cal(a, ser, step + 1, pflag);
        a[0] = a0;
    }
}
int main() {
    frac a[5];
    while (scanf("%d%d%d%d", &a[1].up, &a[2].up, &a[3].up, &a[4].up) != EOF) {
        a[1].down = a[2].down = a[3].down = a[4].down = 1;
        int flag = 0;
        for (int i = 1; i <= 4; i++) {
            for (int j = 1; j <= 4 ; j++) {
                if (j != i) {
                    for (int k = 1; k <= 4 ; k++) {
                        if (k != i && k != j) {
                            int step = 1, ser[5] = { 0,i,j,k,10 - i - j - k };
                            cal(a, ser, step, &flag);
                        }
                    }
                }
            }
        }
        printf("%s\n", flag == 1 ? "true": "false");
    }
}