题解 | #24点游戏算法#

解题思路

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

对于输入的4个数字，需要考虑所有可能的两两组合

对每个组合，尝试四种运算（加、减、乘、除）

将运算结果与剩余的数字继续进行组合运算

如果最终结果为24，则返回true

注意处理除法时的除数不为0的情况

代码

#include

#include

#include

using namespace std;

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

bool isEqual(double a, double b) {

return fabs(a - b) < EPSILON;

}

bool solve24(vector& 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 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 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 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 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 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的特殊处理。