LQ0023 三羊献瑞【枚举】

题目来源：蓝桥杯2015初赛 C++ B组E题

题目描述
观察下面的加法算式：

其中，相同的汉字代表相同的数字，不同的汉字代表不同的数字。
请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

输出格式
请你填写“三羊献瑞”所代表的4位数字（答案唯一），不要填写任何多余内容。

问题分析
方法一：枚举各位数字
对于10进制的某一位数字x和y，因为x,y≤9，得x+y≤18，即进位为1，也可以说2个10进制数做加法运算，进位最多为1。
根据题目给定的竖式，其中三必然为1。
设"三羊献瑞"=“abcd”，其中的a、b、c和d为10进制数字，那么a=1；可以设"祥瑞生辉"=“edfg”；也可以设“三羊生瑞气”=“abfdh”。
因为a=1，那么e只能是8或9，其他各个数字则为0-9，枚举计算一下。
方法二：枚举2个数的各位数字
枚举"三羊献瑞"="abcd"和“三羊生瑞气”=“abfdh”，再做判定。这个方法可以减少枚举组合数量，判定条件略微复杂。
方法三：DFS
用深度优先搜索来枚举也是一种有效的方法。
方法四：置换
使用置换来枚举也是一种程序代码简洁的方法。

AC的C语言程序（枚举各位数字）如下：

/* LQ0023 三羊献瑞 */

#include 
#include 

int main()
{
    int a = 1, b, c, d, e, f, g, h, ans;
    for (b = 0; b <= 9; b++)
        if (b != a)
        for (c = 0; c <= 9; c++)
            if (c != a && c != b)
            for (d = 0; d <= 9; d++)
                if (d != a && d != b && d != c)
                for (e = 8; e <= 9; e++)
                    if (e != b && e != c && e != d)
                    for (f = 0; f <= 9; f++)
                        if (f != a && f != b && f != c && f != d && f != e)
                        for (g = 0; g <= 9; g++)
                            if (g != a && g != b && g != c && g != d && g != e && g != f)
                            for (h = 0; h <= 9; h++) {
                                if (h != a && h != b && h != c && h != d && h != e && h != f && h != g)
                                    if ((ans = a * 1000 + b * 100 + c * 10 + d) +
                                            (e * 1000 + d * 100 + f * 10 + g) ==
                                            (a * 10000 + b * 1000 + f * 100 + d * 10 + h)) {
                                        printf("%d\n", ans);
                                        exit(0);
                                    }
                            }
    return 0;
}

AC的C语言程序（枚举2个数的各位数字）如下：

/* LQ0023 三羊献瑞 */

#include 
#include 

int main()
{
    int a = 1, b, c, d, f, h, ans;
    for (b = 0; b <= 9; b++)
        if (b != a)
        for (c = 0; c <= 9; c++)
            if (c != a && c != b)
            for (d = 0; d <= 9; d++)
                if (d != a && d != b && d != c)
                    for (f = 0; f <= 9; f++)
                        if (f != a && f != b && f != c && f != d)
                            for (h = 0; h <= 9; h++)
                                if (h != a && h != b && h != c && h != d && h != f) {
                                    ans = a * 1000 + b * 100 + c * 10 + d;
                                    int sum = a * 10000 + b * 1000 + f * 100 + d * 10 + h;
                                    int t = sum - ans;
                                    int e = t / 1000;
                                    int g = t % 10;
                                    if (e != a && e != b && e != c && e != d && e != f && e != h &&
                                            g != a && g != b && g != c && g != d && g != f && g != h &&
                                            e != g &&
                                            f == t / 10 % 10 && d == t / 100 % 10) {
                                        printf("%d\n", ans);
                                        exit(0);
                                    }
                                }

    return 0;
}

AC的C语言程序（DFS）如下：

/* LQ0023 三羊献瑞 */

#include 
#include 

/* 枚举8个数字 */
int d[8 + 1], vis[10], ans = 0;
/* 三=x[1] 羊=x[2] 献=x[3] 瑞=x[4] 祥=x[5] 辉=x[6] 生=x[7] 气=x[8] */

void dfs(int k)
{
    if (k > 8) {
        int a = d[5] * 1000 + d[4] * 100 + d[7] * 10 + d[6];
        int b = d[1] * 1000 + d[2] * 100 + d[3] * 10 + d[4];
        int sum = d[1] * 10000 + d[2] * 1000 + d[7] * 100 + d[4] * 10 + d[8];
        if (a + b == sum) ans = b;
    } else if (ans == 0) {
        for (int i = 0; i <= 9; i++)
            if (vis[i] == 0) {
                d[k] = i;
                vis[i] = 1;
                dfs (k + 1);
                vis[i] = 0;
            }
    }
}

int main()
{
    memset(vis, 0, sizeof vis);
    d[1] = 1, vis[1] = 1;

    dfs(2);

    printf("%d\n", ans);

    return 0;
}

AC的C语言程序（置换）如下：

/* LQ0023 三羊献瑞 */

#include 
#include 
using namespace std;

int main()
{
    int a[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
    for (; ;) {
        if (a[0] != 0 && a[4] != 0) {
            int sum1 = a[4] * 1000 + a[3] * 100 + a[5] * 10 + a[6];
            int sum2 = a[0] * 1000 + a[1] * 100 + a[2] * 10 + a[3];
            int sum = a[0] * 10000 + a[1] * 1000 + a[5] * 100 + a[3] * 10 + a[7];
            if (sum1 + sum2 == sum) {
                printf("%d\n", sum2);
                break;
            }
        }
        next_permutation(a, a +10);
    }

    return 0;
}