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

1 逻辑思维与计算机解题 2 将实际问题抽象为逻辑关系枚举法解题思路关系与关系表达式程序的循环结构与分支结构 学习目标 3 关系运算符与关系表达式人的思维到用计算机语言的表示枚举的概念与思路循环结构分支结构 内容要点 4 计算机强大的逻辑分析功能是由人通过程序赋给它的 一些逻辑问题必须转换成计算机能够看得懂的数学表达式和一定的程序指令 这一章我们通过例子来介绍如何将人对问题的思考转换为让计算机能解的数学表达式 同时给出一些通常要用到的程序结构和C C 语句 5 清华附中有四位同学中的一位做了好事 不留名 表扬信来了之后 校长问这四位是谁做的好事 A说 不是我 B说 是C C说 是D D说 他胡说 已知三个人说的是真话 一个人说的是假话 现在要根据这些信息 找出做了好事的人 例1 谁做的好事 6 为了解这道题 我们需要学习如何通过逻辑思维与判断解这类问题的思路 7 将四个人说的四句话写成关系表达式 在声明变量时 我们让thisman表示要寻找的做了好事的人 定义它是字符变量 charthisman 定义字符变量并将其初始化为空让 的含义为 是 让 的含义为 不是 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 预编译命令usingnamespacestd intmain 主函数 主函数开始intk 0 sum 0 g 0 定义整型变量 均初始化为0charthisman 定义字符变量 初始化为空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 Can tfound endl 输出无解信息return0 主函数结束 17 include 预编译命令usingnamespacestd voidmain intk 0 sum 0 g 0 charthisman 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 Can tfound 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 预编译命令usingnamespacestd voidmain 主函数 主函数开始intk 0 sum 0 g 0 声明变量为整数类型 且均初始化为0for 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 Thismanis char 64 k endl 输出做好事者g 1 让有解标志置1 if g 1 则输出无解信息 cout Can tfound 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 预编译命令intmain 主函数 主函数开始intk 0 g 0 声明变量为整数类型 且均初始化为0for 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 Can tfound endl return0 主函数结束 上述程序可以简化为 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 intk 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 DA和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 为了讲多重循环先做些铺垫编一个程序输出000000000001000010 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 cout A B C D E F endl 38 作业请你完成输出000000到111111的程序并上机运行下面是据案情分析采用枚举法寻找罪犯的程序框图 39 40 为了给出每个人是否为罪犯的信息 程序中定义了一个二维数组 charinfo 2 9 不是罪犯 是罪犯 有两个字串 每串最多有9 1个英文字符 info为数组名 41 char是说 info数组的元素为字符 2 为下标 表示有两个字符串 每个字符串最多有9 1个字符 因为英文字符占一个字节 而汉字占两个字节 故4个汉字要占8个英文字符的地方 每一字串后面自动跟一个空字符 0 因此可以看出 第0号字符串info 0 的内容为 不是罪犯 第1号字符串info 1 的内容为 是罪犯 42 在输出时用cout A info A endl 如果A为0 则输出A 不是罪犯如果A为1 则输出A 是罪犯 43 includeusingnamespacestd intmain void 案情分析 A和B至少有一人作案 cc1 A B A和D不可能是同案犯 cc2 A 定义二维数组 给出是否罪犯信息 44 for A 0 A 1 A A 1 枚举Afor B 0 B 1 B B 1 枚举Bfor C 0 C 1 C C 1 枚举Cfor D 0 D 1 D D 1 枚举Dfor E 0 E 1 E E 1 枚举Efor 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 info A endl cout B info B endl cout C info C endl cout D info D endl cout E info E endl cout F info F endl 输出结束 循环结束return0 主函数体结束 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 C选手说 C 1 D 2 D选手说 C 5 D 3 E选手说 E 4 A 1 49 2 考虑到每个人说的话是一对一错 即一真一假 比如A说的 B 2 A 3 应该是11 0 10 1 1 50 我们可以归纳出要同时满足五个人所说的话都符合一半对一半错的条件是ta B 2 A 3 1 符合A选手的话tb B 2 E 4 1 符合B选手的话tc C 1 D 2 1 符合C选手的话td C 5 D 3 1 符合D选手的话te E 4 A 1 1 符合E选手的话因为ta tb te非1即0 五个条件值都加在一起 51 ta的取值是0或1ta的取值取决于下列关系 B 2 A 3 1B 2 可能是0或1A 3 可能是0或1 B 2 A 3 可能是0或1或2只有上式为1才能使ta为1 52 3 只有等于5时才都符合每个人所说的话 这仅只是符合题意的一个必要条件 同时还得考虑A B C D E的取值不得有相同者 可以考虑 是一个条件 53 4 仍然可以用枚举的方法 让变量A B C D E在1 5中取值 形成满足上述条件的A E的组合 即是所求 这时可用循环结构 如下所示 54 55 作业 1请你自己完成这个程序 2思考如何提高效率 3思考还有什么其它解法 56 结束