数字排列的方法

【题目描述】

用1，2，3，…，9组成3个三位数abc，def和ghi，每个数字恰好使用一次，要求abc：def：ghi＝1：2：3。按照“abc def ghi”的格式输出所有解，每行一个解。提示：不必太动脑筋。

【题目来源】

刘汝佳《算法竞赛入门经典  第2版》习题2-6　排列（permutation）

【解析】

一、逐一避重法

这是老金想出的笨办法，算法分两部分：

(1)数的生成：

①a、b、c三个数字用三层循环生成；

②将a、b、c合成三位数abc；

③根据比例关系求出def、ghi；

④将def、ghi分离成d、e、f、g、h、i；

(2)数的避重：每生成一个数，都去与之前生成的所有数逐一比较是否相等，相等就跳过，不相等就再生成下一个数。

#include<stdio.h>
int main(){
    int a, b, c, d, e, f, g, h, i;
    for(a=1; a<=3; a++){
        for(b=1; b<=9; b++){
            if(b==a) continue;
            for(c=1; c<=9; c++){
                if(c==a||c==b) continue;

                //根据abc，分别求出d、e、f、g、h、i
                int abc = 100*a+10*b+c;
                int def = 2*abc;
                int ghi = 3*abc;
                d = def/100;
                e = def/10%10;
                f = def%10;
                g = ghi/100;
                h = ghi/10%10;
                i = ghi%10;

                //排除def、ghi是4位数的情况
                if(d>9||g>9) continue;

                //排除每个数字与前面所有数字相等的情况
                if(d==a||d==b||d==c) continue;
                if(e==a||e==b||e==c||e==d) continue;
                if(f==a||f==b||f==c||f==d||f==e) continue;
                if(g==a||g==b||g==c||g==d||g==e||g==f) continue;
                if(h==a||h==b||h==c||h==d||h==e||h==f||h==g) continue;
                if(i==a||i==b||i==c||i==d||i==e||i==f||i==g||i==h) continue;

                //排除d、e、f、g、h、i中有0的情况
                if(0==d||0==e||0==f||0==g||0==h||0==i) continue;

                //排除以上情况，剩下的就是满足要求的数
                printf("%d%d%d %d%d%d %d%d%d\n", a, b, c, d, e, f, g, h, i);
            }
        }
    }
    return 0;
}

数字a只需遍历到3即可，因为超过3会使ghi成为4位数。

二、集中判重法

换一种思路，先不考虑数字有没有重复出现，而是把所有的数生成完，最后集中判断数字中是否有重复。算法也分两部分：

1．数的生成

①用一层循环生成abc（范围在123-329之间）；

②根据比例关系求出def、ghi；

③分离成a、b、c、d、e、f、g、h、i，用于下一步判重。

2．数的判重

(1)不重条件：1-9每个数字恰好使用一次。它等价于下面几种描述：

①每个数字都出现且只出现了1次。

②每个数字都出现过。如果有数字出现次数大于1，必然有其他数字没出现，所以②与①是等价的。这样就只需要判断每个数字是否都出现过，不用判断出现次数。

③任何1个数字出现的次数不能为0。

④任何1个数字出现的次数不能大于1。

下面给出按条件②的判断的代码：

#include<stdio.h>
int main(){
    int a, b, c, d, e, f, g, h, i;
    for(int abc=123; abc<=329; abc++){
        //根据abc，分别求出各个数字
        int def = 2*abc;
        int ghi = 3*abc;
        a = abc/100;
        b = abc/10%10;
        c = abc%10;
        d = def/100;
        e = def/10%10;
        f = def%10;
        g = ghi/100;
        h = ghi/10%10;
        i = ghi%10;

        //检查1-9是否都出现过
        int cnt=0;
        for(int k=1; k<=9; k++){
            if(k==a||k==b||k==c||k==d||k==e||k==f||k==g||k==h||k==i) cnt++;
        }

        //输出符合要求的数
        if(9==cnt){
            printf("%d %d %d\n", abc, def, ghi);
        }
    }
    return 0;
}

(2)重复条件：任一数字的出现次数不等于1。它等价于下面2种描述：

①任一数字的出现次数等于0。就像之前说的，任一数字的出现次数不等于1，必然会导致有数字没出现。

②任一数字的出现次数大于1。

下面给出按条件①的判断的代码：

#include<stdio.h>
int main(){
    int a, b, c, d, e, f, g, h, i;
    for(int abc=123; abc<=329; abc++){
        //根据abc，分别求出d、e、f、g、h、i
        int def = 2*abc;
        int ghi = 3*abc;
        a = abc/100;
        b = abc/10%10;
        c = abc%10;
        d = def/100;
        e = def/10%10;
        f = def%10;
        g = ghi/100;
        h = ghi/10%10;
        i = ghi%10;

        //检查是否有数字没出现过
        int flag = 1;
        for(int k=1; k<=9; k++){
            if(k!=a&&k!=b&&k!=c&&k!=d&&k!=e&&k!=f&&k!=g&&k!=h&&k!=i){
                flag = 0;
                break;
            }
        }

        //输出符合要求的数
        if(1==flag){
            printf("%d %d %d\n", abc, def, ghi);
        }
    }
    return 0;
}

最后要说明的是，本题其实用数组更简单，思路就是将num[a]、num[b]……num[i]都赋值为1，再判断num[1]到num[9]的值，如果有值为0就说明该数字没有出现过。

由于本题是第二章，还没学到数组，所以上面所给代码均未用到数组。