题解 | #24点游戏算法#

解题思路

这是一个经典的24点游戏问题，需要通过回溯算法来尝试所有可能的运算组合。主要步骤：

1. 对于输入的4个数字，需要考虑所有可能的两两组合
2. 对每个组合，尝试四种运算（加、减、乘、除）
3. 将运算结果与剩余的数字继续进行组合运算
4. 如果最终结果为24，则返回true
5. 注意处理除法时的除数不为0的情况

代码

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const double EPSILON = 1e-10;  // 用于浮点数比较

bool isEqual(double a, double b) {
    return fabs(a - b) < EPSILON;
}

bool solve24(vector<double>& numbers) {
    if (numbers.size() == 1) {
        return isEqual(numbers[0], 24);
    }
    
    for (int i = 0; i < numbers.size(); i++) {
        for (int j = i + 1; j < numbers.size(); j++) {
            double a = numbers[i];
            double b = numbers[j];
            vector<double> next;
            
            // 保存剩余的数字
            for (int k = 0; k < numbers.size(); k++) {
                if (k != i && k != j) {
                    next.push_back(numbers[k]);
                }
            }
            
            // 尝试四种运算
            next.push_back(a + b);
            if (solve24(next)) return true;
            next.pop_back();
            
            next.push_back(a - b);
            if (solve24(next)) return true;
            next.pop_back();
            
            next.push_back(a * b);
            if (solve24(next)) return true;
            next.pop_back();
            
            if (!isEqual(b, 0)) {
                next.push_back(a / b);
                if (solve24(next)) return true;
                next.pop_back();
            }
            
            next.push_back(b - a);
            if (solve24(next)) return true;
            next.pop_back();
            
            if (!isEqual(a, 0)) {
                next.push_back(b / a);
                if (solve24(next)) return true;
                next.pop_back();
            }
        }
    }
    return false;
}

int main() {
    int a, b, c, d;
    while (cin >> a >> b >> c >> d) {
        vector<double> numbers = {(double)a, (double)b, (double)c, (double)d};
        cout << (solve24(numbers) ? "true" : "false") << endl;
    }
    return 0;
}

import java.util.*;

public class Main {
    private static final double EPSILON = 1e-10;
    
    private static boolean isEqual(double a, double b) {
        return Math.abs(a - b) < EPSILON;
    }
    
    private static boolean solve24(List<Double> numbers) {
        if (numbers.size() == 1) {
            return isEqual(numbers.get(0), 24);
        }
        
        for (int i = 0; i < numbers.size(); i++) {
            for (int j = i + 1; j < numbers.size(); j++) {
                double a = numbers.get(i);
                double b = numbers.get(j);
                List<Double> next = new ArrayList<>();
                
                // 保存剩余的数字
                for (int k = 0; k < numbers.size(); k++) {
                    if (k != i && k != j) {
                        next.add(numbers.get(k));
                    }
                }
                
                // 尝试四种运算
                next.add(a + b);
                if (solve24(next)) return true;
                next.remove(next.size() - 1);
                
                next.add(a - b);
                if (solve24(next)) return true;
                next.remove(next.size() - 1);
                
                next.add(a * b);
                if (solve24(next)) return true;
                next.remove(next.size() - 1);
                
                if (!isEqual(b, 0)) {
                    next.add(a / b);
                    if (solve24(next)) return true;
                    next.remove(next.size() - 1);
                }
                
                next.add(b - a);
                if (solve24(next)) return true;
                next.remove(next.size() - 1);
                
                if (!isEqual(a, 0)) {
                    next.add(b / a);
                    if (solve24(next)) return true;
                    next.remove(next.size() - 1);
                }
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            List<Double> numbers = new ArrayList<>();
            for (int i = 0; i < 4; i++) {
                numbers.add(sc.nextDouble());
            }
            System.out.println(solve24(numbers) ? "true" : "false");
        }
    }
}

def is_equal(a, b):
    return abs(a - b) < 1e-10

def solve24(numbers):
    if len(numbers) == 1:
        return is_equal(numbers[0], 24)
    
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            a = numbers[i]
            b = numbers[j]
            next_nums = [numbers[k] for k in range(len(numbers)) if k != i and k != j]
            
            # 尝试四种运算
            next_nums.append(a + b)
            if solve24(next_nums): return True
            next_nums.pop()
            
            next_nums.append(a - b)
            if solve24(next_nums): return True
            next_nums.pop()
            
            next_nums.append(a * b)
            if solve24(next_nums): return True
            next_nums.pop()
            
            if not is_equal(b, 0):
                next_nums.append(a / b)
                if solve24(next_nums): return True
                next_nums.pop()
            
            next_nums.append(b - a)
            if solve24(next_nums): return True
            next_nums.pop()
            
            if not is_equal(a, 0):
                next_nums.append(b / a)
                if solve24(next_nums): return True
                next_nums.pop()
    
    return False

while True:
    try:
        numbers = list(map(float, input().split()))
        print("true" if solve24(numbers) else "false")
    except:
        break

算法及复杂度

• 算法：回溯法（深度优先搜索）
• 时间复杂度：，因为需要考虑4个数字的所有排列组合
• 空间复杂度：，其中n是递归深度

这个解法通过回溯算法尝试所有可能的运算组合，同时使用浮点数比较来处理除法可能产生的精度问题。代码中还包含了对除数为0的特殊处理。