从趣味等式到计算机思维：回溯法与"找叛徒"的数学之旅

import java.util.ArrayList;
import java.util.List;
import java.util.ArrayList;
import java.util.List;
/**
 * 使用回溯法解决儿童等式魔法数问题
 * 在数字1□2□3□4□5□6□7□8=10的方框中填入"+"或"-"，使等式成立
 */
public class MagicNumberBacktracking {
    // 定义数字序列
    private static final int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8};
    // 目标结果
    private static final int target = 10;
    // 存储所有找到的解
    private static List<String> solutions = new ArrayList<>();
    public static void main(String[] args) {
        // 开始回溯搜索
        backtrack(new char[7], 0); // 7个运算符位置
        // 打印所有找到的解
        printSolutions();
    }
    /**
     * 回溯法核心方法，递归尝试所有可能的运算符组合
     * @param operators 当前运算符数组（'+'或'-'）
     * @param position 当前处理的位置（0-6）
     */
    private static void backtrack(char[] operators, int position) {
        // 基本情况：所有运算符位置都已填充
        if (position == 7) {
            // 计算当前运算符组合的结果
            int sum = calculate(operators);
            // 如果结果等于目标值，保存这个解
            if (sum == target) {
                solutions.add(buildEquation(operators));
            }
            return;
        }
        // 递归情况：尝试两种可能的运算符
        // 1. 尝试加号
        operators[position] = '+';
        backtrack(operators, position + 1);
        // 2. 尝试减号
        operators[position] = '-';
        backtrack(operators, position + 1);
    }
    /**
     * 根据给定的运算符计算等式结果
     * @param operators 运算符数组
     * @return 计算结果
     */
    private static int calculate(char[] operators) {
        // 初始值为第一个数字
        int sum = numbers[0];
        // 遍历每个运算符和对应的数字
        for (int i = 0; i < operators.length; i++) {
            if (operators[i] == '+') {
                sum += numbers[i + 1]; // 加下一个数字
            } else {
                sum -= numbers[i + 1]; // 减下一个数字
            }
        }
        return sum;
    }
    /**
     * 根据运算符构建等式字符串
     * @param operators 运算符数组
     * @return 等式字符串
     */
    private static String buildEquation(char[] operators) {
        StringBuilder sb = new StringBuilder();
        sb.append(numbers[0]); // 添加第一个数字
        // 添加每个运算符和对应的数字
        for (int i = 0; i < operators.length; i++) {
            sb.append(operators[i]).append(numbers[i + 1]);
        }
        sb.append("=").append(target); // 添加等号和目标值
        return sb.toString();
    }
    /**
     * 打印所有找到的解
     */
    private static void printSolutions() {
        if (solutions.isEmpty()) {
            System.out.println("没有找到符合条件的等式");
            return;
        }
        System.out.println("找到的魔法公式:");
        for (String solution : solutions) {
            System.out.println(solution);
        }
    }
}

import java.util.ArrayList;
import java.util.List;
/**
 * 使用找叛徒法解决儿童等式魔法数问题
 * 
 * 数学原理：总和 - 目标 = 2 × 叛徒和（需要变为减号的数字之和）
 */
public class MagicNumberTraitor {
    // 定义数字序列
    private static final int[] numbers = {1, 2, 3, 4, 5, 6, 7, 8};
    // 目标结果
    private static final int target = 10;
    // 存储所有找到的解
    private static List<String> solutions = new ArrayList<>();
    public static void main(String[] args) {
        // 寻找所有解
        findSolutions();
        // 打印所有解
        printSolutions();
    }
    /**
     * 使用找叛徒法寻找所有解
     */
    private static void findSolutions() {
        // 1. 计算所有数字的总和（假设全部用加号）
        int totalSum = 0;
        for (int num : numbers) {
            totalSum += num;
        }
        // 2. 计算总和与目标的差值
        int difference = totalSum - target;
        // 3. 如果差值为奇数，无解（因为需要差值是叛徒和的两倍）
        if (difference % 2 != 0) {
            return;
        }
        // 4. 计算叛徒和（需要变为减号的数字之和）
        int traitorSum = difference / 2;
        // 5. 找出所有可能的叛徒组合（子集和等于traitorSum）
        List<List<Integer>> traitorCombinations = findSubsets(traitorSum);
        // 6. 为每个叛徒组合生成等式
        for (List<Integer> traitors : traitorCombinations) {
            solutions.add(buildEquation(traitors));
        }
    }
    /**
     * 寻找所有子集，其和等于目标值
     * @param targetSum 目标和
     * @return 所有符合条件的子集列表
     */
    private static List<List<Integer>> findSubsets(int targetSum) {
        List<List<Integer>> result = new ArrayList<>();
        /**
         * 注意：
         * 由于第一个数字前面没有方框去指定加号或者减号，不会是叛徒，需要过滤掉，下标从1开始
         */
        findSubsetsHelper(numbers, 1, targetSum, new ArrayList<>(), result);
        return result;
    }
    /**
     * 回溯法寻找子集和的辅助方法
     * @param nums 数字数组
     * @param index 当前处理的索引
     * @param remaining 剩余需要达到的和
     * @param current 当前子集
     * @param result 存储结果的列表
     */
    private static void findSubsetsHelper(int[] nums, int index, int remaining, 
                                        List<Integer> current, List<List<Integer>> result) {
        // 找到符合条件的子集
        if (remaining == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        // 尝试每个可能的数字
        for (int i = index; i < nums.length; i++) {
            // 跳过太大的数字
            if (nums[i] > remaining) continue;
            // 尝试包含当前数字
            current.add(nums[i]);
            findSubsetsHelper(nums, i + 1, remaining - nums[i], current, result);
            // 回溯，移除当前数字
            current.remove(current.size() - 1);
        }
    }
    /**
     * 根据叛徒列表构建等式字符串
     * @param traitors 需要变为减号的数字列表
     * @return 等式字符串
     */
    private static String buildEquation(List<Integer> traitors) {
        StringBuilder sb = new StringBuilder();
        sb.append(numbers[0]); // 第一个数字总是正
        // 遍历剩余数字
        for (int i = 1; i < numbers.length; i++) {
            // 如果数字在叛徒列表中，用减号
            if (traitors.contains(numbers[i])) {
                sb.append("-");
            } else {
                sb.append("+");
            }
            sb.append(numbers[i]);
        }
        sb.append("=").append(target);
        return sb.toString();
    }
    /**
     * 打印所有找到的解
     */
    private static void printSolutions() {
        if (solutions.isEmpty()) {
            System.out.println("没有找到符合条件的等式");
            return;
        }
        System.out.println("找到的魔法公式:");
        for (String solution : solutions) {
            System.out.println(solution);
        }
    }
}