逻辑思维与计算机解题.pptVIP

1,逻辑思维与计算机解题,2,将实际问题抽象为逻辑关系 枚举法解题思路 关系与关系表达式 程序的循环结构与分支结构,学 习 目 标,3,关系运算符与关系表达式 人的思维到用计算机语言的表示 枚举的概念与思路 循环结构 分支结构,内 容 要 点,4,计算机强大的逻辑分析功能是由人通过程序赋给它的。一些逻辑问题必须转换成计算机能够看得懂的数学表达式和一定的程序指令。这一章我们通过例子来介绍如何将人对问题的思考转换为让计算机能解的数学表达式，同时给出一些通常要用到的程序结构和C/C+语句。,5,清华附中有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。 A说：不是我。 B说：是C。 C说：是D。 D说：他胡说。 已知三个人说的是真话，一个人说的是假话。现在要根据这些信息，找出做了好事的人。,【例1】 “谁做的好事”,6,为了解这道题，我们需要学习如何通过逻辑思维与判断解这类问题的思路。,7,将四个人说的四句话写成关系表达式。 在声明变量时，我们让thisman表示要寻找的做了好事的人，定义它是字符变量。 char thisman=; / 定义字符变量并将其初始化为空 让 “ = ” 的含义为“是”， 让 “ != ” 的含义为“不是”。,8,利用关系表达式将四个人所说的话表示成,9,A、B、C、D四个人，只有一位是做好事者。令做好事者为1，未做好事者为0，可以有如下4中状态（情况）,枚举法的思路,10,这四种状态可简化写成,显然第一种状态是假定A是做好事者，第二种状态是假定B是做好事者，。所谓枚举是按照这四种假定逐一地去测试四个人的话有几句是真话，如果不满足三句为真，就否定掉这一假定，换下一个状态再试。 具体做法如下：,11,（1）假定让thisman=A代入四句话中,四个关系表达式的值的和为1，显然不是A做的好事,12,（2）假定让thisman=B代入四句话中,四个关系表达式的值的和为2，显然不是B做的好事,13,（3）假定让thisman=C代入四句话中,四个关系表达式的值的和为3，就是C做的好事,14,综上所述一个人一个人去试，就是枚举。从编写程序看，实现枚举最好用循环结构。 这部分的程序写出如下：,for (k=1; k=4; k=k+1) / 计数型循环，循环的控制变量为k thisman=64+k; / 产生被试者，依次为A,B,C,D sum = (thisman!=A) / 测试A的话是否为真 +(thisman=C) / 测试B的话是否为真 +(thisman=D) / 测试C的话是否为真 +(thisman!=D); / 测试D的话是否为真 ,15,NS图,有了上述了解之后，我们来看解“谁做的好事”的程序框图,图 4.7,16,#include / 预编译命令 using namespace std ; int main() / 主函数 / 主函数开始 int k=0,sum=0,g=0 ; / 定义整型变量，均初始化为0 char thisman= ; / 定义字符变量，初始化为空 for(k=1;k=4;k=k+1 ) / k是循环控制变量 / for 循环体开始 thisman = 64+k; sum=( thisman!=A )+ ( thisman=C ) + ( thisman=D ) + ( thisman!=D ); if (sum=3) / 如果3句话为真，则输出该人 cout “做好事者为“ char(64+k) endl; g=1; / 有解标志置1 / for 循环体结束 if (g!=1) cout “Cant found!“ endl; / 输出无解信息 return 0 ; / 主函数结束,17,#include / 预编译命令 using namespace std ; void main() int k =0, sum =0 , g =0; char thisman = ; for ( k = 1; k = 4 ; k = k+1 ) thisman = 64 + k; sum = ( thisman != A ) +( thisman=D ) + ( thisman=C ) + ( thisman !=D ); if ( sum=3 ) cout “做好事者为“ char(64+k) endl; g=1; if (g!=1) cout “Cant found!“ endl; ,18,换个思路 数字 1 表示 A 数字 2 表示 B 数字 3 表示 C 数字 4 表示 D 让 K 表示要找的人，K从1到4，表示从A 找到D，这时 A说：不是我; 可形式化为 K !=1; B说：是C ; 可形式化为 K=3; C说：是D; 可形式化为 K=4; D说：他胡说； 可形式化为 K!=4;,19,#include / 预编译命令 using namespace std; void main() / 主函数 / 主函数开始 int k=0,sum=0,g=0; / 声明变量为整数类型，且均初始化为0 for(k=1;k=4;k=k+1) / 循环从k为1到4， sum=0; / 循环体内的初始化，用sum累计真话数 if (k!=1) sum=sum+1; / 如A的话为真，则让sum加1； if (k=3) sum=sum+1; / 如B的话为真，则让sum加1； if (k=4) sum=sum+1; / 如C的话为真，则让sum加1； if (k!=4) sum=sum+1; / 如D的话为真，则让sum加1； if (sum=3) / 若有三句话为真，则做下列两件事 cout “This man is “ char(64+k) endl; / 输出做好事者 g=1; / 让有解标志置1 if (g!=1) / 则输出无解信息 cout “Cant found!“ endl; ,20,for ( k = 1; k = 4; k = k+1 ) sum=0; if ( k != 1 ) sum = sum+1; / 如A的话为真， 则让sum加1； if ( k =3 ) sum = sum+1; / 如B的话为真，则让sum加1； if ( k =4 ) sum = sum+1; / 如C的话为真，则让sum加1； if ( k != 4 ) sum = sum+1; / 如D的话为真，则让sum加1； . . . ,21,#include / 预编译命令 int main() / 主函数 / 主函数开始 int k=0,g=0; / 声明变量为整数类型，且均初始化为0 for(k=1;k=4;k=k+1) / k既是循环控制变量，也表示第k个人 if (k!=1)+(k=3)+(k=4)+(k!=4)=3) / 如果4句话有3句话为真，则输出该人 cout “做好事者为“ char(64+k) endl; g=1; / 有解标志置1 if (g!=1) / g!=1则输出无解信息 cout “Cant found!“ endl; return 0; / 主函数结束,上述程序可以简化为：,22,for ( k = 1; k = 4 ; k = k+1 ) if (k!=1)+(k=3)+(k=4)+(k!=4)=3) cout “做好事者为“ char(64+k) endl; g=1; A说 B说 C说 D说,23,for( k= 1; k= 4; k= k+ 1 ) if ( ( ( k != 1) + ( k = 3) + /如果4句话有3句真话，就 ( k = 4) + /输出做好事者 ( k != 4 ) ) = 3 ) cout “做好事者为” char( 64+ k )endl; g = 1; ,24,思考和讨论 for(int k=68; k= 65; k= k- 1 ) if ( ( ( k != 65) + ( k = 67) + /如果4句话有3句真话， ( k = 68) + /就输出做好事者 ( k != 68 ) ) = 3 ) cout “做好事者为” char( k )endl; g = 1; ,25,某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析： A、B 至少有一人作案； A、E、F 三人中至少有两人参与作案； A、D 不可能是同案犯； B、C 或同时作案，或与本案无关； C、D 中有且仅有一人作案； 如果 D 没有参与作案，则 E 也不可能参与作案。 试编一程序，将作案人找出来。,例2,26,思路：,1、案情分析： 将案情的每一条写成逻辑表达式， 第一条用 CC1 表示， 第二条用 CC2 表示， ,27,CC1：A和B至少有一人作案 令 A 变量表示 A 作案，B 变量表示 B 作案,显然这是或的关系，有CC1= ( A | B ),28,CC2：A和D不可能是同案犯 可以分析为： A 和D是同案犯，写成 A & D A 和 D 不是同案犯，写成 !( A & D ) 因此有 CC2 = !( A & D ),29,CC3：A、E、F 中至少有两人涉嫌作案 分析有三种可能 第一种，A 和 E 作案，（A & E） 第二种，A 和 F 作案，（A & F） 第三种，E 和 F 作案，（E & F） 这三种可能性是 或 的关系，因此有 CC3 = (A & E）|（A & F）|（E & F),30,CC4：B和C或同时作案，或都与本案无关 第一种情况：同时作案（B & C） 第二种情况：都与本案无关（!B & !C） 两者为或的关系，因此有 CC4 = (B & C) | (!B & !C),31,CC5：C、D中有且仅有一人作案 CC5=(C & !D) | (D & !C),32,CC6：如果D没有参与作案，则E也不可能参与作案。 分析这一条比较麻烦一些，可以列出真值表再归纳,33,CC6=D | !E,以上是案情分析，已经化成了计算机可解的逻辑表达式,34,6个人每个人都有作案或不作案两种可能，因此有 种组合，从这些组合中挑出符合6条分析的作案者。 定义 6 个整数变量，分别表示 6 个人A，B，C，D，E，F。 枚举每个人的可能性 让 0 表示不是罪犯； 让 1 表示就是罪犯。,2、采取枚举方法，枚举什么呢？枚举组合,35,为了讲多重循环先做些铺垫 编一个程序输出 000000 000001 000010 . . . . . . 111111 从高位到低位，分别用ABCDEF来表示,36,37,写一个从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) coutABCDEF endl; ,38,作业 请你完成输出000000到111111的程序 并上机运行 下面是据案情分析采用枚举法寻找罪犯的程序框图,39,40,为了给出每个人是否为罪犯的信息，程序中定义了一个二维数组。 char info29=“不是罪犯”，“是罪犯”；,有两个字串,每串最多有91个英文字符,info为 数组名,41,char 是说，info 数组的元素为字符，2为下标，表示有两个字符串，每个字符串最多有91个字符。 因为英文字符占一个字节，而汉字占两个字节，故 4个汉字要占 8 个英文字符的地方。 每一字串后面自动跟一个空字符0 因此可以看出： 第 0 号字符串 info0 的内容为“不是罪犯”。 第 1 号字符串 info1 的内容为“是罪犯”。,42,在输出时用 cout “ A: ” infoA endl; 如果A为0，则输出 A:不是罪犯 如果A为1，则输出 A:是罪犯,43,#include using namespace std; int main(void) /案情分析 /A和B至少有一人作案； cc1=A | B /A和D不可能是同案犯； cc2=!(A /定义二维数组,给出是否罪犯信息,44,for (A=0;A=1;A=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 ,45,/测试6句话都为真时, 才输出谁是罪犯 if ( cc1+cc2+cc3+cc4+cc5+cc6 = 6 ) /输出判断结果 cout “A: “ infoA endl; cout “B: “ infoB endl; cout “C: “ infoC endl; cout “D: “ infoD endl; cout “E: “ infoE endl; cout “F: “ infoF endl; /输出结束 /循环结束 return 0; / 主函数体结束,46,讨 论,47,大家参与讨论的题,五位跳水高手将参加十米高台跳水决赛，有好事者让五个人据实力预测比赛结果。 A选手说：B第二，我第三； B选手说：我第二，E第四； C选手说：我第一，D第二； D选手说：C最后，我第三； E选手说：我第四，A第一; 决赛成绩公布之后，每位选手的预测都只说对了一半，即一对一错，请编程解出比赛的实际名次。,48,思路：,1、首先是将五个人的预测写成逻辑表达式： 让关系运算符 “=” 的含义是 “是”。 让数字 1、2、3、4、5 分别表示名次第一、第二，第五。 让整型变量 A、B、C、D、E 分别表示每个选手所得名次。 A选手说：B=2，A=3； B选手说：B=2，E=4；