当前位置 博文首页 > qq_44831918的博客：穷举法(枚举法)实例解析
生活中我们常常会遇到很多看似简单，却比较繁琐的问题。例如写出1000以内的素数集合，破解三位数密码的无数次尝试等比较繁琐的工作，但是计算机处理这类反反复复的作业，却比较轻松。
充分利用计算机运算速度快、精确度高的特点，对要解决问题的所有可能情况，一个不漏地进行检验，从中找出符合要求的答案，这也就是我们所说的枚举法，或者叫做穷举法。
穷举法的运用确实比较广泛，但是我们要充分明确穷举法运用的实际条件：
1、循环条件；
2、穷举对象；
3、穷举算法
接下来，让我们进入实际例题中，充分明确穷举法的运用：
有蜘蛛、蜻蜓、蝉三种动物共有18只，共有腿118条，翅膀20对。问蜘蛛、蜻蜓、蝉三种动物各有多少只？(蜘蛛又8条腿；蜻蜓有6条腿，两对翅膀；蝉有6条腿，一对翅膀)
分析如下：
首先我们确定三种动物的实际数量，决定循环次数。对三种动物各进行一次循环，实现三次嵌套循环。其次，就是填充判断条件。
(1)确定循环次数：
for(x=0;x<18;x++) //蜘蛛的总数不能超过18只
for(y=0;y<18;y++) //蜻蜓的总数不能超过18只
for(z=0;z<18;z++) //蝉的总数不能超过18只
(2)循环嵌套：
for(x=0;x<18;x++) //蜘蛛的总数不能超过18只
for(y=0;y<18;y++) //蜻蜓的总数不能超过18只
for(z=0;z<18;z++) //蝉的总数不能超过18只
(3)判断条件：
if((x+y+z)==18 && (8*x+6*y+6*z)==118 && (2*y+z)==20)
(4)总体代码如下：
#include<stdio.h>
void Count();
int main()
{
Count();
return 0;
}
void Count()
{
int x,y,z;
for(x=0;x<18;x++) //蜘蛛的总数不能超过18只
for(y=0;y<18;y++) //蜻蜓的总数不能超过18只
for(z=0;z<18;z++) //蝉的总数不能超过18只
{
if((x+y+z)==18 && (8*x+6*y+6*z)==118 && (2*y+z)==20) //判断条件
{
printf("x=%d,y=%d,z=%d\n",x,y,z);
}
}
}
(5)运行结果：
(6)结果分析：
从循环的分析，每一种的动物都进行了三次循环，极大地增加了时间复杂度。
(1)确定循环次数
for(x=0;x<14;x++) //蜘蛛的总数不能超过14只
for(y=0;y<10;y++) //蜻蜓的总数不能超过10只
for(z=0;z<18;z++) //蝉的总数不能超过18只
(2)判断条件
if((x+y+z)==18 && (8*x+6*y+6*z)==118 && (2*y+z)==20)
(3)总体代码如下：
#include<stdio.h>
void Count();
int main()
{
Count();
return 0;
}
void Count()
{
int x,y,z;
for(x=0;x<14;x++) //蜘蛛的总数不能超过14只
for(y=0;y<10;y++) //蜻蜓的总数不能超过10只
for(z=0;z<18;z++) //蝉的总数不能超过18只
{
if((x+y+z)==18 && (8*x+6*y+6*z)==118 && (2*y+z)==20) //判断条件
{
printf("x=%d,y=%d,z=%d\n",x,y,z);
}
}
}
(4)运行结果：
(5)结果分析：
从循环的分析，每一种的动物都进行了内外三次循环，但是第二种方法的循环次数有所减少，间接减少了时间的效率问题。
总结：
通过以上两种方法解决问题，我们知道这两种方法的效率明显不同。特别是第一种方法，时间的效率低于第二种方法。
穷举需要注意以下几个要点：
(1)循环次数分析
(2)判断条件要充分利用
(3)算法
