用穷举法的设计算法.ppt

【例7】: (四大湖问题)上地理课时，四个学生回答我国四个淡水湖大小时说： 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 (3) 穷举: 穷举a,b,c,d四个变量的所有可能取值,进行测试，满足前述四个条件的取值就是我们所要的结果 【例8】（白帽子和红帽子问题）厅内有5个人，他们均戴着帽子－白帽子和红帽子。已知戴白帽子的说真话，戴红帽子的说假话，请从他们各自提供的线索辨别谁戴白帽子，谁戴红帽子。 甲：我看见一个戴白帽子的 乙：我没有看见戴红帽子的 丙：我看见一个戴白帽子的，但不是甲 丁：我没有看见戴白帽子的 戊：我的帽子和丙一样 ⑴ 定义变量 用5个整型变量a,b,c,d,e分别表示甲、乙、丙、丁、戊，1表示戴白帽子，0表示戴红帽子。 ⑵ 写出五个人所说的每句话的逻辑表达式 甲：(b+c+d+e==1) 乙：(a+c+d+e==4) 丙：(b+d+e==1) 丁：(a+b+c+e==0) 戊：(e==c) 这里只是简单地将五个人说的话写成了表达式，但这还不够，由于这五个人本身有些说真话，有些说假话，因此如何判断上述五个表达式的真假呢？ 思考：每个人说话的真假与他所戴的帽子有关，如果他戴的是白帽子，则他说真话；如果他戴的是红帽子，则他所说的是假话，这样将每个人帽子颜色与他说的话直接联系起来，因此上述条件可表示成： 甲：(b+c+d+e==1)==a 乙：(a+c+d+e==4)==b 丙：(b+d+e==1)==c 丁：(a+b+c+e==0)==d 戊：(e==c)==e void main() { int a,b,c,d,e,c1,c2,c3,c4,c5; for(a=0;a=1;a++) for(b=0;b=1;b++) for(c=0;c=1;c++) for(d=0;d=1;d++) for(e=0;e=1;e++) { c1=(b+c+d+e==1)==a; c2=(a+c+d+e==4)==b; c3=(b+d+e==1)==c; c4