例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;
}
}
}
评论