穷举法(枚举法)实例解析

2021年9月17日 13点热度 0条评论 来源: 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)算法

    原文作者:qq_44831918
    原文地址: https://blog.csdn.net/qq_44831918/article/details/108407444
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。