题解 | 24点游戏算法

package main

import (
	"fmt"
	"math"
)

const (
	TARGET = 24.0 // 目标值
	EPS    = 1e-6 // 浮点数精度
)

// 检查两个浮点数是否相等
func isEqual(a, b float64) bool {
	return math.Abs(a-b) < EPS
}

// 检查浮点数是否为零
func isZero(a float64) bool {
	return math.Abs(a) < EPS
}

// 递归回溯函数
// nums: 当前数字列表
// 返回值: 是否能计算出24
func canGet24(nums []float64) bool {
	n := len(nums)

	// 终止条件：只剩一个数字
	if n == 1 {
		return isEqual(nums[0], TARGET)
	}

	// 枚举所有可能的数字对
	for i := 0; i < n; i++ {
		for j := i + 1; j < n; j++ {
			a, b := nums[i], nums[j]

			// 创建新的数字列表（移除选中的两个数字）
			newNums := make([]float64, 0, n-1)
			for k := 0; k < n; k++ {
				if k != i && k != j {
					newNums = append(newNums, nums[k])
				}
			}

			// 尝试四种运算符
			// 1. 加法（交换律，只需计算一次）
			newNums = append(newNums, a+b)
			if canGet24(newNums) {
				return true
			}
			newNums = newNums[:len(newNums)-1] // 回溯

			// 2. 减法（不满足交换律，需要计算两次）
			// a - b
			newNums = append(newNums, a-b)
			if canGet24(newNums) {
				return true
			}
			newNums = newNums[:len(newNums)-1] // 回溯

			// b - a
			newNums = append(newNums, b-a)
			if canGet24(newNums) {
				return true
			}
			newNums = newNums[:len(newNums)-1] // 回溯

			// 3. 乘法（交换律，只需计算一次）
			newNums = append(newNums, a*b)
			if canGet24(newNums) {
				return true
			}
			newNums = newNums[:len(newNums)-1] // 回溯

			// 4. 除法（不满足交换律，需要计算两次）
			// a / b
			if !isZero(b) {
				newNums = append(newNums, a/b)
				if canGet24(newNums) {
					return true
				}
				newNums = newNums[:len(newNums)-1] // 回溯
			}

			// b / a
			if !isZero(a) {
				newNums = append(newNums, b/a)
				if canGet24(newNums) {
					return true
				}
				newNums = newNums[:len(newNums)-1] // 回溯
			}
		}
	}

	return false
}

// 24点游戏主函数
func game24(a, b, c, d int) bool {
	// 转换为浮点数列表
	nums := []float64{float64(a), float64(b), float64(c), float64(d)}

	// 调用递归函数
	return canGet24(nums)
}

func main() {
	var a, b, c, d int

	// 读取输入
	fmt.Scan(&a, &b, &c, &d)

	// 判断是否能得到24
	if game24(a, b, c, d) {
		fmt.Println("true")
	} else {
		fmt.Println("false")
	}
}

解题思路

算法分析

这道题的核心是递归回溯和表达式求值。主要涉及：

1. 递归枚举：所有可能的数字组合和运算符组合
2. 回溯搜索：尝试所有可能的计算路径
3. 浮点数处理：处理除法运算的精度问题
4. 剪枝优化：提前终止不可能的计算路径

问题本质分析

graph TD
    A[24点游戏] --> B[递归枚举]
    B --> C[选择两个数字]
    B --> D[选择运算符]
    C --> E[四种运算]
    D --> E
    E --> F[生成新数字]
    F --> G[更新数字列表]
    G --> H{剩余数字个数}
    H -->|1个| I[检查是否为24]
    H -->|>1个| J[递归继续]
    I --> K[返回结果]
    J --> B

递归搜索策略

graph TD
    A[递归搜索] --> B[终止条件]
    B --> C[只剩一个数字]
    C --> D[检查是否接近24]
    
    E[递归过程] --> F[选择两个数字]
    F --> G[尝试四种运算]
    G --> H[+ 加法]
    G --> I[- 减法]
    G --> J[* 乘法] 
    G --> K[/ 除法]
    
    H --> L[递归调用]
    I --> L
    J --> L
    K --> M[检查除数非零]
    M --> L
    L --> N[回溯还原]

运算符处理详解

flowchart TD
    A[四种运算符] --> B[加法 a+b]
    A --> C[减法 a-b, b-a]
    A --> D[乘法 a*b]
    A --> E[除法 a/b, b/a]
    
    B --> F[交换律适用]
    C --> G[不满足交换律]
    D --> F
    E --> H[需检查除数非零]
    
    F --> I[只需计算一次]
    G --> J[需计算两次]
    H --> J
    
    I --> K[优化处理]
    J --> L[完整枚举]
    K --> M[递归调用]
    L --> M

浮点数精度处理

graph TD
    A[浮点数精度] --> B[IEEE 754标准]
    B --> C[精度误差]
    C --> D[比较策略]
    
    D --> E[绝对误差法]
    E --> F[abs(x - 24) < ε]
    F --> G[ε = 1e-6]
    
    H[除法处理] --> I[除数检查]
    I --> J[abs(divisor) < ε]
    J --> K[跳过除法运算]
    
    G --> L[精度控制]
    K --> L

算法流程图

flowchart TD
    A[输入四个数字] --> B[调用递归函数]
    B --> C[判断数字个数]
    C --> D{只剩一个数字?}
    D -->|是| E[检查是否为24]
    D -->|否| F[枚举所有数字对]
    
    E --> G{|num - 24| < 1e-6?}
    G -->|是| H[返回true]
    G -->|否| I[返回false]
    
    F --> J[选择数字i和j]
    J --> K[尝试四种运算]
    K --> L[加法: i+j]
    K --> M[减法: i-j, j-i]
    K --> N[乘法: i*j]
    K --> O[除法: i/j, j/i]
    
    L --> P[生成新数字列表]
    M --> Q[检查是否不同]
    N --> R[检查交换律]
    O --> S[检查除数非零]
    
    P --> T[递归调用]
    Q --> T
    R --> T
    S --> T
    T --> U{返回true?}
    U -->|是| H
    U -->|否| V[尝试下一种运算]
    V --> W{所有运算尝试完?}
    W -->|否| K
    W -->|是| X[尝试下一个数字对]
    X --> Y{所有数字对尝试完?}
    Y -->|否| F
    Y -->|是| I

代码实现思路

1. 递归函数设计：参数：当前数字列表返回值：是否能计算出24终止条件：只剩一个数字时检查结果
2. 运算符处理：加法和乘法：交换律，只需计算一次减法和除法：不满足交换律，需要计算两次除法特殊处理：检查除数是否为零
3. 数字列表更新：移除参与运算的两个数字添加运算结果递归调用后恢复原状态

时间复杂度分析

• 时间复杂度：O(4^3 × 3!)，其中4是运算符数量，3是递归层数
• 空间复杂度：O(4)，递归栈深度最大为4

关键优化点

1. 交换律优化：加法和乘法只计算一次
2. 提前终止：找到解后立即返回
3. 精度控制：使用合适的epsilon值
4. 除零检查：避免除法运算错误

边界情况处理

1. 相同数字：如1,1,1,1无解
2. 特殊组合：需要括号改变运算顺序
3. 除法精度：处理浮点数除法结果
4. 极端情况：很大或很小的中间结果

测试用例分析

graph TD
    A[测试用例1: 7,2,1,10] --> B[7×1×2+10=24]
    B --> C[结果: true]
    
    D[测试用例2: 2,2,2,9] --> E[2+2×(2+9)=24]
    E --> F[结果: true]
    
    G[测试用例3: 10,9,6,9] --> H[10×9÷6+9=24]
    H --> I[结果: true]
    
    J[测试用例4: 3,3,8,8] --> K[8÷(3-8÷3)=24]
    K --> L[结果: true]
    
    M[测试用例5: 1,1,1,1] --> N[无法组合成24]
    N --> O[结果: false]
    
    C --> P[验证算法正确性]
    F --> P
    I --> P
    L --> P
    O --> P

递归树分析

graph TD
    A[初始: [7,2,1,10]] --> B[选择7和2]
    A --> C[选择7和1]
    A --> D[选择7和10]
    
    B --> E[7+2=9: [9,1,10]]
    B --> F[7-2=5: [5,1,10]]
    B --> G[7*2=14: [14,1,10]]
    B --> H[7/2=3.5: [3.5,1,10]]
    
    E --> I[继续递归...]
    F --> I
    G --> I
    H --> I
    
    I --> J[找到解: 14*1+10=24]
    J --> K[返回true]

算法特点

1. 完全搜索：枚举所有可能的计算路径
2. 回溯机制：尝试失败后自动恢复状态
3. 精度控制：正确处理浮点数运算
4. 优化剪枝：利用交换律减少计算量

实际应用场景

1. 游戏开发：24点游戏实现
2. 数学教育：算术表达式求值
3. 算法竞赛：递归回溯类问题
4. 表达式计算：四则运算组合求值

关键数学理论

graph TD
    A[数学理论] --> B[排列组合]
    B --> C[C(4,2) = 6种数字选择]
    C --> D[每对数字4种运算]
    D --> E[减法和除法考虑顺序]
    
    F[递归理论] --> G[分治思想]
    G --> H[问题分解]
    H --> I[子问题求解]
    I --> J[结果合并]
    
    E --> K[搜索空间]
    J --> K
    K --> L[总体复杂度分析]

精度处理策略

graph TD
    A[精度处理] --> B[epsilon选择]
    B --> C[1e-6适中精度]
    C --> D[避免过严格]
    D --> E[避免过宽松]
    
    F[比较函数] --> G[abs(a-b) < eps]
    G --> H[相等判断]
    H --> I[24的判断]
    
    E --> J[精度平衡]
    I --> J
    J --> K[算法稳定性]

这个问题的关键在于正确实现递归回溯搜索和妥善处理浮点数精度问题，通过枚举所有可能的运算组合来判断是否能得到24。