数据结构与算法笔记：计算思维之谁做的好事与刑侦作案问题

数据结构与算法笔记：计算思维之谁做的好事与刑侦作案问题"/>

数据结构与算法笔记：计算思维之谁做的好事与刑侦作案问题

谁做的好事

• 清华附中有四位同学中的一位做了好事，不留名，表扬信来了之后，校长问这四位是谁做的好事。
  • 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'
  • 代码实现

    #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
  • 代码实现

    #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)
  • 代码实现

    #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;
    }