穷举算法程序设计.pptVIP

2.12 穷举法程序设计 采用穷举算法解题的基本思想： （1） 明确问题要求，确定枚举对象，用合适类型的变量表示枚举对象。 （2） 明确枚举对象的取值范围。 （3） 根据题目要求，写出有关的条件表达式。这里条件表达式可以是数学表达式、关系表达式或逻辑表达式； （4） 使用循环语句枚举出可能的解，在循环体内验证各种条表达式是否满足； （5） 根据问题背景，优化程序，以便缩小有哪些信誉好的足球投注网站范围，减少程序运行时间。 逻辑推理问题 逻辑推理问题 1.算法分析 将相关的陈述写成关系表达式和逻辑表达式 ⑴我们把四个人说的四句话写成关系表达式。定义变量thisman表示做好事的人（将其定义为字符型）。 for(thisman=’A’;thisman=’D’;thisman++) { cond=(thisman!=‘A’)+(thisman==‘C’) +(thisman==‘D’)+(thisman!=‘D); if(cond==3) printf(做好事的人是：%C\n,thisman); } #includestdio.h void main() { char thisman; int cond; for(thisman=A; thisman=D;thisman++) { cond=(thisman!=‘A’)+(thisman==‘C’) +(thisman==‘D’)+(thisman!=‘D); if(cond==3) 　　printf(做好事的人是：%C\n,thisman); } } 【例】: (四大湖问题)上地理课时，四个学生回答我国四个淡水湖大小时说： A学生：洞庭湖最大，洪泽湖最小，鄱阳湖第3 B学生：洪泽湖最大，洞庭湖最小，鄱阳湖第2，太湖第3 C学生：洪泽湖最小，洞庭湖第3 D学生：鄱阳湖最大，太湖最小，洪泽湖第2，洞庭第3 对于湖的大小，每个学生仅答对一个，请编程判断四个湖的大小 1.分析与算法设计 (1)定义变量： a—洞庭湖，a可能的取值{1,2,3,4} b—洪泽湖，b可能的取值{1,2,3,4} c—鄱阳湖，c可能的取值{1,2,3,4} d—太湖，　d可能的取值{1,2,3,4} 　a,b,c,d四个变量的取值互不相同，1表示最大，四表最小 (2) 用变量表示条件 A学生的叙述可表示为：a==1, b==4,c==3 这是三个关系表达式，由于每个学生的叙述只有一个正确，所以这三个关系表达式的值的和应等于1。 A学生的叙述可表示成： 　 ( (a==1)+(b==4)+(c==3）)==1　 　　 同理，B学生的叙述表示成： 　 ((b==1)+(a==4)+(c==2)+(d==3))==1　　　　 C学生的叙述可表示成： 　 ((b==4)+(a==3)) ==1 D学生的叙述可表示成： 　 ((c==1)+(d==4)+(b==2)+(a==3))==1 　for(a=1;a=4;a++) for(b=1;b=4;b++) for(c=1;c=4;c++) for(d=1;d=4;d++) { ca=((a==1）+（b==4）+(c==3）)==1; cb=((b==1)+(a==4)+(c==2)+(d==3))==1; cc=((b==4)+(a==3) )==1; cd=((c==1)+(d==4)+(b==2)+(a==3))==1; if(ca cb cc cd) { printf(TongTing=%d\n,a); 　 　 printf(Hongzhe=%d\n,b); printf(Poyang=%d\n,c); 　　　　 printf(Taihu=%d\n,d); } }//end for 【例】（白帽子和红帽子问题）厅内有5个人，他们均戴着帽子－白帽子和红帽子。已知戴白帽子的说真话，戴红帽子的说假话，请从他们各自提供的线索辨别谁戴白帽子，谁戴红帽子。 甲：我看见一个戴白帽子的 乙：我没有看见戴红帽子的 丙：我看见一个戴白帽子的，但不是甲