数据结构与算法笔记:计算思维之谁做的好事与刑侦作案问题"/>
数据结构与算法笔记:计算思维之谁做的好事与刑侦作案问题
谁做的好事
- 清华附中有四位同学中的一位做了好事,不留名,表扬信来了之后,校长问这四位是谁做的好事。
- A说:不是我。
- B说:是C。
- C说:是D。
- D说:他胡说。
- 已知:三个人说的是真话,一个人说的是假话。
- 现在请你根据这些信息,编写程序找出做了好事的人。
- 分析
- 将四个人说的四句话(自然语言)转换成计算机可以计算的式子, 可使用循环枚举的方式来判断
- (1) 思路一:通过字符表示人
- 先定义一个字符变量
thisman
表示要寻找的做了好事的人的“名字(代号)”(A、B、C、D),即char thisman; // 'A', 'B', 'C', 'D'
- 用关系表达式改写四个人说的话
- A说“不是我” ⇒ \Rightarrow ⇒
thisman != 'A'
- B说“是C” ⇒ \Rightarrow ⇒
thisman == 'C'
- C说“是D” ⇒ \Rightarrow ⇒
thisman == 'D'
- D说“他胡说” ⇒ \Rightarrow ⇒
thisman != 'D'
- A说“不是我” ⇒ \Rightarrow ⇒
- 代码实现
#include <iostream> using namespace std;int main() {int g = 0; // 初始化为0,表示“无解”// for 循环体开始 k是循环控制变量for (int k = 0; k < 4; k++) {char thisman = 'A' + k;int sum = (thisman != 'A') + (thisman == 'C') + (thisman == 'D') + (thisman != 'D');if (sum == 3){ // 如果3句话为真,则输出当前可能性所假定的人为做好事者cout << "做好事者为" << thisman << endl;g = 1; // 有解标志置1,表示找到解了}}if (g != 1) {cout << "找不出做好事者" << endl; // 输出无解信息return 0;} }
- (2) 思路二:通过数字表示人
- 让k表示要找的人,k从0到3,表示从A找到D
- 用关系表达式改写四个人说的话
- A说“不是我” ⇒ \Rightarrow ⇒
k != 0
- B说“是C” ⇒ \Rightarrow ⇒
k == 2
- C说“是D” ⇒ \Rightarrow ⇒
k == 3
- D说“他胡说” ⇒ \Rightarrow ⇒
k != 3
- A说“不是我” ⇒ \Rightarrow ⇒
- 代码实现
#include <iostream> using namespace std;int main() {int g = 0; // 初始化为0,表示“无解” 哨兵变量char thisman = 'A';// for 循环体开始 k是循环控制变量for (int i = 0; i < 4; i++) {int k = 0;k += i;int sum = (k != 0) + (k == 2) + (k == 3) + (k != 3);// 如果3句话为真,则输出当前可能性所假定的人为做好事者if (sum == 3){thisman += k;cout << "做好事者为" << thisman << endl;g = 1; // 有解标志置1,表示找到解了}}if (g != 1) {cout << "找不出做好事者" << endl; // 输出无解信息return 0;} }
刑侦案件
- 某地刑侦大队对涉及六个嫌疑人的一桩疑案进行分析,以下内容叙述的是刑侦队搜集到的线索和情报:
- A、B 至少有一人作案;
- A、E、F 三人中至少有两人参与作案;
- A、D 不可能是同案犯;
- B、C 或同时作案,或与本案无关;
- C、D 中有且仅有一人作案;
- 如果D没有参与作案,则E也不可能参与作案
- 请编写程序,将作案人找出来
- 分析
- 同上题一样,这一题也是一个循环枚举的思想
- 6个人中,每一个人都有2种可能,作案和没作案
- 可以根据数学思想,作分步枚举,共有6步,所以用6个循环
- 分别用a,b,c,d,e,f表示6个人, 同时,作案用1表示,未作案用0表示
- 用关系表达式改写6条线索
- A、B 至少有一人作案; ⇒ \Rightarrow ⇒
a || b
- A、E、F 三人中至少有两人参与作案; ⇒ \Rightarrow ⇒
(a&&e) || (a&&f) || (e&&f)
- A、D 不可能是同案犯; ⇒ \Rightarrow ⇒
!(a&&d)
- B、C 或同时作案,或与本案无关; ⇒ \Rightarrow ⇒
(b&&c) || (!b&&!c)
- C、D 中有且仅有一人作案; ⇒ \Rightarrow ⇒
(c&&!d) || (!c&&d)
- 如果D没有参与作案,则E也不可能参与作案 ⇒ \Rightarrow ⇒
d || (!d&&!e)
- A、B 至少有一人作案; ⇒ \Rightarrow ⇒
- 代码实现
#include <bits/stdc++.h> using namespace std;int main() { int flag = 0; for (int a = 0; a < 2; a++) {for (int b = 0; b < 2; b++) {for (int c = 0; c < 2; c++) {for (int d = 0; d < 2; d++) {for (int e = 0; e < 2; e++) {for (int f = 0; f < 2; f++) {if ((a || b) + ((a && e) || (a && f) || (e && f)) + (!(a && d)) + ((b && c) || (!b && !c)) + ((c && !d) || (!c && d)) + (d || (!d && !e)) == 6) {flag = 1;string A, B, C, D, E, F;A = a ? "A" : "";B = b ? "B" : "";C = c ? "C" : "";D = d ? "D" : "";E = e ? "E" : "";F = f ? "F" : "";cout << "作案人员有:" << A << B << C << D << E << F << endl;}}}}}} } if (!flag) {printf("未找到作案人员!"); } return 0; }
更多推荐
数据结构与算法笔记:计算思维之谁做的好事与刑侦作案问题
发布评论