知识点

计算思维

7 分钟阅读

计算思维把一个问题从“想清楚”推进到“能算”：先确定输入与输出，再拆出可以由有限步骤完成的子任务，最后比较不同做法的正确性与代价。本页用找假币和分解因数两个问题演示这条路径。递归的写法见递归；把问题分成同型子问题、分别求解再合并的策略见分治法。

定义

计算思维是运用计算机科学的基础概念进行问题求解、系统设计以及人类行为理解等一系列思维活动。落到算法设计上，它通常包含四个方面：

抽象：忽略与目标无关的细节，保留决定答案的对象和关系。
分解：把大问题拆成若干可以独立处理的子问题。
算法设计：写出有限、确定、可执行的步骤，并说明何时停止。
评估：比较不同步骤序列的正确性与代价，例如比较次数、运行时间和额外空间。

从问题到可计算步骤

把一个用自然语言描述的问题转成算法，可以按下面的顺序检查：

明确输入与输出

写出输入的类型、范围和约束，以及要返回什么。找假币的输入是硬币重量列表，输出是假币的下标。
确定判定与终止条件

说明什么情况下已经得到答案、可以停止。找假币在发现一对重量不同的硬币时立即返回，不需要扫描完整个列表。
选择分解方式

可以按位置分、按规模分、按值分，也可以先处理一个局部再递归处理剩余部分。分解方式决定了子问题是否同型，以及是否需要合并。
评估代价

数一数最坏情况下要做多少次基本操作。代价必须相对于允许的操作来计数：如果只允许比较两枚硬币的重量，一次扫描需要 $n-1$ 次比较；如果换用天平、每次把候选分成三堆，代价就会不同。讨论复杂度之前先固定计算模型。
用边界情形检查

至少检查最小规模、答案在首尾、没有答案这几类输入，确认程序不会越界或漏解。

分解的粒度也影响实现：拆得太细会带来大量调用和合并开销，拆得太粗则子问题仍然难以直接求解。

例子

找假币：一次相邻比较

设有 $n\ge2$ 枚硬币，其中恰有一枚比真币轻。只允许比较两枚硬币的重量时，可以按相邻位置扫描：重量相等就继续前进，出现不等时较轻的那一枚就是假币。

1
def findcoin_1(L):
2
    if len(L) <= 1:
3
        print("Error: coins are too few")
4
        quit()
5
    i = 0
6
    while i < len(L):
7
        if L[i] < L[i + 1]:
8
            return i
9
        elif L[i] > L[i + 1]:
10
            return i + 1
11
        i = i + 1
12
    print("All coins are the same")
13
    return len(L)  # 正常输入不会到达这里
14

15

16
import random
17

18
n = int(input("Enter the number of coins >=2: "))
19
w_normal = random.randint(2, 5)
20
index_faked = random.randint(0, n - 1)  # 0 <= index <= n-1
21
L = []
22
for i in range(0, n):
23
    L.append(w_normal)
24
L[index_faked] = w_normal - 1
25
print(L)
26
print("The index of faked coin:", findcoin_1(L))

假币在最后一位时，前 $n-2$ 对都相等，最后一次比较才会发现它，因此最坏情况需要 $n-1$ 次比较。

分解因数：每层把规模缩小到 $\sqrt{x}$

下面的函数找出 $x$ 的所有素因数。若 $x$ 是合数，它一定有一个不超过 $\lfloor\sqrt{x}\rfloor$ 的因数；从小到大地试除，找到第一个因数 $i$ 后，只需递归分解 $x//i$ ，因为更小的因数已经不可能出现。

1
import math
2

3

4
def factors(x, L):
5
    y = int(math.sqrt(x))  # x的平方根
6
    for i in range(2, y + 1):  # 从小到大找因数
7
        if x % i == 0:  # 找到一个因数i
8
            print(i)
9
            L.append(i)
10
            factors(x // i, L)  # 递归分解剩余部分
11
            break  # 找到一个就跳出for循环
12
    else:  # 找不到因数，x是素数
13
        L.append(int(x))
14
        print(int(x))
15

16

17
L = []
18
factors(18, L)

for ... else的else只在循环没有被break打断时执行，所以它正好对应“试除完毕仍没有因数”的情形。factors(18, L) 依次输出2、3、3，结束后L为 [2, 3, 3]。

每层递归至少把 $x$ 缩小一半，递归深度不超过 $\log_2 x$ ；每层只试除到当前数的平方根，避免了对整个原数逐一试除。

交互探索

选择一枚较轻的硬币，按三等分策略逐次称量，观察每次结果如何缩小候选范围。

两次称量怎样缩小假币范围？

假设九枚硬币中有一枚较轻，逐步查看称量决策。

正在准备演示…

题集

练习

设L = [5, 5, 5, 4, 5]，调用findcoin_1(L) 返回的下标是。
参考解答
前两对重量相等，i增加到2；此时L[2] = 5大于L[3] = 4，于是返回3。
有8枚硬币，假币比真币轻且位于最后一个位置。按findcoin_1的相邻比较方式，最坏情况下需要的比较次数是。
参考解答
假币在最后一位时，前6对相等，第7次比较L[6] 与L[7] 才发现较轻的一枚，所以需要 $8-1=7$ 次比较。
把一个自然语言描述的问题转成可计算步骤时，下列哪些属于必要的检查？
题 computable-checks · choice
A
明确输入的类型、范围与输出
B
保证每一步可执行且步骤有限
C
说明算法对合法输入一定终止
D
先列出输入的所有具体数值
参考解答
输入输出、可执行性和终止性都是算法的基本要求。具体数值只是某一次运行的实例，不能代替对输入范围的说明。
执行factors(18, L) 后，L的内容是：
选择答案
A
[2, 3, 3]
B
[2, 9]
C
[3, 3, 2]
D
[2, 2, 3]
参考解答
先找到因数2，剩余9；对9找到因数3，剩余3；3没有不超过 $\sqrt{3}$ 的因数，作为素数加入，得到 [2, 3, 3]。