枚举算法
枚举算法是我们在日常中使用到的最多的一个算法,它的核心思想就是:枚举所有的可能。
1、简介
枚举算法简单粗暴,他暴力的枚举所有可能,尽可能地尝试所有的方法。虽然枚举算法非常暴力,而且速度可能很慢,但确实我们最应该优先考虑的!因为枚举法变成实现最简单,并且得到的结果总是正确的。
在实际问题中,有些变量的取值被限定在一个有限的范围内。例如,一个星期内只有七天,一年只有十二个月,一个班每周有六门课程等等。如果把这些量说明为整型,字符型或其它类型显然是不妥当的。为此,C语言提供了一种称为“枚举”的类型。在“枚举”类型的定义中列举出所有可能的取值,被说明为该“枚举”类型的变量取值不能超过定义的范围。应该说明的是,枚举类型是一种基本数据类型,而不是一种构造类型,因为它不能再分解为任何基本类型。
2、满足条件
枚举法的本质就是从所有候选答案中去搜索正确的解,使用该算法需要满足两个条件:(1)可预先确定候选答案的数量;(2)候选答案的范围在求解之前必须有一个确定的集合。
3、定义
枚举的定义枚举类型定义的一般形式为:
enum枚举名
{枚举值表};
在枚举值表中应罗列出所有可用值。这些值也称为枚举元素。
例如:enumweekday
{sun,mou,tue,wed,thu,fri,sat};
该枚举名为weekday,枚举值共有7个,即一周中的七天。凡被说明为weekday类型变量的取值只能是七天中的某一天。
4、基本思想
枚举也称作穷举,指的是从问题所有可能的解的集合中一一枚举各元素。
用题目中给定的检验条件判定哪些是无用的,哪些是有用的。能使命题成立。即为其解。
5、基本框架
设ai1—状态元素ai的最小值;aik—状态元素ai的最大值(1≤i≤n),即a11≤a1≤a1k,a21≤a2≤a2k,ai1≤ai≤aik,……,an1≤an≤ank
fora1←a11toa1kdo
fora2←a21toa2kdo
……………………
forai←ai1toaikdo
……………………
foran←an1toankdo
if状态(a1,…,ai,…,an)满足检验条件
then输出问题的解;
6、优缺点
优点:算法简单,在局部地方使用枚举法,效果十分的好
缺点:运算量过大,当问题的规模变大的时候,循环的阶数越大,执行速度越慢
7、说明
如同结构和联合一样,枚举变量也可用不同的方式说明,即先定义后说明,同时定义说明或直接说明。设有变量a,b,c被说明为上述的weekday,可采用下述任一种方式:
enumweekday
{
......
};
enumweekdaya,b,c;或者为:enumweekday
{
......
}a,b,c;或者为:enum
{
......
}a,b,c;
8、使用
枚举类型在使用中有以下规定:
枚举值是常量,不是变量。不能在程序中用赋值语句再对它赋值。例如对枚举weekday的元素再作以下赋值:sun=5;mon=2;sun=mon;都是错误的。
枚举元素本身由系统定义了一个表示序号的数值,从0开始顺序定义为0,1,2…。如在weekday中,sun值为0,mon值为1,…,sat值为6。
例如:
#include
intmain()
{
enumweekday{sun,mon,tue,wed,thu,fri,sat};
weekdaya,b,c;//将a,b,c定义为枚举变量
a=sun;
b=mon;
c=tue;
printf("%d,%d,%d",a,b,c);
return0;
}
运行结果为:0,1,2
枚举值也可以用来做判断比较。如:if(mon>sun)…
枚举变量的值可以由程序员自己定。如:
enumweekday{sun=7,mon=1,tue,wed,thu,fri,sat};
定义sun为7,mon为1,以后按顺序加1,即wed=3。
9、赋值
只能把枚举值赋予枚举变量,不能把元素的数值直接赋予枚举变量。如:a=sum;b=mon;是正确的。而:a=0;b=1;是错误的。如一定要把数值赋予枚举变量,则必须用强制类型转换,如:a=(enumweekday)2;其意义是将顺序号为2的枚举元素赋予枚举变量a,相当于:a=tue;还应该说明的是枚举元素不是字符常量也不是字符串常量,使用时不要加单、双引号。
main(){
enumbody
{a,b,c,d}month,j;
inti;
j=a;
for(i=1;i
month=j;
j++;
if(j>d)j=a;
}
for(i=1;i
switch(month)
{
casea:printf("%2d%c\t",i,'a');break;
caseb:printf("%2d%c\t",i,'b');break;
casec:printf("%2d%c\t",i,'c');break;
cased:printf("%2d%c\t",i,'d');break;
default:break;
}
}
printf("\n");
}