Python枚举算法的思想与实战

前言

枚举算法是一种基础而强大的算法思想，其核心在于系统地列举所有可能的解空间，并逐一验证每个候选解是否满足问题约束条件。虽然枚举法在理论上可能面临“组合爆炸”的挑战，但在实际问题中，通过合理的剪枝、状态压缩或数学性质优化，往往能高效解决问题。

本文将围绕四个经典算法演练题展开：找符合条件的五位数、24点游戏、熄灯问题和“讨厌的青蛙”问题。我们将深入分析每道题的枚举策略、状态表示、剪枝技巧，并提供完整可运行的Python代码实现，适合初学者理解枚举思想的本质与应用。

一、找符合条件的五位数

问题描述

求解一个五位数 ABCDE（A≠0），使得：

ABCDE × A = EEEEEE

其中，EEEEEE 是由六个相同数字 E 组成的六位数。

算法分析

枚举范围：五位数范围为 10000 ~ 99999。
关键观察：
- EEEEEE = E × 111111
- 所以原式变为：ABCDE × A = E × 111111
- 即：ABCDE = (E × 111111) / A
- 因此，我们只需枚举 A ∈ [1,9], E ∈ [0,9]，计算右边值，判断是否为整数且是五位数，且首位等于 A。

实现思路

枚举 A 从 1 到 9。
枚举 E 从 0 到 9。
计算 target = E * 111111。
若 target % A == 0，则 num = target // A。
检查 num 是否为五位数，且 num // 10000 == A。
输出符合条件的结果。

代码实现

# 文件名: find_five_digit.py

def find_special_number():
    """寻找满足 ABCDE × A = EEEEEE 的五位数"""
    results = []
    for A in range(1, 10):      # A不能为0
        for E in range(0, 10):  # E可以是0~9
            target = E * 111111
            if target % A == 0:
                num = target // A
                # 检查是否为五位数且首位是A
                if 10000 <= num <= 99999 and num // 10000 == A:
                    results.append((num, A, E))
    return results

if __name__ == "__main__":
    solutions = find_special_number()
    if solutions:
        print("找到以下解：")
        for num, A, E in solutions:
            print(f"{num} × {A} = {E}*6 = {E*111111}")
    else:
        print("未找到符合条件的五位数。")

✅ 运行结果示例：
79365 × 7 = 555555 → 符合条件！

二、24点游戏

问题描述

给定4个1~13之间的整数，使用加减乘除和括号，构造表达式使其结果为24。

算法分析

核心思想：全排列 + 运算符组合 + 括号结构模拟。
难点：括号改变运算顺序，需考虑不同结合方式。
简化策略：
- 枚举4个数的所有排列（4! = 24种）。
- 枚举3个运算符的所有组合（4^3 = 64种）。
- 枚举5种基本括号结构（对应二叉树形态）：
  1. ((a op b) op c) op d
  2. (a op (b op c)) op d
  3. a op ((b op c) op d)
  4. a op (b op (c op d))
  5. (a op b) op (c op d)

实现思路

生成所有数字排列。
生成所有运算符三元组。
对每种排列和运算符组合，尝试5种括号结构。
使用 eval() 安全计算表达式（注意浮点误差）。
若结果接近24（允许±1e-6误差），记录表达式。

代码实现

# 文件名: game_24.py

from itertools import permutations, product

def solve_24(nums):
    """解决24点游戏，返回所有可行表达式"""
    ops = ['+', '-', '*', '/']
    structures = [
        "(({} {} {}) {} {}) {} {}",   # ((a op b) op c) op d
        "({} {} ({} {} {})) {} {}",   # (a op (b op c)) op d
        "{} {} (({} {} {}) {} {})",   # a op ((b op c) op d)
        "{} {} ({} {} ({} {} {}))",   # a op (b op (c op d))
        "({} {} {}) {} ({} {} {})"    # (a op b) op (c op d)
    ]
    
    solutions = set()
    
    for p in permutations(nums):
        for op_combo in product(ops, repeat=3):
            for struct in structures:
                expr = struct.format(p[0], op_combo[0], p[1], op_combo[1], p[2], op_combo[2], p[3])
                try:
                    # 避免除以0
                    if '/' in expr:
                        parts = expr.split('/')
                        # 简单检查分母不为0（实际应更严谨，此处简化）
                        pass
                    result = eval(expr)
                    if abs(result - 24) < 1e-6:
                        solutions.add(expr.replace(' ', ''))
                except:
                    continue
    
    return list(solutions)

if __name__ == "__main__":
    nums = [9, 8, 8, 3]  # 示例输入
    sols = solve_24(nums)
    if sols:
        print(f"对于数字 {nums}，有以下解法：")
        for s in sols[:5]:  # 最多显示5个
            print(s)
    else:
        print("无解")

✅ 示例输出：(9-8)*8*3=24

三、解决熄灯问题

问题描述

有一个5行6列的按钮矩阵，每个按钮控制自身及上下左右灯的状态切换（开↔关）。目标是通过按下某些按钮，使所有灯熄灭。

算法分析

关键性质：
1. 同一按钮按两次等价于没按 → 每个按钮最多按一次。
2. 操作顺序无关 → 只关心哪些按钮被按下。
3. 第一行的操作决定第二行操作 → 可逐行推导。
优化策略：
- 枚举第一行所有可能操作（2^6 = 64种）。
- 根据当前行灯状态，确定下一行必须按下的按钮（以熄灭上一行灯）。
- 最后检查最后一行是否全部熄灭。

示例矩阵图

按下按钮后状态变化示意（X表示按下）：

X . . . . .     → 影响自身+右+下（改变三盏灯的状态）
. . . . . .     
. . X . . .     → 影响自身+左+右+上+下（改变五盏灯的状态）
. . . . . . 
. . . . X .     → 影响自身+左+右+下（改变四盏灯的状态）

初始状态（1=亮，0=灭）：

1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0
0 1 0 1 0 1
1 0 1 0 1 0

最终目标：所有灯为0。

代码实现

# 文件名: lights_out.py

def get_neighbors(r, c, rows=5, cols=6):
    """获取(r,c)位置影响的邻居坐标"""
    neighbors = [(r, c)]
    if r > 0: neighbors.append((r-1, c))
    if r < rows-1: neighbors.append((r+1, c))
    if c > 0: neighbors.append((r, c-1))
    if c < cols-1: neighbors.append((r, c+1))
    return neighbors

def apply_press(grid, press, r, c):
    """在grid上应用(r,c)处的按压操作"""
    for nr, nc in get_neighbors(r, c):
        grid[nr][nc] ^= 1  # 异或翻转

def solve_lights_out(initial_grid):
    """解决熄灯问题，返回按下方案"""
    rows, cols = 5, 6
    best_solution = None
    
    # 枚举第一行所有可能操作（0~63）
    for first_row_mask in range(1 << cols):
        grid = [row[:] for row in initial_grid]  # 复制初始状态
        press_plan = [[0]*cols for _ in range(rows)]
        
        # 设置第一行按压计划
        for c in range(cols):
            if (first_row_mask >> c) & 1:
                press_plan[0][c] = 1
                apply_press(grid, press_plan, 0, c)
        
        # 根据上一行灯状态，决定当前行按压
        for r in range(1, rows):
            for c in range(cols):
                if grid[r-1][c] == 1:  # 上一行该列灯还亮着，必须按当前行对应按钮
                    press_plan[r][c] = 1
                    apply_press(grid, press_plan, r, c)
        
        # 检查最后一行是否全灭
        if all(grid[rows-1][c] == 0 for c in range(cols)):
            best_solution = press_plan
            break  # 找到一个即可
    
    return best_solution

if __name__ == "__main__":
    # 示例输入：5x6矩阵，1表示灯亮，0表示灯灭
    initial = [
        [1, 0, 1, 0, 1, 0],
        [0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0],
        [0, 1, 0, 1, 0, 1],
        [1, 0, 1, 0, 1, 0]
    ]
    
    solution = solve_lights_out(initial)
    if solution:
        print("按下方案（1=按下，0=不按）：")
        for row in solution:
            print(" ".join(map(str, row)))
    else:
        print("无解")

📌 注：本例中由于对称性，可能存在多个解，程序返回第一个找到的解。

四、解决“讨厌的青蛙”问题

问题描述

稻田为R×C网格，N棵水稻被踩踏。青蛙沿直线跳跃，每次跳固定步长(dx, dy)，路径上至少踩3棵水稻。求单只青蛙最多踩多少棵水稻。

算法分析

核心思想：枚举路径起点和前两个点，确定方向向量(dx, dy)，然后向前/向后延伸统计路径上的水稻数。
剪枝优化：
- 起点必须是某棵被踩水稻。
- 第二步也必须落在另一棵被踩水稻上。
- 路径两端必须超出稻田边界（确保是完整穿越）。
- 若当前路径长度 ≤ 已知最大值，提前终止。

示例矩阵图

稻田6行7列，被踩水稻位置（●表示）：

  1 2 3 4 5 6 7
1 ● . . . . . .
2 . ● . . . . .
3 . . ● . . . .
4 . . . ● . . .
5 . . . . ● . .
6 . . . . . ● .

青蛙路径：(1,1)→(2,2)→(3,3)→(4,4)→(5,5)→(6,6) → 共6棵。

代码实现

# 文件名: angry_frog.py

def solve_angry_frog(R, C, damaged_rice):
    """解决讨厌的青蛙问题，返回最大踩踏数"""
    # 将损坏水稻存入集合便于O(1)查询
    rice_set = set(tuple(pos) for pos in damaged_rice)
    max_steps = 0
    
    # 枚举每一对被踩水稻作为路径前两点
    n = len(damaged_rice)
    for i in range(n):
        x1, y1 = damaged_rice[i]
        for j in range(i+1, n):
            x2, y2 = damaged_rice[j]
            dx = x2 - x1
            dy = y2 - y1
            
            # 反向延伸：检查(x1-dx, y1-dy)是否在田外
            prev_x, prev_y = x1 - dx, y1 - dy
            if 1 <= prev_x <= R and 1 <= prev_y <= C:
                continue  # 起点不在边界外，无效
            
            # 正向延伸：从(x2,y2)开始继续走
            steps = 2  # 已包含前两点
            curr_x, curr_y = x2 + dx, y2 + dy
            while 1 <= curr_x <= R and 1 <= curr_y <= C:
                if (curr_x, curr_y) in rice_set:
                    steps += 1
                    curr_x += dx
                    curr_y += dy
                else:
                    break
            
            # 检查终点是否在田外
            if not (1 <= curr_x <= R and 1 <= curr_y <= C):
                if steps >= 3 and steps > max_steps:
                    max_steps = steps
    
    return max_steps if max_steps >= 3 else 0

if __name__ == "__main__":
    # 示例输入
    R, C = 6, 7
    damaged = [
        (1,1), (2,2), (3,3), (4,4), (5,5), (6,6),
        (1,7), (2,6), (3,5), (4,4), (5,3), (6,2)
    ]
    
    result = solve_angry_frog(R, C, damaged)
    print(f"最多踩踏水稻数: {result}")

✅ 示例输出：最多踩踏水稻数: 6

小结

枚举算法虽看似“笨拙”，却是许多复杂问题的基石。本文四个案例展示了枚举的不同面貌：

数值枚举（五位数）：利用数学性质缩小搜索空间。
组合枚举（24点）：结合排列、运算符、括号结构。
状态枚举（熄灯）：利用递推关系减少维度。
几何枚举（青蛙）：基于向量与边界条件剪枝。

掌握枚举的关键在于：

明确解空间边界；
设计高效的验证函数；
善用剪枝与预处理；
灵活转换问题视角（如熄灯问题中的“第一行决定全局”）。

希望本文能帮助读者建立对枚举算法的系统认知，并在实践中举一反三，攻克更多算法难题！

前言

一、找符合条件的五位数

问题描述

算法分析

实现思路

代码实现

二、24点游戏

问题描述

算法分析

实现思路

代码实现

三、解决熄灯问题

问题描述

算法分析

示例矩阵图

代码实现

四、解决“讨厌的青蛙”问题

问题描述

算法分析

示例矩阵图

代码实现

小结

微风陪我得闲捕梦