ch3 逻辑推理与枚举¶

1. 谁做的好事 —— 语义表示¶

方法一：用字符来表示，'A' 代表 A，'B' 代表 B，\(...\)
方法二：给 A、B、C、D 编号，\(0\) 号是 A，\(1\) 号是 B，\(...\)

两种方法本质是一样的，在 C++ 中，字符本质上是整数（\(\tt ASCII\) 码）。

变量不仅能用于表示代数计算中的数量，还能够用于表示特定概念的事物，因此我们可以定义一个变量表示 “做好事的人”。

C++

char good_man;      // 定义变量，表示 “做好事的人”
good_man = 'A';     // “做好事的人” 是 A --> A 做了好事

赋值语句表示的是一个既成事实，或者在当前情况下认定的事实，是一种 “真理”。问题中每个人的话实际上只是一种说法，一种论断，需要判断 “真伪”。

C++

good_man != 'A';    // A 说：不是我。即：“做好事的人” 和 A 不是同一个人
good_man == 'C';    // B 说：是 C。即：“做好事的人” 和 C 是同一个人

!= 和 == 称为关系运算符，分别表示 “不等于” 和 “等于”。含有关系运算符的式子称为关系表达式，关系表达式的计算结果是布尔类型。关系运算符还有大于 >、大于等于 >=、小于 <、小于等于 <=。

2. 谁做的好事 —— 真假检查¶

条件语句 if 可以使得部分程序语句在满足一定条件的情况下才能执行。

if 语句 if-else 语句

C++

int count = 0;                  // 说真话的人数
if (good_man != 'A')            // A 说了真话
    count++;
if (good_man == 'C')            // B 说了真话
    count++;
if (good_man == 'D')            // C 说了真话
    count++;
if (good_man != 'D')            // D 说了真话
    count++;
if (count == 3)                 // 有 3 个人说了真话
    cout << good_man << endl;   // 输出做好事的人

3. 谁做的好事 —— 循环枚举¶

循环语句是让程序循环执行一些代码指令的语句。

for 语句

C++

for (good_man = 'A'; good_man <= 'D'; good_man++) {
    int count = 0;                  // 说真话的人数
    if (good_man != 'A')            // A 说了真话
        count++;
    if (good_man == 'C')            // B 说了真话
        count++;
    if (good_man == 'D')            // C 说了真话
        count++;
    if (good_man != 'D')            // D 说了真话
        count++;
    if (count == 3) {               // 有 3 个人说了真话
        cout << good_man << endl;   // 输出做好事的人
        break;                      // 跳转语句，找到答案之后提前结束循环
    }
}

枚举往往通过循环实现，通过合理巧妙设计 \(3\) 个表达式，依次不重复不遗漏的枚举所有可能答案，并进行检测。

4. 谁是嫌疑犯 —— 多重循环¶

把事物进行人为有序的编号，利用编号可以进行更方便的计算。比如用 \(0\) 表示没有参与作案，用 \(1\) 表示参与作案：

C++

int A, B, C, D, E, F;
for (A = 0; A <= 1; A++)
    for (B = 0; B <= 1; B++)
        for (C = 0; C <= 1; C++)
            for (D = 0; D <= 1; D++)
                for (E = 0; E <= 1; E++)
                    for (F = 0; F <= 1; F++)
                        // 检测答案是否正确并输出

5. 谁是嫌疑犯 —— 破案线索表示¶

逻辑与 &&，表达同时成立的含义
逻辑或 ||，表达至少一个成立的含义
逻辑非 !，表达不成立的含义

C++

int A, B, C, D, E, F;
bool found = false;     // break 只能退出一层循环，用标志变量退出多层循环更简单
for (A = 0; A <= 1 && !found; A++)
    for (B = 0; B <= 1 && !found; B++)
        for (C = 0; C <= 1 && !found; C++)
            for (D = 0; D <= 1 && !found; D++)
                for (E = 0; E <= 1 && !found; E++)
                    for (F = 0; F <= 1 && !found; F++) {
                        bool b1 = (A == 1) || (B == 1);
                        bool b2 = ((A == 1) && (E == 1)) ||
                                  ((A == 1) && (F == 1)) ||
                                  ((E == 1) && (F == 1));
                        bool b3 = !((A == 1) && (D == 1));
                        bool b4 = ((B == 1) && (C == 1)) ||
                                  ((B == 0) && (C == 0));
                        bool b5 = ((C == 1) && (D == 0)) ||
                                  ((C == 0) && (D == 1));
                        bool b6 = ((D == 0) && (E == 0)) || （D == 1);

                        if (b1 && b2 && b3 && b4 && b5 && b6) {
                            cout << A << B << C << D << E << F << endl;
                            found = true;
                        }
                    }

6. 谁是嫌疑犯 —— 用二进制枚举¶

如果用 \(1\) 个二进制位来表示一个人是否作案，于是 \(6\) 个人是否作案的情况可以表示成一个 \(6\) 位二进制数，因此我们可以用一层循环来枚举所有的 \(6\) 位二进制数即可。

获取一个数的二进制位需要用到位运算。

位运算

C++

for (int i = 0; i < (1 << 6); i++) {
    int A = (i >> 5) & 1;
    int B = (i >> 4) & 1;
    int C = (i >> 3) & 1;
    int D = (i >> 2) & 1;
    int E = (i >> 1) & 1;
    int F = i & 1;

    bool b1 = (A == 1) || (B == 1);
    bool b2 = ((A == 1) && (E == 1)) ||
              ((A == 1) && (F == 1)) || ((E == 1) && (F == 1));
    bool b3 = !((A == 1) && (D == 1));
    bool b4 = ((B == 1) && (C == 1)) || ((B == 0) && (C == 0));
    bool b5 = ((C == 1) && (D == 0)) || ((C == 0) && (D == 1));
    bool b6 = ((D == 0) && (E == 0)) || （D == 1);

    if (b1 && b2 && b3 && b4 && b5 && b6) {
        cout << A << B << C << D << E << F << endl;
        break;
    }
}