程序设计基础-chap04--逻辑思维2课件.ppt

1、课前思考题课前思考题图片中的事、物，哪些与程序设计无关？图片中的事、物，哪些与程序设计无关？都江堰都江堰逻辑问题及其解法某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析：某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析：A、B 至少有一人作案；至少有一人作案；A、E、F 三人中至少有两人参与作案；三人中至少有两人参与作案；A、D 不可能是同案犯；不可能是同案犯；B、C 或同时作案，或与本案无关；或同时作案，或与本案无关；C、D 中有且仅有一人作案；中有且仅有一人作案；如果如果 D 没有参与作案，则没有参与作案，则 E 也不可能参与作案。也不可能参与作案。试编一程序，将作案人找出来。试编一程序，将作

2、案人找出来。任务 4.2为解此题，我们要研究逻辑运算符逻辑表达式1、逻辑与，运算符为、逻辑与，运算符为&B A A&B 变量变量A 表示开关表示开关A是否是否合上；合上；变量变量B 表示开关表示开关B是否是否合上；合上；若取值为若取值为0 0：表示开关未合上；：表示开关未合上；若取值为若取值为1 1：表示开关合上。：表示开关合上。逻辑运算式逻辑运算式 A&B 表示灯表示灯是否点是否点亮；亮；结果为结果为0：灯熄灭；：灯熄灭；结果为结果为1：灯点亮。：灯点亮。1 表示真，0 表示假，这是逻辑变量的取值，非真即假ABA&B1111000100002 2、逻辑或，运算符为、逻辑或，运算符为|变量变量

3、A 表示开关表示开关A开开合合状态状态；变量变量B 表示开关表示开关B开开合上合上状态状态；取值为取值为0：开关断开；：开关断开；1：开关合上。：开关合上。运算式运算式A|B 表示灯表示灯是否点是否点亮；亮；结果为结果为0：灯熄灭；：灯熄灭；1：灯点亮。：灯点亮。B A A|B 1 1 表示真，表示真，0 0 表示假表示假ABA|B1111010110003 3、逻辑非，运算符为、逻辑非，运算符为 !示例：示例：n两队比赛篮球，变量两队比赛篮球，变量 A A 表示表示 A A 队到场，队到场，!A!A 表示表示 A A 队不到场；变量队不到场；变量 B B 表示表示 B B 队到队到场，场，!

4、B!B 表示表示 B B 队不到场。队不到场。n若要这场球赛能赛成，则两队都得到场。若要这场球赛能赛成，则两队都得到场。n若用若用C C表示表示“能赛成能赛成”（事件），则（事件），则C=A&BC=A&B若若D D 表示赛不成表示赛不成，则则：（1 1）赛不成赛不成，当然用当然用 !C!C 表示，表示，D=!C D=!C，（2 2）也可以：）也可以：D=!A|!BD=!A|!B 其含义是：其含义是：A A 不到场不到场或或 B B 不到场不到场，导致导致球赛无法进行。球赛无法进行。思考为什么：思考为什么：!C=!(A&B)=!A|!B!C=!(A&B)=!A|!B1、案情分析：、案情分析：将案

5、情的每一条写成逻辑表达式将案情的每一条写成逻辑表达式，第一条用第一条用 CC1 表示，表示，第二条用第二条用 CC2 表示，表示，思路：CC1CC1：A A和和B B至少有一人作案至少有一人作案令令 A 变量表示变量表示 A 作案，作案，B 变量表示变量表示 B 作案作案ABCC1000101011111显然这是或的关系，有显然这是或的关系，有CC1=(A|B)CC1=(A|B)CC2CC2：A A和和D D不可能是同案犯不可能是同案犯可做如下分析：可做如下分析：如果如果A 和和D是同案犯，则应写成是同案犯，则应写成 A&D所以，对于所以，对于“A 和和 D 不是同案犯不是同案犯”，应写成，应

6、写成 !(A&D)因此有因此有 CC2=!(A&D)CC2=!(A&D)ADA&DCC21001111000010101CC3CC3：A A、E E、F F 中至少有两人涉嫌作案中至少有两人涉嫌作案分析有三种可能分析有三种可能第一种，第一种，A 和和 E 作案，（作案，（A&E）第二种，第二种，A 和和 F 作案，（作案，（A&F）第三种，第三种，E 和和 F 作案，（作案，（E&F）这三种可能性是这三种可能性是 或或 的关系，因此有的关系，因此有CC3=(A&E）|（A&F）|（E&F)我们写出我们写出 CC3 的真值表。的真值表。AEFCC3111111011011011100100100

7、10000000CC3=(A&ECC3=(A&E）|（A&FA&F）|（E&F)E&F)CC4：B和和C或同时作案，或都与本案无关或同时作案，或都与本案无关第一种情况：同时作案（第一种情况：同时作案（B&C）第二种情况：都与本案无关（第二种情况：都与本案无关（!B&!C）两者为两者为或或的关系，因此有的关系，因此有 CC4=(B&C)|(!B&!C)BC!B!CB&C!B&!CCC41100101100100001100000011011CC5CC5：C C、D D中有且仅有一人作案中有且仅有一人作案CC5=(C&!D)|(D&!C)CC6：如果如果D没有参与作案，则没有参与作案，则E也不可能

8、参与作案。也不可能参与作案。两种可能性两种可能性：（1）D作案；（作案；（2）D未作案未作案对于（对于（1）D作案：作案：E可能作案，也可能不作案。因此，可表示为可能作案，也可能不作案。因此，可表示为:D&(E|(!E)当然，依题意，此种情况下与当然，依题意，此种情况下与E无关，故也可以将条件无关，故也可以将条件简化描述为简化描述为 D，而不必，而不必与与上上(E|!E)对于（对于（2）D未作案：未作案：依线索陈述，依线索陈述，E没有作案。因此，可表示：没有作案。因此，可表示：(!D)&(!E)综合起来，综合起来，CC6=(D&(E|(!E)|(!D)&(!E)CC6=(D&(E|(!E)|(

9、!D)&(!E)我们注意到，我们注意到，E|(!E)E|(!E)恒为真，即恒为真，即1 1。所以，上式可以化简为：所以，上式可以化简为：CC6=(D&1)|(!D)&(!E)CC6=(D&1)|(!D)&(!E)因为因为 D&1 D&1 恒等于恒等于 D D，所以有：，所以有：CC6 CC6 D|(!D)&(!E)D|(!D)&(!E)上式求或时，上式求或时，“或或”右边隐含着右边隐含着!D!D的意思，所以右的意思，所以右半部分中的半部分中的 !D!D 可以去掉，即：可以去掉，即：CC6 CC6 D|(!E)D|(!E)6个人每个人都有个人每个人都有作案作案或或不作案不作案两种可能，因此有两种

10、可能，因此有 26 种组合，从这些组合中挑出符合条件的作案者。种组合，从这些组合中挑出符合条件的作案者。定义定义 6 个整数变量，分别表示个整数变量，分别表示 6 个人个人A，B，C，D，E，F。如何枚举每个人的可能性？如何枚举每个人的可能性？用用 0 表示不是罪犯；表示不是罪犯；用用 1 表示就是罪犯。表示就是罪犯。涉及到涉及到“多重循环多重循环”！2、采取枚举方法，枚举下述64种组合什么是多重循环？来看下面的例子：什么是多重循环？来看下面的例子：编一个程序输出编一个程序输出 000000 000001 000010 .111111从高位到低位，分别用从高位到低位，分别用ABCDEF来表示来

11、表示ABCDEF000000000001000010111111 写一个从写一个从000000到到111111的程序的程序for(A=0;A=1;A=A+1)for(B=0;B=1;B=B+1)for(C=0;C=1;C=C+1)for(D=0;D=1;D=D+1)for(E=0;E=1;E=E+1)for(F=0;F=1;F=F+1)cout A B C D E F endl;for(F=0;F=1;F=F+1)coutABCDEF endl;循环体循环体 for(E=0;E=1;E=E+1)for(F=0;F=1;F=F+1)coutABCDEF endl;循环体循环体 for(D=0;D

12、=1;D=D+1)for(E=0;E=1;E=E+1)for(F=0;F=1;F=F+1)coutABCDEF endl;循环体循环体 for(A=0;A=1;A=A+1)for(B=0;B=1;B=B+1)循循 for(C=0;C=1;C=C+1)环环 for(D=0;D=1;D=D+1)体体 for(E=0;E=1;E=E+1)for(F=0;F=1;F=F+1)coutABCDEF endl;课后练习：课后练习：请你将上述输出请你将上述输出000000到到111111的程序补充的程序补充完整，并上机运行测试。完整，并上机运行测试。下面是下面是根根据案情分析采用枚举法寻找罪犯的据案情分析采

13、用枚举法寻找罪犯的程序框图程序框图 输输 出出 CC1+CC2+CC3+CC4+CC5+CC6=6 假假 真真 CC1=A|B;CC2=!(A&D);CC3=(A&E)|(A&F)|(E&F);CC4=(B&C)|(!B&!C);CC5=(C&!D)|(D&!C);CC6=D|(!E);for(F=0;F=1;F=F+1)for(E=0;E=1;E=E+1)for(D=0;D=1;D=D+1)for(C=0;C=1;C=C+1)for(B=0;B=1;B=B+1)for(A=0;A=1;A=A+1)为了给出每个人是否为罪犯的信息，程序中使用了下面的语句：cout “A:”(A=1?“是罪犯”:

14、“不是罪犯”)endl;其中，(A=1?”是罪犯”:”不是罪犯”)是一个三元表达式，该表达式由三部分组成，即 条件判断式?结果1:结果2如果 条件 为真，则表达式返回 结果1；如果 条件 为假，则表达式返回 结果2。/*/*程程 序序 名：名：4-9.cpp */*作作 者：者：wuwh */*编制时间：编制时间：2001年年8月月 */*主要功能：案情分析主要功能：案情分析 */*#include using namespace std;int main()/案情分析案情分析 /A和和B至少有一人作案；至少有一人作案；cc1=A|B /A和和D不可能是同案犯；不可能是同案犯；cc2=!(A&

15、D)/A，E，F中至少有两人涉嫌作案中至少有两人涉嫌作案 cc3=(A&E)|/(A&F)|/(E&F)/B和和C或同时作案或都与本案无关或同时作案或都与本案无关 cc4=(B&C)|(!B&!C)/C，D中有且仅有一人作案；中有且仅有一人作案；cc5=(C&!D)|(D&!C)/如果如果D没有参与作案没有参与作案,则则E也不可能参与作案也不可能参与作案;cc6=D|(!E)int cc1,cc2,cc3,cc4,cc5,cc6;/定义定义6个变量个变量,分别表示分别表示6句话句话 int A,B,C,D,E,F;/定义定义6个变量个变量,分别表示分别表示6个人个人 for(A=0;A=1;A

16、=A+1)/枚举枚举A for(B=0;B=1;B=B+1)/枚举枚举B for(C=0;C=1;C=C+1)/枚举枚举C for(D=0;D=1;D=D+1)/枚举枚举D for(E=0;E=1;E=E+1)/枚举枚举E for(F=0;F=1;F=F+1)/枚举枚举F cc1=A|B;cc2=!(A&D);cc3=(A&E)|(A&F)|(E&F);cc4=(B&C)|(!B&!C);cc5=(C&!D)|(D&!C);cc6=D|(!E);/测试测试6 6句话都为真时句话都为真时,才输出谁是罪犯才输出谁是罪犯 if(cc1+cc2+cc3+cc4+cc5+cc6=6)/输出判断结果输出判断结果 cout A:(A=1?”是罪犯”:”不是罪犯”)endl;cout B:(B=1?”是罪犯”:”不是罪犯”)endl;cout C:(C=1?”是罪犯”:”不是罪犯”)endl;cout D:(D=1?”是罪犯”:”不是罪犯”)endl;cout E:(E=1?”是罪犯”:”不是罪犯”)endl;cout F:(F=1?”是罪犯”:”不是罪犯”)数学语言描述以实现其以实现其“可计算性可计算性”n数学语言表达-程序语言表达满足其满足其“可行性可行性”，变成可执行的程序，变成可执行的程序结结 束束