枚举法是一种比较“笨”的算法思想,在面对问题时它会尝试每一种情况。打一个比方,假设有两个小朋友A和B在玩做迷藏的游戏,规定只能藏在树上、屋顶上和墙角。A比较聪明,他在找到之前会先考虑B恐高,所以他推测B只能藏在角落处;而B比较笨,他不会考虑A会不会爬树,它会随便找一个地方,如果发现这个地方没有,他会去寻找另外一个地方。如果可以藏的地方有多个,B会挨个地方寻找,直到找到A为止。上述B挨个地方寻找的做法就和枚举法算法思想的原理一样。
工具/原料
枚举法的解题思路
1枚举算法的思想:将问题的所有可能答案一一列举,然后根据条件判断此答案是否符合条件,保留合适的,丢弃不合适的。使用枚举法算法解题的基本思路如下所示。
枚举法的解题步骤
1题解的可能范围不能遗漏任何一个真正解,也要避免有重复。
3试可能解得范围降至最小,以便提高解决问题的效率。
实例
2在下面的算式中,添加“+”、“-”、“x”、“÷“4个运算符,使这个等式成立。5 5 5 5 5=5END
实例算法分析
上述算式由5个数字构成,一共需要填入4个运算符。根据题目要求,知道每两个数字之间的运算符只能有4种选择,分别是“+”“-”“x”“÷”。在具体编程时,可以通过循环来填入各种运算符,然后在判断算式是否成立。并且保证当填入除号时,其右侧的数不能是0,并且“x”“÷”运算符的优先级高于“+”、“-”。
实例程序编写参考
#includeint main(){ int j; //设置循环变量 int i[5]; //表示4个运算符 int num[6]; // 表示输入的5个数据 int result; // 表示最终验证的结果值 int sign; // 加减运算时的符号 int count=0; // 统计一共有多少种符合的式子 float left,right; // left表示左边的值,也就是算加减法时的值,right表示右边的值,也就是运算时下一个数的值 char oper[5]={' ','+','-','*','/'}; //表示运算符 printf('请输入5个数的值\n'); for(j=1;j<=5;j++) scanf('%d',&num[j]); printf('请输入结果值是\n'); scanf('%d',&result); for(i[1]=1 ; i[1]<=4 ; i[1]++) //循环4种运算符,i[1]=1时,由下面的oper[i[1]]可知表示+号,因此,在这里面,1表示+,2表示-,3表示*,4表示/ { if( (i[1]<4) || (num[2]!=0) ) //运算符等于4时,也就是为除号时,它后面的数不能为零;如果后面的为零,则前面的运算符不能为除号 { for(i[2]=1;i[2]<=4;i[2]++) { if((i[2]<4) || (num[3]!=0)) { for(i[3]=1;i[3]<=4;i[3]++) { if((i[3]<4) || num[4]!=0) { for(i[4]=1;i[4]<=4;i[4]++) { if((i[4]<4)||num[5]!=0) { left=0; //设置最开始的数值为0 right=num[1]; //设置右边的数,也就是下一个数是多少,这里设置为5个中数的第一个数 sign=1; //运算时符号初始化为正值,用1来表示 for(j=1;j<=4;j++) { switch(oper[i[j]]) //判断运算符 { case '+': left=left+sign*right; //加减法时的值 right=num[j+1]; //下一个数的值 sign=1; break; case '-': left=left+sign*right; right=num[j+1]; sign=-1; //实现减法 break; case '*': right=right*num[j+1]; //实现乘法,优先级为*高于+-,所以先算右边的数 break; case '/': right=right/num[j+1]; //实现除法 break; } } if(left+sign*right==result) //将左边的数和右边的数相加就是最终值,看与验证值是否相等 { count++; printf(' 第%d个成立的等式: ',count); for(j=1;j<=4;j++) printf('%d%c',num[j],oper[i[j]]); //输出这些数和运算符 printf('%d=%d\n',num[5],result); //输出第5个数和验证值 //此部分输出符合条件的完整表达式 } } } } } } } } } if(count==0) //说明没有符合的,count不变,输出无 printf('没有符合的等式!!!\n'); return 0;}END
方法/步骤7
注意事项
1也许有很多读者觉得枚举有点“笨”,很多人称其为“暴力算法”:但是枚举法却又总是我们面对算法问题时最先被想起的
2用枚举法解题的最大缺点是运算量比较大,解题效率不高。如果枚举范围太大(一般以不超过200万次为限),则由于效率低的问题而会在时间上难以承受
3在任何情况下,都需要选准最合适的对象,无论是枚举还是其他的算法思想,只是最关键的!