例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;         }     } }枚举算法的特点是算法简单，但运算量大，当问题的规模变大，循环的阶数越大，执行的速度越慢。如果枚举范围太大（一般以不超过两百万次为限），在时间上就难以承受。从全局的角度使用枚举法，计算量容易过大，在局部使用枚举法，会大大减小算法的难度。枚举算法的思路简单，程序编写和调试方便，比赛时也容易想到，在竞赛中，时间是有限的，我们竞赛的最终目标就是求出问题解，因此，如果题目的规模不是很大，在规定的时间与空间限制内能够求出解，那么我们最好是采用枚举法，而不需太在意是否还有更快的算法，这样可以使你有更多的时间去解答其他难题。

评论