python/TangDou/LanQiaoBei/LanQiao14STEMA202208/编程解决小学奥数问题(竖式).md

一、题目大意

昨日，糖豆做了一道小学四年级数学举一反三试题：

\large ~~~~abcdef \large + abcdef \large ---- \large ~~~jeghba

已知题目中所有字符是非负整数,求abcdef和jeghba的值是多少？

此题我给出的数学方法是画树形图，标注分支，然后尝试每个分支，判断是否符合题目，是否可以剪枝，但计算量很大，糖豆历时20分钟，完成此题。

回头思考，既然都画了树形图，不如使用编程的办法尝试一下，随即做了两套办法，现整理给同学们参考，望大家深入理解深搜的优势，以及它的实现细节。

二、循环暴力法

Running~time:1000ms 1秒内完成计算，无法优化了，没法剪枝。贵在思路简单，好上手。

#include <bits/stdc++.h>

using namespace std;

const int N = 10;
int a[N], al; //用于将最终的两个原数字相加的结果 拆分到数组中
int b[N], bl; //用于拆分原数字到数组中

int main() {
    //记录开始时间
    clock_t begin = clock();

    // 1234
    //排重后数字个数
    unordered_set<int> _set1, _set2;
    
    for (int i = 123456; i < 1000000 / 2; i++) {
        int x = i;
        int y = i + i;

        al = 0;
        while (y) a[++al] = y % 10, y /= 10;

        bl = 0;
        while (x) b[++bl] = x % 10, x /= 10;
        
        _set1.clear();
        for (int j = 1; j <= al; j++) _set1.insert(a[j]);
        if (_set1.size() != 6) continue;

        _set2.clear();
        for (int j = 1; j <= bl; j++) _set2.insert(b[j]);
        if (_set2.size() != 6) continue;

        if (a[1] == b[6] && a[2] == b[5] && a[5] == b[2]
            && !_set2.count(a[3]) && !_set2.count(a[4]) && !_set2.count(a[6]))
            printf("%d\n", i);
    }

    //记录结束时间
    clock_t end = clock();
    cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;

    return 0;
}

三、深搜+剪枝

Running~~ time:3ms

逆天的3ms！整整快了300倍~

分析： 因深搜可以在行进过程中随时发现问题，随时终止此分支前进，防止了很多无用的枚举。

#include <bits/stdc++.h>

using namespace std;
/*

输出：
468532
*/
const int N = 10;
int num;      //不断增加的前缀，最终是选择的数字
bool st[N];   // 0~9哪个数字使用过
int a[N], al; //用于将最终的两个原数字相加的结果 拆分到数组中
int b[N], bl; //用于拆分原数字到数组中

void dfs(int u) {
    if (u == 7) { //完成所有数位的枚举
        int sum = num << 1, tmp = num;

        //拆分到数组中
        al = 0;
        while (sum) a[++al] = sum % 10, sum /= 10;

        bl = 0;
        while (tmp) b[++bl] = tmp % 10, tmp /= 10;

        //判断条件,能剪枝的代码，尽量提前，减少后面无用的计算
        // 放在unordered_set前面，可以做到: Running time:3ms
        if (a[1] != b[6] || a[2] != b[5] || a[5] != b[2]) return;
        if (st[a[6]] || st[a[4]] || st[a[3]]) return;

        // Running time:526ms
        //判断是不是结果存在数位值重复
        unordered_set<int> _set;
        for (int i = 1; i <= al; i++) _set.insert(a[i]);
        if (_set.size() < 6) return;

        //全部符合要求，输出结果
        printf("%d\n", num);
        return;
    }
    for (int i = 0; i <= 9; i++) {
        //首位不能达到5，否则就是7位了,剪枝
        //如果是首位，a!=1,因为加法的结果个数是1，加法结果最小应该是2开始
        // a只能是2,4
        if (u == 1 && (i != 2 && i != 4)) continue;
        if (!st[i]) {
            st[i] = true;
            num = num * 10 + i; //增加上此位
            dfs(u + 1);         //下一个位置
            // num = (num - i) / 10; //减回去此位
            //简写
            num = num / 10; //减回去此位
            st[i] = false;
        }
    }
}
int main() {
    //记录开始时间
    clock_t begin = clock();

    dfs(1);

    //记录结束时间
    clock_t end = clock();
    cout << "Running time:" << (double)(end - begin) / CLOCKS_PER_SEC * 1000 << "ms" << endl;

    return 0;
}