Python 计算思维入门到实用：函数、循环、条件、排序、矩阵、图与最短路

这篇笔记根据 COMP1010 / COMP1002 计算思维与问题求解资料整理。它和普通 Python 语法教程不太一样：重点不是“Python 有哪些语法”，而是“拿到一个问题之后，怎样把它拆成可以执行的步骤，再用 Python 写出来”。

如果你以后想继续学数据分析、机器学习、搜索推荐、NLP 或 AI infra，Python 的价值不只是写脚本，更重要的是训练一种能力：把模糊问题变成输入、输出、数据结构和算法流程。

参考资料下载

原始课件和作业资料保留在这里，方便对照阅读：

• COMP1010 Python 全部资料压缩包
• Lecture 1: Introduction to Computational Thinking
• Lecture 2: Number Representation, Functions and Procedures
• Lecture 3: Pseudocode and Iterations
• Lecture 4: Conditionals
• Lecture 5 and 6: Sorting and Computing
• Lecture 7: Challenges in Computation
• Lecture 8: Problem Solving Principles and Abstraction
• Lecture 9: Graph Problems
• Lecture 10: Graph Representations
• Lecture 11: Shortest Paths
• Lecture 12: Recap
• Assignment 1
• Assignment 2

1. 什么是计算思维

计算思维不是“会用电脑”，而是用计算机可以执行的方式描述问题。

一个程序通常可以拆成：

Input -> Process -> Output

例如“把一组学生分数按从高到低排序”：

• Input：学生名字和分数列表。
• Process：比较分数、交换位置、生成排序结果。
• Output：排序后的学生列表。

如果问题还停留在“我想整理成绩”这个层面，电脑是无法执行的。你必须进一步说明：数据长什么样、比较规则是什么、输出格式是什么、边界情况如何处理。

这就是计算思维的核心：

• abstraction：忽略不必要细节，只保留解决问题需要的信息。
• decomposition：把大问题拆成小问题。
• algorithm：设计一步一步能执行的流程。
• evaluation：检查结果是否正确，效率是否能接受。

2. 先写伪代码，再写 Python

初学者常见问题是直接写代码，然后卡在语法里。更稳的方法是先写伪代码。

假设要输出 1 到 10 的平方：

set i = 1
while i <= 10 do
    print i * i
    i = i + 1
end while

翻译成 Python：

i = 1

while i <= 10:
    print(i * i)
    i = i + 1

伪代码的好处是，它让你先关心逻辑，再关心语法。尤其是循环、条件、图算法这类问题，伪代码可以帮你看清楚每一步。

3. 变量、类型与表达式

Python 变量不需要提前声明类型：

age = 20
gpa = 3.7
name = "Richard"
passed = True

常见基础类型：

类型	示例	用途
int	42	整数
float	3.14	小数
str	"hello"	文本
bool	True	判断条件
list	[1, 2, 3]	一组有顺序的数据
tuple	(1, 2)	固定组合
dict	{"a": 1}	键值映射
set	{1, 2, 3}	去重集合

一个容易踩的坑是整数除法和取余：

print(7 / 2)   # 3.5
print(7 // 2)  # 3
print(7 % 2)   # 1

// 常用于“只保留整数部分”，% 常用于判断整除、奇偶、循环位置。

4. 进制转换：理解数字如何被表示

课件里讲了十进制、八进制、二进制、十六进制。计算机底层使用二进制，因为硬件状态天然适合表示 0 和 1。

手写十进制转二进制的思路：

while n > 0:
    remainder = n % 2
    record remainder
    n = n // 2
reverse recorded remainders

Python 实现：

def decimal_to_binary(n):
    if n == 0:
        return "0"

    digits = []

    while n > 0:
        digits.append(str(n % 2))
        n = n // 2

    digits.reverse()
    return "".join(digits)


print(decimal_to_binary(13))  # 1101

为什么这很重要？因为它训练你用循环不断缩小问题，也能帮助理解哈希、位运算、编码和计算机存储。

5. 函数与过程：把重复逻辑封装起来

函数让程序有结构。比如判断一个输入是否有效：

def is_four_digit_number(text):
    if len(text) != 4:
        return False

    for ch in text:
        if ch < "0" or ch > "9":
            return False

    return True

这个函数只做一件事：判断 text 是否由 4 个数字组成。

好的函数通常有几个特点：

• 函数名说明用途。
• 参数清晰。
• 返回值清晰。
• 不在一个函数里做太多事。
• 能被单独测试。

例如作业中常见的结构：

def validate_input(n):
    """Return True if n is a valid input, otherwise False."""
    pass


def sort_digits(n, descending=True):
    """Return digits of n sorted manually."""
    pass


def main():
    user_input = input("Enter a number: ")
    if validate_input(user_input):
        print(sort_digits(user_input))


main()

这种结构比把所有代码堆在一起更容易改，也更容易查 bug。

6. 条件判断：把问题变成分支

条件判断负责“如果这样，就做 A；否则，做 B”。

score = 86

if score >= 90:
    grade = "A"
elif score >= 80:
    grade = "B"
elif score >= 70:
    grade = "C"
else:
    grade = "D"

print(grade)

复杂条件可以用 and、or、not：

if age >= 18 and has_ticket:
    print("can enter")

条件判断的难点不是语法，而是边界：

• >= 还是 >？
• 多个条件有没有重叠？
• 是否覆盖了所有可能输入？
• 嵌套太深时能不能改成更清晰的结构？

一个判断三角形的例子：

def triangle_type(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return "not a triangle"

    if a + b <= c or a + c <= b or b + c <= a:
        return "not a triangle"

    if a == b == c:
        return "equilateral"
    elif a == b or a == c or b == c:
        return "isosceles"
    else:
        return "scalene"

注意这里先处理非法输入，再处理合法分类。这是写条件判断时很实用的顺序。

7. 循环：重复、累计与搜索

循环是程序处理批量任务的基础。

while 循环

适合“不知道要循环多少次”的情况：

n = int(input("Enter a positive number: "))
count = 0

while n > 0:
    n = n // 10
    count += 1

print(count)

for 循环

适合遍历一个范围或容器：

total = 0

for x in [3, 5, 7, 9]:
    total += x

print(total)

手写最大值

很多作业会要求不用内置函数，因为目的是训练算法流程：

def my_max(values):
    best = values[0]

    for x in values[1:]:
        if x > best:
            best = x

    return best

这个过程看似简单，但它是很多算法的基础：维护一个当前最优答案，然后不断更新。

8. 列表：Python 里的基础数据容器

列表用来保存一组有顺序的数据：

numbers = [5, 2, 9, 1]

print(numbers[0])   # 5
print(numbers[-1])  # 1

常见操作：

numbers.append(7)
numbers[1] = 100

for x in numbers:
    print(x)

如果需要同时拿到下标和值：

for i, x in enumerate(numbers):
    print(i, x)

初学时要特别注意：列表下标从 0 开始。长度为 n 的列表，合法下标是 0 到 n - 1。

9. 手写排序：从选择排序理解算法

课件中排序的思路是：每次找出当前列表中最小的数，放入新列表。

伪代码：

set result as empty list
repeat until original list is empty:
    find smallest value in original list
    append smallest value to result
    remove smallest value from original list

Python 实现：

def selection_sort(values):
    temp = values[:]
    result = []

    while len(temp) > 0:
        smallest_index = 0

        for i in range(1, len(temp)):
            if temp[i] < temp[smallest_index]:
                smallest_index = i

        result.append(temp[smallest_index])
        temp.pop(smallest_index)

    return result


print(selection_sort([1, 5, 8, 2, 7, 9]))

这不是最高效的排序方法，但很适合入门，因为逻辑直观。

你需要能说清楚：

• temp 是还没处理的数据。
• result 是已经排好的数据。
• 每一轮找一个最小值。
• 循环结束时，所有元素都被移动到 result。

10. 抽象：把复杂问题变成简单模型

抽象是计算思维中最重要的一步。

比如“帮员工按生日排序”这个问题，现实中有姓名、部门、职位、生日格式等很多细节。但如果当前目标只是按生日排序，我们可以先抽象成：

employees = [
    ("Alice", "03-15"),
    ("Bob", "01-20"),
    ("Chris", "12-05"),
]

然后问题变成：按 tuple 的第二个元素排序。

抽象不是忽略现实，而是暂时只保留当前问题需要的部分。做算法题、数据分析和机器学习时，这个能力非常重要：

• 推荐系统把用户行为抽象成 user-item interaction。
• 搜索系统把网页抽象成节点和链接。
• NLP 把文本抽象成 token 序列或 embedding。
• 图算法把城市道路抽象成节点和边。

11. 矩阵：用列表嵌套列表表示二维数据

Python 里可以用 list of lists 表示矩阵：

A = [
    [1, 2, 3],
    [4, 5, 6],
]

访问第 i 行第 j 列：

print(A[0][1])  # 2

矩阵乘法的核心是三层循环：

def matrix_multiply(A, B):
    rows = len(A)
    cols = len(B[0])
    inner = len(B)

    C = []

    for i in range(rows):
        row = []
        for j in range(cols):
            total = 0
            for k in range(inner):
                total += A[i][k] * B[k][j]
            row.append(total)
        C.append(row)

    return C

理解这段代码的关键：

• i 控制结果矩阵的行。
• j 控制结果矩阵的列。
• k 负责做点积。

矩阵很快会连接到后面的线性代数、图、机器学习。比如图的邻接矩阵就是一种矩阵。

12. 图：节点、边与关系建模

图由节点和边组成：

Graph = (V, E)

• V 是 vertices，也就是节点。
• E 是 edges，也就是边。

社交网络、道路、网页链接、知识图谱、推荐系统都可以用图来建模。

一个简单无向图：

nodes = ["a", "b", "c", "d"]
edges = [("a", "b"), ("a", "c"), ("b", "d")]

如果要快速查询某个点连着哪些点，更常用邻接表：

graph = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a"],
    "d": ["b"],
}

邻接矩阵则适合用二维列表表示：

matrix = [
    [0, 1, 1, 0],
    [1, 0, 0, 1],
    [1, 0, 0, 0],
    [0, 1, 0, 0],
]

邻接表和邻接矩阵的区别：

表示方式	优点	缺点
邻接表	节省空间，适合稀疏图	查询两点是否相连可能较慢
邻接矩阵	查询连接关系很快	节点多时占空间

13. BFS：无权图最短路

如果图是无权图，找最少边数的路径可以用 BFS。

def bfs_shortest_path(graph, start, target):
    queue = [(start, [start])]
    visited = {start}

    while queue:
        node, path = queue.pop(0)

        if node == target:
            return path

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))

    return None

例子：

graph = {
    "a": ["b", "c"],
    "b": ["a", "d"],
    "c": ["a", "d"],
    "d": ["b", "c", "e"],
    "e": ["d"],
}

print(bfs_shortest_path(graph, "a", "e"))

BFS 的思想是按层扩展：

• 先看距离起点 1 步的节点。
• 再看距离起点 2 步的节点。
• 第一次到达目标时，就是最短路径。

14. Dijkstra：带权图最短路

如果边有权重，比如道路距离、花费、时间，就不能只数边数。这个时候可以用 Dijkstra 算法。

一个带权图：

graph = {
    "a": [("b", 4), ("c", 2)],
    "b": [("a", 4), ("d", 5)],
    "c": [("a", 2), ("d", 1)],
    "d": [("b", 5), ("c", 1)],
}

不用高级库的简单版本：

def dijkstra(graph, start):
    distances = {}
    visited = set()

    for node in graph:
        distances[node] = float("inf")
    distances[start] = 0

    while len(visited) < len(graph):
        current = None
        current_distance = float("inf")

        for node in graph:
            if node not in visited and distances[node] < current_distance:
                current = node
                current_distance = distances[node]

        if current is None:
            break

        visited.add(current)

        for neighbor, weight in graph[current]:
            new_distance = distances[current] + weight
            if new_distance < distances[neighbor]:
                distances[neighbor] = new_distance

    return distances

Dijkstra 的核心是维护当前已知的最短距离，每次选择还没确定的节点中距离最小的那个，然后用它更新邻居。

这个思想以后会在搜索、推荐、路径规划、网络路由里反复出现。

15. Assignment 风格：不要只会调用内置函数

这类课程经常限制不能用内置排序、不能用外部库。原因不是 Python 没有这些功能，而是训练你理解背后的算法。

例如不能直接写：

sorted(values)

而要自己实现：

def sort_numbers(values):
    result = []
    temp = values[:]

    while temp:
        min_index = 0
        for i in range(1, len(temp)):
            if temp[i] < temp[min_index]:
                min_index = i

        result.append(temp.pop(min_index))

    return result

这对算法学习很有帮助。等你理解原理之后，在真实项目里当然应该优先使用标准库和成熟工具。

16. 一个完整小项目模板

写程序时可以用这个模板：

def read_input():
    """Read and return user input."""
    return input("Enter values: ")


def validate(data):
    """Return True if data is valid."""
    return len(data) > 0


def solve(data):
    """Core algorithm."""
    result = []

    for item in data:
        result.append(item)

    return result


def display(result):
    """Display result."""
    print(result)


def main():
    data = read_input()

    if not validate(data):
        print("Invalid input")
        return

    result = solve(data)
    display(result)


main()

这个结构对应：

input -> validation -> algorithm -> output

以后做更大的项目，比如数据清洗、模型训练、RAG demo，也可以沿用这个思路，只是每个函数会变得更复杂。

17. 怎么从这篇继续学

建议按这个顺序练：

1. 用伪代码写清楚问题流程。
2. 用 Python 写变量、条件、循环。
3. 把重复逻辑封装成函数。
4. 手写最大值、计数、搜索、排序。
5. 用 list of lists 表示矩阵。
6. 用 dict/list 表示图。
7. 写 BFS 找无权最短路。
8. 写简单 Dijkstra 找带权最短路。
9. 做 2 到 3 个综合小项目，把输入、处理、输出串起来。

如果目标是后续算法实习，这篇文章对应的是基础中的基础。真正重要的不是“背过 Python 语法”，而是看到一个问题时，能自然地问：

• 输入是什么？
• 输出是什么？
• 数据结构怎么选？
• 是否需要循环、条件或递归？
• 有没有边界情况？
• 算法会不会太慢？
• 能不能拆成几个函数？

这套思考方式一旦建立，后面学 Pandas、PyTorch、NLP、图算法、推荐系统都会轻松很多。

18. 最小练习清单

如果下面这些题能独立写出来，Python 计算思维入门就比较稳：

• 手写十进制转二进制。
• 判断一个字符串是否只包含数字。
• 统计一个整数有多少位。
• 输入一组数，手写最大值、最小值、平均值。
• 手写选择排序。
• 写一个函数判断三角形类型。
• 用二维列表实现矩阵加法。
• 用三层循环实现矩阵乘法。
• 用邻接表表示无向图。
• 写 BFS 找两个节点之间的最短路径。
• 写 Dijkstra 求起点到所有点的最短距离。
• 把一个完整题目拆成 validate_input、solve、display、main。

这些练习看起来朴素，但它们会直接支撑后面的算法题、数据结构和机器学习项目。