回溯算法经典应用：NOIP1998三连击（洛谷P1008）问题详解与代码解析

一、问题背景分析

三连击是NOIP1998普及组的经典题目，要求找出所有三位数组合(a, b, c)，满足：

1. b = 2×a

2. c = 3×a

3. a、b、c三个数的各位数字恰好组成1-9的不重复排列

二、算法设计思路

1. 数字有效性检查：确保数字在100-999范围内且不含0

2. 数字组合验证：检查三个数的数字是否构成1-9的完整排列

3. 遍历范围优化：a的范围限制在123-329之间(因为3×329=987仍为三位数)

三、完整代码解析

#include <iostream>
#include <cstring> // 用于memset函数

using namespace std;

// 检查数字是否有效
bool isValid(int num) {
    // 检查数字是否在100-999范围内且不含0
    if (num < 100 || num > 999) return false;
    while (num > 0) {
        if (num % 10 == 0) return false; // 发现0立即返回false
        num /= 10;
    }
    return true;
}

// 检查三个数的数字组合是否满足条件
bool checkDigits(int a, int b, int c) {
    int digits[10] = {0}; // 初始化数字出现次数统计数组
    
    // 处理三个数的各位数字
    for (int num : {a, b, c}) {
        while (num > 0) {
            int digit = num % 10;
            if (++digits[digit] > 1) return false; // 任何数字重复出现即无效
            num /= 10;
        }
    }
    
    // 检查1-9是否都恰好出现一次
    for (int i = 1; i <= 9; ++i) {
        if (digits[i] != 1) return false;
    }
    return true;
}

int main() {
    // 遍历可能的a值范围
    for (int a = 123; a <= 329; ++a) {
        if (!isValid(a)) continue; // 跳过无效的a值
        
        int b = 2 * a;
        int c = 3 * a;
        
        // 检查b、c的有效性和数字组合
        if (isValid(b) && isValid(c) && checkDigits(a, b, c)) {
            cout << a << " " << b << " " << c << endl; // 输出有效组合
        }
    }
    return 0;
}

四、关键算法解析

1. 数字分解技巧：通过取模(%)和整除(/)运算分解数字各位

2. 数字统计方法：使用数组记录每个数字出现次数

3. 遍历范围确定：数学推导缩小搜索范围提高效率

五、算法优化建议

1. 可以预先计算并存储所有有效三位数

2. 使用位运算替代数组统计可能提高效率

3. 并行处理多个候选值(现代CPU支持)

六、常见错误防范

1. 忘记检查数字是否包含0

2. 数字分解时未正确处理最后一位

3. 数组索引越界(如digit=0的情况)

参考：NOIP题解