深度优先解小学算术题：987654321 +-使结果为 100

在小学数学题中，有时我们会遇到这样的题目：给出一个数字串（例如 987654321），需要在其间插入加号（+）或者减号（-），使得计算结果为 100。比如 9+8+76+5+4-3+2-1 = 100。

这种题目看似简单，但实际解题过程中需要遍历所有可能的加减组合，才能找到符合条件的表达式。本文将通过**深度优先搜索算法（DFS）**来解决这个问题，并给出 Python 代码示例。

问题描述

给定数字串 987654321，要求通过在数字间加入加号或者减号，使得计算结果为 100。我们需要找到所有符合条件的表达式。

例如，9+8+76+5+4-3+2-1 = 100 是其中一种解。

深度优先搜索（DFS）解法

我们可以将这个问题看作一个树形结构，每次选择一个操作符（+、- 或者 空），然后递归地搜索后续的组合。通过DFS，可以枚举所有可能的表达式，最终筛选出结果为 100 的组合。

代码实现

countIndex = 0

def find_expression():
    numbers = '987654321'
    operators = ['+', '-', '']  # 定义三个操作符：加、减和空（用于连接多位数）

    def generate_combinations(current_idx, current_expression):
        global countIndex
        # 如果到达最后一位数字
        if current_idx == len(numbers) - 1:
            if eval(current_expression) == 100:  # 计算表达式结果是否等于100
                countIndex += 1
                print(f"{countIndex}: {current_expression} = {eval(current_expression)}")
            return
        
        # 遍历每个操作符
        for op in operators:
            # 递归调用，生成后续组合
            generate_combinations(
                current_idx + 1, current_expression + op + numbers[current_idx + 1]
            )

    # 从正负两种情况开始生成表达式
    generate_combinations(0, '' + numbers[0])
    generate_combinations(0, '-' + numbers[0])

find_expression()

代码解析

1. 操作符的定义：我们定义了三种操作符，分别是 +、- 和 空。空 表示可以直接将数字组合成多位数。例如 '9' 和 '8' 之间没有操作符时，它们会合并为 98。
2. 递归生成表达式：我们通过递归方式，依次尝试每个操作符组合，构建表达式。递归的基准条件是，当前已经处理到数字串的最后一位。如果此时表达式的计算结果为 100，就输出该表达式。
3. 表达式计算：利用 eval() 函数来计算当前生成的表达式的结果。
4. 结果输出：代码会打印出所有符合条件的表达式。

输出结果

执行上述代码，可以得到以下结果：

1: 9+8+76+5+4-3+2-1 = 100
2: 9+8+76+5-4+3+2+1 = 100
3: 9-8+7+65-4+32-1 = 100
4: 9-8+76+54-32+1 = 100
5: 9-8+76-5+4+3+21 = 100
6: 98+7+6-5-4-3+2-1 = 100
...

共计找到了 18 种不同的表达式组合，满足计算结果为 100。

深度优先搜索的优势

使用深度优先搜索，我们可以逐步构建和探索每一个可能的表达式，直到找到满足条件的解。通过这种方式，可以枚举出所有可能的解法，而且代码逻辑清晰易懂，便于调试和扩展。

相比于暴力搜索，DFS 的递归结构更有助于将复杂问题拆解为多个子问题，这样在面对更大规模的数字串时，仍然能够保持较好的可维护性和扩展性。

总结

通过本文的解法，我们使用深度优先搜索（DFS）成功地解决了给定数字串 987654321，通过加减符号使其结果为 100 的问题。DFS 的核心思想是逐步递归搜索，直到找到满足条件的解。最后，Python 的 eval() 函数让我们可以快速验证每一个生成的表达式是否符合条件。

这种解题思路不仅仅适用于这种简单的加减符号问题，还可以推广到更复杂的组合问题，比如括号匹配、数学表达式的符号变换等。