枚举法，常常称之为穷举法，是指从可能的集合中一一枚举各个元素，用题目给定的约束条件判定哪些是无用的，哪些是有用的。能使命题成立者，即为问题的解。
采用枚举算法解题的基本思路：
（1）确定枚举对象、枚举范围和判定条件；
（2）一一枚举可能的解，验证是否是问题的解
下面我们就从枚举算法的的优化、枚举对象的选择以及判定条件的确定，这三个方面来探讨如何用枚举法解题。
例1：百钱买百鸡问题：有一个人有一百块钱，打算买一百只鸡。到市场一看，公鸡一只3元,母鸡一只5元,小鸡3只1元,试求用100元买100只鸡,各为多少才合适?
算法分析：此题很显然是用枚举法，我们以三种鸡的个数为枚举对象（分别设为cock, hen, chick）,以三种鸡的总数（cock + hen + chick）和买鸡用去的钱的总数(COCKPRICE*cock + HENPRICE*hen + chick/CHICKS)为判定条件，枚举各种鸡的个数。
注：我这里用了一个自定义函数Function()来解三种鸡的百钱买百鸡问题。函数提供了两个参数int money, int chooks，分别表示总钱数和总鸡数，除了把她们都赋值100外，还可以赋任意正整数值，解决x钱买y鸡问题。

#include<stdio.h>
const int COCKPRICE = 3; //一只公鸡的价格 
const int HENPRICE = 5;  //一只母鸡的价格 
const int CHICKS = 3;   //一元钱能买的小鸡数量 
void Function(int money, int chooks);//计算并输出三种鸡的数量各是多少 

int main()
{
    int money = 100;//钱的总数 
    int chooks = 100;//鸡的总数 
    
    Function(money, chooks);//计算并输出三种鸡的数量各是多少 
    getchar();
    return 0;       
}

void Function(int money, int chooks) //计算并输出三种鸡的数量各是多少 
{
    int maxCock = money / COCKPRICE;    
    int maxHen = money / HENPRICE;    
    int maxChick = chooks;        
    int cock, hen, chick;
    
    for (cock=0; cock<maxCock; ++cock)//枚举公鸡的可能数量 
    {
        for (hen=0; hen<maxHen; hen++)//枚举母鸡的可能数量
        {
            for (chick=0; chick<maxChick; chick++)//枚举小鸡的可能数量
            {
                if (0 == chick%CHICKS && cock + hen + chick == chooks 
                 && COCKPRICE*cock + HENPRICE*hen + chick/CHICKS == money)//约束条件 
                {
                    printf("cock = %2d, hen = %2d, chick = %2d\n", cock, hen, chick);
                }
            }
        }
    }
}
上面的条件还有优化的空间，三种鸡的和是固定的，我们只要枚举二种鸡（cock, hen），第三种鸡就可以根据约束条件求得（chick = chooks - cock - hen），这样就缩小了枚举范围，请看下面的程序：
void Function(int money, int chooks)//计算并输出三种鸡的数量各是多少 
{
    int maxCock = money / COCKPRICE;    
    int maxHen = money / HENPRICE;        
    int cock, hen, chick;
    
    for (cock=0; cock<maxCock; ++cock)//枚举公鸡的可能数量 
    {
        for (hen=0; hen<maxHen; hen++)//枚举母鸡的可能数量
        {
            chick = chooks - cock - hen;//小鸡的数量根据约束条件求得
            if (0 == chick%CHICKS 
            && COCKPRICE*cock + HENPRICE*hen + chick/CHICKS == money)//约束条件 
            {
                printf("cock = %2d, hen = %2d, chick = %2d\n", cock, hen, chick);
            }
        }
    }
}
未经优化的程序时间复杂度为O(n3)；优化后的程序时间复杂度为O(n2)。通过简单的优化，程序的效率大大提高，实际上如果能从数学角度来考虑优化，会得到意想不到的结果。
根据题意我们可以得到方程组：
3X + 5Y + Z/3 = 100；
X + Y + Z = 100；
（X，Y，Z > 0, Z%3 == 0）；
观察方程的特点，消去一个未知数Z：
4X + 7Y = 100；
X + Y + Z = 100；
（X，Y，Z > 0, Z%3 == 0）；
根据整理以后的方程可以得到新的程序：
#include<stdio.h>
int main()
{
    int x, y, z;
    for (y=0; y<=14; y++)//根据约束条件（方程），枚举公鸡的可能数量
    {
        x = 100 - 7 * y;
        if (x % 4)//由方程知：x = （100 - 7 * y）/ 4;x是4的倍数
            continue;
        else
            x /= 4;
        
        z = 100 - x - y;
        if (z % 3)
            continue;
        else
            printf("x = %d, y = %d, z = %d\n", x, y, z);
    }
    getchar();
    return 0;       
}
本程序虽然不如前面两个的通用性强，但不管多少钱多少鸡，我们都可以按照上面的方法对方程进行化简，从而得到对应的方程。程序时间复杂度从O(n3)到O(n2)，再到O(n)，从上面的对比可以看出，对于枚举算法，加强约束条件，缩小枚举的范围，是程序优化的主要考虑方向。

在枚举算法中，枚举对象的选择也是非常重要的，它直接影响着算法的时间复杂度，选择适当的枚举对象可以获得更高的效率。如下例：
例2. 五猴分桃：五只猴子一起摘了一堆桃子,因为太累了,它们商量决定,先睡一觉再分.一会其中的一只猴子来了,它见别的猴子没来,便将这堆桃子平均分成5份 ,结果多了一个,就将多的这个吃了,并拿走其中的一份.一会儿,第2只猴子来了,他不知道已经有一个同伴来过,还以为自己是第一个到的呢,于是将地上的桃子堆起来,再一次平均分成5份,发现也多了一个,同样吃了这1个,并拿走其中一份.接着来的第3,第4,第5只猴子都是这样做的.......,
根据上面的条件,问这5只猴子至少摘了多少个桃子?第5只猴子走后还剩下多少个桃子?
算法分析：我们设总的桃子数为S0，五子猴子分得的桃子数分别为S1，S2，S3，S4，S5，则有以下关系式：S0 = 5*S1 + 1；  4*S1 = 5*S2 + 1；  4*S2 = 5*S3 + 1；  
4*S3 = 5*S4 + 1；  4*S4 = 5*S5 + 1；  
我们可以枚举桃子总数S0，从5开始直到满足条件，此时S0的值就是最少的总桃子数。对应程序如下：
#include <stdio.h>

int main(void)
{
    int s[6] = {0};
    int i;
   
    for(s[0]=5; ;s[0]++)
    {
        s[1] = s[0] - 1;
        if (s[1]%5)  // （s[0] – 1）要能被5整除
            continue;
        else
            s[1] /= 5;
            
        s[2] = 4 * s[1] - 1;
        if (s[2]%5)  // （4 * s[1] - 1）要能被5整除
            continue;
        else
            s[2] /= 5;
        
        s[3] = 4 * s[2] - 1;
        if (s[3]%5)
            continue;
        else
            s[3] /= 5;
        
        s[4] = 4 * s[3] - 1;
        if (s[4]%5)
            continue;
        else
            s[4] /= 5;
            
        s[5] = 4 * s[4] - 1;
        if (s[5]%5)
            continue;
        else
            s[5] /= 5;
            
        break;
    }
    printf("摘了%d个桃子, 剩下%d个桃子\n", s[0], s[5]*4);
    for (i=0; i<6; i++)
        printf("%d  ", s[i]); 
       getchar();
       return 0;   
}   
程序输出：摘了3121个桃子, 剩下765个桃子。
根据程序结果我们知道循环体执行了3116次，同时我们可以知道第5个猴子分得255个桃子，所以如果枚举S5，则循环体只需执行了255次。对应程序如下：
#include <stdio.h>

int main(void)
{
    int s[6] = {0};
    int i;
   
    for(s[5]=1; ;s[5]++)
    {
        s[4] = 5 * s[5] + 1;
        if (s[4]%4)
            continue;
        else
            s[4] /= 4;
            
        s[3] = 5 * s[4] + 1;
        if (s[3]%4)
            continue;
        else
            s[3] /= 4;
        
       s[2] = 5 * s[3] + 1;
        if (s[2]%4)
            continue;
        else
            s[2] /= 4; 
        
        s[1] = 5 * s[2] + 1;
        if (s[1]%4)
            continue;
        else
            s[1] /= 4;
        
        s[0] = 5 * s[1] + 1;
        break;
    } 
    printf("摘了%d个桃子, 剩下%d个桃子\n", s[0], s[5]*4);
    getchar();
    return 0;   
}   
我们可以发现求S4，S3，S2，S1的表达式完全是一样的，所以我们可以用一个函数或者循环来表示，改进后的程序如下：
#include <stdio.h>

int main(void)
{
    int s[6] = {0};
    int i;
   
    for(s[5]=1; ;s[5]++)
    {
        for (i=4; i>0; i--)
        {
            s[i] = 5 * s[i+1] + 1;
            if (s[i]%4)
                break;
            else
                s[i] /= 4;
        }
        if (i == 0)
        {
            s[0] = 5 * s[1] + 1;
            break;
        }
    }
    printf("摘了%d个桃子, 剩下%d个桃子\n", s[0], s[5]*4);
       getchar();
       return 0;   
}

例3. 将1,2...9共9个数分成三组,分别组成三个三位数,且使这三个三位数构成1:2:3的比例,试求出所有满足条件的三个三位数.
例如:三个三位数192,384,576满足以上条件.(NOIP1998pj)
算法分析：这是1998年全国分区联赛普及组试题（简称NOIP1998pj，以下同）。此题数据规模不大，可以进行枚举，如果我们不加思地以每一个数位为枚举对象，一位一位地去枚举：
for (a=1; a<10; a++)
for (b=1; b<10; b++)
for (c=1; c<10; c++)
...
for (i=1; i<10; i++)
这样下去，枚举次数就有387420489（9的9次方）次，如果我们分别设三个数为x,2x,3x，以x为枚举对象，枚举的范围就减少为（326-123=）203次，在细节上再进一步优化，枚举范围就更少了。程序如下：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int Function(int lib[][3]);//主处理函数 

int main()
{
    int lib[100][3] = {0};
    int len = Function(lib);
    int i;
    
    for (i=0; i<len; i++)
    {
        printf("%5d%5d%5d\n", lib[i][0], lib[i][1], lib[i][2]);
}
    getchar();
    return 0;       
}

int Function(int lib[][3])//主处理函数 
{
    int len = 0;//表示lib的长度 
    int x;
    char str[10];//用来存储9个数字构成的字符串 
    char buf[4];//临时字符串，存储每组数字
    char i; 
    
    for (x=123; x<326; x++) //987/3 = 325
    {
        str[0] = '\0';
        itoa(x, buf, 10);//把整数x转换为字符串buf 
        strcat(str, buf);//添加第1组数字 
        itoa(2*x, buf, 10); 
        strcat(str, buf);//添加第2组数字 
        itoa(3*x, buf, 10); 
        strcat(str, buf);//添加第3组数字 
        
        for (i='1'; i<='9'; i++)//判断数字组合是否满足条件
        {
            if (!strchr(str, i))
                break;
        }
        if (i > '9')//如果满足则存储到lib中 
        {
            lib[len][0] = x;
            lib[len][1] = 2 * x;
            lib[len++][2] = 3 * x;
        }
    }
    return len;
}

在枚举法解题中，判定条件的确定也是很重要的，如果约束条件不对或者不全面，就枚举不出正确的结果， 我们再看看下面的例子。
例4. 一元三次方程求解(noip2001tg)
问题描述:有形如：ax3+bx2+cx+d=0  这样的一个一元三次方程。给出该方程中各项的系数(a，b，c，d  均为实数)，并约定该方程存在三个不同实根(根的范围在-100至100之间)，且根与根之差的绝对值>=1。要求由小到大依次在同一行输出这三个实根(根与根之间留有空格)，并精确到小数点后2位。
提示：记方程f(x)=0，若存在2个数x1和x2，且x1<x2，f(x1)*(x2)<0，则在(x1，x2)之间一定有一个根。
样例
输入：1   -5   -4   20    
输出：-2.00   2.00   5.00
算法分析：由题目的提示很符合二分法求解的原理，所以此题可以用二分法。用二分法解题相对于枚举法来说很要复杂很多。此题是否能用枚举法求解呢？再分析一下题目，根的范围在-100到100之间，结果只要保留两位小数，我们不妨将根的值域扩大100倍（-10000<=x<=10000），再以根为枚举对象，枚举范围是-10000到10000，用原方程式进行一一验证，找出方程的解。
有的同学在比赛中是这样做
#include<stdio.h>
void Function(double xa[], double a, double b, double c, double d);//解方程 

int main()
{
    double a = 1, b = -5, c = -4, d = 20;
    double x[3] = {0};
 
    printf("%f  %f  %f  %f\n", a, b, c, d);
    Function(x, a, b, c, d);//解方程
    printf("%.2f  %.2f  %.2f\n", x[0], x[1], x[2]);
    getchar();
    return 0;       
}

void Function(double xa[], double a, double b, double c, double d)//解方程
{
    int i;
    double x;
    int top = 0;
    
    for (i=-10000; i<=10000; i++)//将根的值域扩大100倍
    {
        x = (i * 1.0) / 100;//再变回来 
        if (((a * x + b) * x + c) * x + d == 0) //有解
        {
            xa[top++] = x;
        }
    }
}
用这种方法，很快就可以把程序编出来，再将样例数据代入测试也是对的，等成绩下来才发现这题没有全对，只得了一半的分。
这种解法为什么是错的呢？错在哪里？前面的分析好象也没错啊，难道这题不能用枚举法做吗？ 看到这里大家可能有点迷惑了。在上面的解法中，枚举范围和枚举对象都没有错，而是在验证枚举结果时，判定条件用错了。因为要保留二位小数，所以求出来的解不一定是方程的精确根，再代入ax3+bx2+cx+d中，所得的结果也就不一定等于0，因此用原方程ax3+bx2+cx+d=0作为判断条件是不准确的。
我们换一个角度来思考问题，设f(x)=ax3+bx2+cx+d，若x为方程的根，则根据提示可知，必有f(x-0.005)*(x+0.005)<0，如果我们以此为枚举判定条件，问题就逆刃而解。另外，如果f(x-0.005)=0，或f(x+0.005)=0，那么就说明（x-0.005）或（x+0.005）是方程的根，这时根据四舍5入，方程的根也为x。所以我们用(f(x-0.005)*f(x+0.005)<=0)作为判定条件。为了程序设计的方便，我们设计一个函数F(x)计算ax3+bx2+cx+d的值，看程序：
double F(double a, double b, double c, double d, double x)//函数表达式 
{
    return ((a * x + b) * x + c) * x + d;
}

void Function(double xa[], double a, double b, double c, double d)
{
    int i;
    double x;
    int top = 0;
    
    for (i=-10000; i<=10000; i++)//将根的值域扩大100倍
    {
        x = (i * 1.0) / 100;//再变回来 
        if (F(a, b, c, d, x-0.005)*F(a, b, c, d, x+0.005) <= 0) //有解
        {
            xa[top++] = x;
        }
    }
}
枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。从全局的角度使用枚举法，计算量容易过大，在局部使用枚举法，会大大减小算法的难度。枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。

经典例题：
    b1    
b2    b3    b4
b5    b6    b7
    b8    
例5.  如图所示的8个格子中放入1～8八个数字，使得相邻的和对角线的数字之差不为1。编程找出所有放法。




我们先不考虑后一条件，只考虑第一个条件，即把1～8八个数字放入8个格子中。这是容易做到的，就是8个数字的全排列，共有 8!=40320种放法。然后对这8!个可行解用后一个条件加以检验，输出符合条件的解。全排列的产生，可以用八重循环，也可以用专门的算法，程序留给同学们自己去完成。
     利用枚举策略编制的程序，其运算量一般是很大的，因此如何提高算法效率是枚举算法一个很重要的问题。一般应尽量减少可行解的个数，使得第二步的检验运算量尽可能地少。
那么如何来优化算法呢?如果注意到b3和b6两个格子，与它们“相邻”的格子有6个，也就是说，放入这两个格子中的数，必须和6个数不连续，仅可以和一个数是连续的，这样的数只有2个，即1和8。这样，b1，b3，b6，b8 4个格子中数的放法仅有两种可能：2、8、1、7和7、1、8、2。而b2、b4、b5、b7四个格子中的数仅需在3～6四个数中选择。经过上述优化，可行解仅有：2×4！＝ 48个，大大减少了计算量。并且检验是否符合要求，也只需检查(b1，b2)，(b1，b4)，(b2，b5)，(b4，b7)，(b5，b8)，(b7，b8)这6对数之差就可以了。
#include<stdio.h>

int main()
{
    int a[4] = {3, 4, 5, 6};//存储在b1，b3，b6，b8 4个格子中的数 
    int b[9] = {0};//为了符合人门的阅读习惯b的下标从1开始 
    int i, j, k;
    int flag;
    
    for (flag=0; flag<2; flag++)
    {
        if (flag == 0)//b1，b3，b6，b8 4个格子中数的放法仅有两种可能
        {
            b[1] = 2;
            b[3] = 8;
            b[6] = 1;
            b[8] = 7;
        }
        else
        {
            b[1] = 7;
            b[3] = 1;
            b[6] = 8;
            b[8] = 2;
        }
        
        for (i=0; i<4; i++)//枚举b2、b4、b5、b7四个格子中的数 
        {
            b[2] = a[i];
            for (j=0; j<4; j++)
            {
                b[4] = a[j];
                if (b[4] != b[2])
                {
                    for (k=0; k<4; k++)
                    {
                        b[5] = a[k];
                        if (b[5] != b[2] && b[5] != b[4])
                        {
                            b[7] = 36 - 18 - b[2] - b[4] - b[5];//根据约束条件可知b7的值 
                            if (abs(b[1]-b[2])!=1 && abs(b[1]-b[4])!=1 && abs(b[2]-b[5])!=1
                             && abs(b[4]-b[7])!=1 && abs(b[5]-b[8])!=1 && abs(b[7]-b[8])!=1)
                            {
                                printf("   %d\n", b[1]);
                                printf("%d  %d  %d\n", b[2], b[3], b[4]);
                                printf("%d  %d  %d\n", b[5], b[6], b[7]);
                                printf("   %d\n", b[8]);
                                printf("\n\n");
                            }
                        }
                    }
                }
            }
        }
    }
    getchar();
    return 0;       
}
上面优化算法的方法是尽可能减少可行解的数目，也称为“剪枝”，即把明显不符合条件的可行解尽可能地剪去，减少枚举的计算量。

例6.  邮票问题。邮局发行一套票面有4种不同值的邮票，如果限制每封信所贴的邮票张数不能超过3枚。存在整数r，使得用不超过3枚的邮票，可以贴出以下序列的整数值：
 1，2，3，…，r。
    例如，面值为1、4、5、9的4种邮票，不超过3张可以贴出：1，1+ 1＝2，1＋1＋1＝3，4，5，1＋5＝6，1+1+5=7，4+4=8，9，1+9=10。 1＋1＋9＝11，4＋4＋4＝12，4＋9＝13，5+9＝14，5＋5＋5＝15等15个连续整数值，虽然有4+4+9=17，但因为16这个数无法贴出，所以最大值是r=15。
    编程求出可以得到尽可能大的r值的邮票面值。
算法分析：因为题目中邮票数是有限的(4)，所以可以用枚举算法来解。设四种邮票面值分别为p1，p2，p3和p4。
#include<stdio.h>
int MaxValue(int p1, int p2, int p3, int p4);

int main()
{
    int p1 = 1, p2 = 4, p3 = 5, p4 = 9;
    
    printf("max = %d\n", MaxValue(p1, p2, p3, p4));
    getchar();
    return 0;       
}

int MaxValue(int p1, int p2, int p3, int p4)
{
    int t1, t2, t3, t4;
    int len = 3*p4 + 1;
    int i;
    int *a = (int *)malloc(sizeof(int)*len);//数组用来存储各种可能存在的票额，根据邮票票额的最大值为数组动态分配空间 
    memset(a, 0, sizeof(int)*len);//设定初值为0 
    
    for (t1 = 0; t1 < 4; t1++)//枚举每种邮票的数量 
    {
        for (t2 = 0; t2 < 4; t2++)
        {
            for (t3 = 0; t3 < 4; t3++)
            {
                for (t4 = 0; t4 < 4; t4++)
                {
                    if (t1+t2+t3+t4 <= 3) 
                    {
                        a[t1*p1+t2*p2+t3*p3+t4*p4] = 1;//存储可能的票额 
                    }
                }
            }
        }
    }
    
    for (i=0; i<len; i++)
    {
        if (a[i] == 0)//若某种票额未出现，则其前面的票额值为所求值 
            return i - 1;
    }
    return i - 1;
}
枚举算法是用计算机解题常用的算法，可以说是用计算机解决问题的一种特色。最典型的例子是四色定理的证明。人们早已从理论上找到一种证明四色定理的方法，但这种方法需作上亿次的判断和检验，用人工力量是完全不可能的。只有高速、大型计算机出现后，才真正获得了证明。
    搜索法，例如深度优先搜索法、广度优先搜索法等，也属于枚举算法的范畴，它们将在后面详细地讨论，这里就不再赘述。

练习：
1．元旦义卖：总共带50件商品，有两种构成，钥匙扣2块一个，漫画书4块一本，要卖出160块要如和搭配？

2．构造一个3*3的魔方：把数字1-9添入如图的表格中
2    7    6
9    5    1
4    3    8
要求每横，竖，斜列之和均相等（如图是一种情况）。输出所有可能的魔方。

3. 虫食算: 所谓虫食算，就是原先的算式中有一部分被虫子啃掉了，需要我们根据剩下的数字来判定被啃掉的字母。来看一个简单的例子： 
43#9865#045 
+ 8468#6633 
____________
44445509678 
其中#号代表被虫子啃掉的数字。根据算式，我们很容易判断：第一行的两个数字分别是5和3，第二行的数字是5。
现在，我们对问题做两个限制： 
首先，我们只考虑10进制加法的虫食算。
其次，虫子把所有的数都啃光了，我们只知道哪些数字是相同的，我们将相同的数字用相同的字母表示，不同的数字用不同的字母表示。
给定等式  A B C D E
              D F G
        +     D F G
       ───────
          X Y Z D E
其中每个字母代表一个数字，且不同数字对应不同字母。编程求出这些数字并且打出这个数字的算术计算竖式。

参考答案：
1．#include<stdio.h>

const int KEYPRICE = 2; //一个钥匙扣的价格 
const int BOOKPRICE = 4;  //一本漫画书的价格 

void Print(int money, int res);//计算并输出两种物品的数量各是多少 

int main()
{
    int money = 160;//钱的总数 
    int res = 50;//物品的总数 
    
    Print(money, res);//计算并输出两种物品的数量各是多少
    
    getchar();
    return 0;       
}

void Print(int money, int res)
{
    int maxKey = money / KEYPRICE;            
    int key, book;
    
    for (key=0; key<maxKey; ++key)//枚举钥匙扣的可能数量 
    {
        book = res - key;//漫画书的数量根据约束条件求得
        if (key*KEYPRICE + book*BOOKPRICE == money)//约束条件 
        {
            printf("key = %d, book = %d\n", key, book);
        }
    }
}

2．参考程序一：九重循环，不做任何剪枝。
#include<stdio.h>
#include<stdlib.h>

int Different(int a[], int len);

int main()
{
    int a[9] = {0};
    int i;
    
    for (a[0]=1; a[0]<=9; a[0]++)
    for (a[1]=1; a[1]<=9; a[1]++)
    for (a[2]=1; a[2]<=9; a[2]++)
    for (a[3]=1; a[3]<=9; a[3]++)
    for (a[4]=1; a[4]<=9; a[4]++)
    for (a[5]=1; a[5]<=9; a[5]++)
    for (a[6]=1; a[6]<=9; a[6]++)
    for (a[7]=1; a[7]<=9; a[7]++)
    {
        if (Different(a, 8))
        {
            a[8] = 45-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7];
            if ((a[0]+a[1]+a[2]) == (a[3]+a[4]+a[5]) && (a[0]+a[1]+a[2]) == (a[6]+a[7]+a[8])
             && (a[0]+a[3]+a[6]) == (a[1]+a[4]+a[7]) && (a[0]+a[3]+a[6]) == (a[2]+a[5]+a[8])
             && (a[0]+a[1]+a[2]) == (a[0]+a[4]+a[8]) && (a[0]+a[1]+a[2]) == (a[2]+a[4]+a[6]))
            {
                for (i=0; i<9; i++)
                {
                    printf("%5d", a[i]);
                    if ((i+1)%3 == 0)
                        printf("\n");
                }
                printf("\n\n");
            }
        }
    }
    
    system("pause");
    return 0;       
}

int Different(int a[], int len)
{
    int i, j;
    for (i=0; i<len-1; i++)
    {
        for (j=i+1; j<len; j++)
        {
            if (a[i] == a[j])
                return 0;
        }
    }
   
    return 1;
}

参考程序二：八重循环，对每重循环均进行剪枝。
#include<stdio.h>
#include<stdlib.h>

int IsElement(int a[], int len, int x);

int main()
{
    int a[9] = {0};
    int i;
    
    for (a[0]=1; a[0]<=9; a[0]++)
    for (a[1]=1; a[1]<=9; a[1]++)
    {
    if (IsElement(a, 1, a[1]))
    {
    for (a[2]=1; a[2]<=9; a[2]++)
    {
    if (IsElement(a, 2, a[2]))
    {
    for (a[3]=1; a[3]<=9; a[3]++)
    {
    if (IsElement(a, 3, a[3]))
    {
    for (a[4]=1; a[4]<=9; a[4]++)
    {
    if (IsElement(a, 4, a[4]))
    {
    for (a[5]=1; a[5]<=9; a[5]++)
    {
    if (IsElement(a, 5, a[5]))
    {
    for (a[6]=1; a[6]<=9; a[6]++)
    {
    if (IsElement(a, 6, a[6]))
    {
    for (a[7]=1; a[7]<=9; a[7]++)
    {
    if (IsElement(a, 7, a[7]))
    {
    a[8] = 45-a[0]-a[1]-a[2]-a[3]-a[4]-a[5]-a[6]-a[7];
    if ((a[0]+a[1]+a[2]) == (a[3]+a[4]+a[5]) && (a[0]+a[1]+a[2]) == (a[6]+a[7]+a[8])
     && (a[0]+a[3]+a[6]) == (a[1]+a[4]+a[7]) && (a[0]+a[3]+a[6]) == (a[2]+a[5]+a[8])
     && (a[0]+a[1]+a[2]) == (a[0]+a[4]+a[8]) && (a[0]+a[1]+a[2]) == (a[2]+a[4]+a[6]))
    {
        for (i=0; i<9; i++)
        {
            printf("%5d", a[i]);
            if ((i+1)%3 == 0)
                printf("\n");
        }
        printf("\n\n");
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    }
    system("pause");
    return 0;       
}

int IsElement(int a[], int len, int x)
{
    int i;
    for (i=0; i<len; i++)
    {
        if (a[i] == x)
            return 0;
    }
   
    return 1;
}

3．算法分析：先看最高位和次高位， A, B都是和进位相加，又C+D+D的进位（设为j）不可能大于2，B+j的进位不能大于1，所以B = 9; Y = 1; X = A + 1;
E+G+G的个位数字仍为E，说明G=0或G=5；同理 F=0或F=5；
做了这些简单的判断以后，可以大大提高穷举的效率。
#include<stdio.h>

int main()
{
    int A, B, C, D, E, F, G, X, Y, Z;
    int m, n, sum;
    
    B = 9;
    Y = 1;
    for (G=0; G<6; G+=5)
        for (F=0; F<6; F+=5)
        if (F!=G)
            for (A=2; A<9; A++)
            if (A!=G && A!=F)
                for (C=2; C<9; C++)
                if (C!=A && C!=G && C!=F)
                    for (D=2; D<9; D++)
                    if (D!=A && D!=C && D!=G && D!=F)
                        for (E=2; E<9; E++)
                        if (E!=A && E!=C && E!=D && E!=G && E!=F)
                        {
                            X = A + 1;
                            if (B!=X && C!=X && D!=X && E!=X && F!=X && G!=X)
                            {
                                Z = 45 - A - B - C - D - E - F - G - X - Y;
                                
                                m = A*10000 + B*1000 + C*100 + D*10 + E;
                                n = D*100 + F*10 + G;
                                sum = X*10000 + Y*1000 + Z*100 + D*10 + E;
                                    
                                if (m + n * 2 == sum)
                                {
                                    printf(" %d%d%d%d%d\n", A, B, C, D, E);
                                    printf("   %d%d%d\n", D, F, G);
                                    printf("+  %d%d%d\n", D, F, G);
                                    printf("_____________\n");
                                    printf(" %d%d%d%d%d\n", X, Y, Z, D, E);
                                    printf("\n");
                                }    
                            }
                        }
    getchar();
    return 0;
}

先顶后看

先顶后看

谢谢分享程序的精髓