CS61A学习笔记
写在前面
CS61A的全称是Structure and Interpretation of Computer Programs（计算机程序的构造和解释），以Python语言授课。其课程内容主要是以Python为例，介绍程序设计中的各种方法，从控制语句到基础算法再到宏等。
单从课程目录来看，这门课与BIT开设的《C语言程序设计》有很多相似之处，虽然语言不同，但是思想却一致，所以学习CS61A并不需要按部就班的听每一节课，选择性地跳过已经学过的内容是高效的做法。
课程教材开源，可以直接阅读：Composing Programs
对于我个人来说，长期受C/C++、Java等强类型语言影响，很不适应Python的各种语法，学习本科目侧重于了解Python语言和编程思路，因而笔记也有不同的侧重点。
Part1 Python
Lecture 1 Welcome
主要是引入，强调了“表达式”概念
Lecture 2 Functions
变量与赋值
一个很神奇的Python变量赋值方式
1
|
f = max #max is a function
|
之后可以通过f来使用max
1
|
f(10,20,30) #30,相当于max(10,20,30)
|
个人认为这里相当于函数指针传递：
1
2
|
int max(int a,int b,int c);
int (*f)(int,int,int) = &max;
|
Python的特殊语法
显然相对于C语言，Python在变量上更加灵活。
需要注意的是在如下Python语句中：
1
2
3
|
a = 1
b = 2
a, b = a+b, a
|
a 最终为3，b最终为1，这里逗号表达式是同时进行赋值操作，所以不能理解为：
函数的返回值
C 语言借助void类型来显式表明函数无返回值，并且禁止把这类函数的调用结果用于赋值操作。而 Python 采用动态类型系统，不管函数是否有返回值都能进行赋值，没有返回值时就返回None。这体现了静态类型语言（C 语言）和动态类型语言（Python）在设计理念上的差异。
例如在一个C语言例子中：
1
2
3
4
5
6
7
8
9
10
11
12
|
#include <stdio.h>
void test(int a){
int b = a;
return;
}
int main(){
int b = test(2);
printf("%d",b);
return 0;
}
|
尝试编译运行会得到如下报错：
1
2
3
4
|
main.c: In function ‘main’:
main.c:12:13: error: void value not ignored as it ought to be
12 | int b = test(2);
| ^~~~
|
意味着编译器禁止了接收void类型函数返回值的行为。
而在python中，对于：
1
|
>>> print(print(1),print(2))
|
会有如下结果：
也就是说，Python的任意函数都有返回值，在没有显式写明返回值时，返回None。
需要注意的是None并不等同与NULL，None表示 “存在但无值”，可以参与逻辑判断如：
1
|
if a is None: #使用is进行身份判断
|
而NULL通常表示 “无效引用” 或 “未初始化”（如空指针、空引用），涉及内存/地址。
Lecture 3 Control
讲了一些Python的基本语法与解释器运行法则及其部分用法。
在Python中布尔值为False的有：False，0，''，None，其余为True。
Python中没有传统意义的for循环。
教你如何本地测评与上传代码，由于咱不是UCB的学生，所以也没有办法上传代码，这段跳过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
|
from operator import add, mul
def square(x):
return x * x
def identity(x):
return x
def triple(x):
return 3 * x
def increment(x):
return x + 1
from operator import add, sub
def a_plus_abs_b(a, b):
"""Return a+abs(b), but without calling abs.
>>> a_plus_abs_b(2, 3)
5
>>> a_plus_abs_b(2, -3)
5
>>> a_plus_abs_b(-1, 4)
3
>>> a_plus_abs_b(-1, -4)
3
"""
if b < 0:
f = sub
else:
f = add
return f(a, b)
def a_plus_abs_b_syntax_check():
"""Check that you didn't change the return statement of a_plus_abs_b.
>>> # You aren't expected to understand the code of this test.
>>> import inspect, re
>>> re.findall(r'^\s*(return .*)', inspect.getsource(a_plus_abs_b), re.M)
['return f(a, b)']
"""
# You don't need to edit this function. It's just here to check your work.
def hailstone(n):
"""Print the hailstone sequence starting at n and return its
length.
>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
>>> b = hailstone(1)
1
>>> b
1
"""
"*** YOUR CODE HERE ***"
print(n)
if n % 2 == 0:
return hailstone(n // 2) + 1
elif n % 2 != 0:
if n == 1:
return 1
else:
return hailstone(3 * n + 1) + 1
def product(n, term):
"""Return the product of the first n terms in a sequence.
n: a positive integer
term: a function that takes an index as input and produces a term
>>> product(3, identity) # 1 * 2 * 3
6
>>> product(5, identity) # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square) # 1^2 * 2^2 * 3^2
36
>>> product(5, square) # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple) # 1*3 * 2*3 * 3*3
162
"""
"*** YOUR CODE HERE ***"
if n == 1:
return term(1)
else:
return term(n) * product(n - 1, term)
def make_repeater(f, n):
"""Returns the function that computes the nth application of f.
>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 3)(5) # square(square(square(5)))
390625
"""
"*** YOUR CODE HERE ***"
def repeater(x):
if n == 0:
return x
else:
return make_repeater(f, n - 1)(f(x))
return repeater
|
Lecture 4 Higher-Order Functions
先讲了一些优先运算行为，比如在python中，函数的参数在传入前要依次进行运算等。该例子老师讲的很到位，不再赘述。
紧接着是高阶函数。实际上可以理解为Python的形式参数可以接收函数名并在函数内部调用函数；此外，Python允许嵌套函数。
例如：
1
2
3
4
5
6
7
|
def apply_twice(f, x):
return f(f(X))
def square(x):
return x * x
result = apply_twice(square, 2)
|
此时相当于：
1
|
result = square(square(2))
|
在C语言中可以尝试理解为：
1
2
3
4
5
6
7
8
9
10
11
12
|
int apply_twice(int (*f)(int), int x){
return f(f(x));
}
int square(int x){
return x * x;
}
int main(){
result = apply_twice(square, 2);
return 0;
}
|
其中，函数指针在C语言的声明方式为<返回值类型> (*指针名)(参数列表)
Lecture 5 Environments
Python的闭包
给到一个例子：
1
2
3
4
5
6
7
|
def make_adder(n):
def adder(k):
return n + k
return adder
add_three = make_adder(3)
add_three(4)
|
这段 Python 代码展示了闭包（Closure）的概念，即在函数内部定义的子函数可以捕获并记住外部函数的局部变量（本例子中为n），在C++11中引入的lambda表达式与Python的闭包极为相似，若用C++转写这段代码，可以写为：
1
2
3
4
5
6
7
8
9
10
11
|
auto make_adder(int n){
return [n](int k){
return n + k;
};
}
int main(){
auto add_three = make_adder(3);
std::cout << add_three(4) << endl;
return 0;
}
|
C++ 中的 lambda 表达式是 C++11 引入的一项重要特性，它允许你在代码中内联定义匿名函数对象，从而方便地实现闭包功能，其格式为[capture list](parameter list) -> return type { function body }
capture list为捕获列表，意味lambda表达式可从外界获取的参数，可以为引用，也可以为值；
parameter list为形式参数列表；
-> return type 为返回值类型，可以省略，由auto自动推断；
1
2
3
4
5
6
|
auto func = [](int x) { return x * 2; };
// 等价于以下类的实例：
struct __lambda {
int operator()(int x) const { return x * 2; }
};
auto func = __lambda{};
|
回到Python的例子，return adder相当于返回一个函数指针，如此便可以理解。
对于Python，它也有lambda表达式，形式较为简单：lambda <参数列表>: <表达式>，自动返回表达式的值，为匿名函数。需要注意的是，Python的lambda表达式没有C++的强大，仅能完成一些简单的表达式计算。
1
2
|
add = lambda a, b: a + b # 等价于 def add(a, b): return a + b
print(add(3, 4)) # 输出：7
|
前两个讨论题主要是关于Python的Shell，print可以打印字符，直接运行函数也可以显示其返回值，这里不再赘述。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
|
def falling(n, k):
"""Compute the falling factorial of n to depth k.
>>> falling(6, 3) # 6 * 5 * 4
120
>>> falling(4, 3) # 4 * 3 * 2
24
>>> falling(4, 1) # 4
4
>>> falling(4, 0)
1
"""
"*** YOUR CODE HERE ***"
ans = 1
i, j = k, n
while(i > 0):
ans *= j
j -= 1
i -= 1
return ans
def divisible_by_k(n, k):
"""
>>> a = divisible_by_k(10, 2) # 2, 4, 6, 8, and 10 are divisible by 2
2
4
6
8
10
>>> a
5
>>> b = divisible_by_k(3, 1) # 1, 2, and 3 are divisible by 1
1
2
3
>>> b
3
>>> c = divisible_by_k(6, 7) # There are no integers up to 6 that are divisible by 7
>>> c
0
"""
"*** YOUR CODE HERE ***"
count = 0
i = 1
while(i <= n):
if i % k == 0:
print(i)
count += 1
i += 1
return count
def double_eights(n):
"""Return true if n has two eights in a row.
>>> double_eights(8)
False
>>> double_eights(88)
True
>>> double_eights(2882)
True
>>> double_eights(880088)
True
>>> double_eights(12345)
False
>>> double_eights(80808080)
False
"""
"*** YOUR CODE HERE ***"
while(n >= 10):
if n % 10 == 8 and (n // 10) % 10 == 8:
return True
n //= 10
return False
def two_of_three(i, j, k):
"""Return m*m + n*n, where m and n are the two smallest members of the
positive numbers i, j, and k.
>>> two_of_three(1, 2, 3)
5
>>> two_of_three(5, 3, 1)
10
>>> two_of_three(10, 2, 8)
68
>>> two_of_three(5, 5, 5)
50
"""
return min(i, j, k) ** 2 + max(min(i, j),min(j, k),min(i, k)) ** 2
def two_of_three_syntax_check():
"""Check that your two_of_three code consists of nothing but a return statement.
>>> # You aren't expected to understand the code of this test.
>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(two_of_three)).body[0].body]
['Expr', 'Return']
"""
# You don't need to edit this function. It's just here to check your work.
def middle(a, b, c):
"""Return the number among a, b, and c that is not the smallest or largest.
Assume a, b, and c are all different numbers.
>>> middle(3, 5, 4)
4
>>> middle(30, 5, 4)
5
>>> middle(3, 5, 40)
5
>>> middle(3, 5, 40)
5
>>> middle(30, 5, 40)
30
"""
return max(min(a, b),min(b, c),min(a, c))
def largest_factor(n):
"""Return the largest factor of n that is smaller than n.
>>> largest_factor(15) # factors are 1, 3, 5
5
>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
40
>>> largest_factor(13) # factors are 1, 13
1
"""
"*** YOUR CODE HERE ***"
for i in range(n - 1, 0, -1):
if n % i == 0:
return i
return 1
def multiple(a, b):
"""Return the smallest number n that is a multiple of both a and b.
>>> multiple(3, 4)
12
>>> multiple(14, 21)
42
"""
"*** YOUR CODE HERE ***"
def gcd(x, y):
while y:
x, y = y, x % y
return x
def lcm(x, y):
return (x * y) // gcd(x, y)
return lcm(a, b)
|
Lecture 6 Sound (Optional)
选修课，用python制作wav音频
规则
在 Hog 游戏中，两名玩家轮流尝试成为第一个以至少 GOAL 总分结束回合的人，其中 GOAL 默认为 100。在每个回合中，当前玩家选择掷出一些骰子，最多 10 个。该玩家该回合的分数是骰子结果的总和。但是，掷出太多骰子的玩家会面临以下风险：
- 逢一判负：如果掷出的骰子中任何一个为 1，则当前玩家该回合得分为 1。(英文名：Sow Sad)
- 示例 1： 当前玩家掷出 7 个骰子，其中 5 个骰子的结果为 1。他们该回合得
1 分。
- 示例 2： 当前玩家掷出 4 个骰子，所有骰子的结果均为 3。由于未发生逢一判负，他们该回合得
12 分。
在正常的 Hog 游戏中，这些就是所有的规则。为了给游戏增添趣味，我们将加入一些特殊规则：
- 野猪乱斗：当玩家掷出零个骰子时，其得分为对手分数十位与自身分数个位之差的绝对值的三倍，或者 1 分，取两者中的较大值。(英文名：Boar Brawl) 个位数为最右边的数字，十位数为倒数第二位数字。如果玩家的分数是个位数（小于 10），则该玩家分数的十位数为 0。
- 示例 1：
- 当前玩家有
21 分，对手有 46 分，当前玩家选择不掷骰子。
- 对手分数的十位数为
4，当前玩家分数的个位数为 1。
- 因此，玩家获得
3 * abs(4 - 1) = 9 分。
- 示例 2：
- 当前玩家有
45 分，对手有 52 分，当前玩家选择跳过掷骰子环节。
- 对手分数的十位数为
5，当前玩家分数的个位数为 5。
- 由于
3 * abs(5 - 5) = 0，因此玩家获得 1 分。
- 示例 3：
- 当前玩家有
2 分，对手有 5 分，当前玩家选择掷出零个骰子。
- 对手分数的十位数为
0，当前玩家分数的个位数为 2。
- 因此，玩家获得
3 * abs(0 - 2) = 6 分。
- Sus Fuss。如果一个数字恰好有 3 个或 4 个因子（包括 1 和它本身），我们就称它为 sus，即满足“可疑”条件的数字。如果在掷骰子后，当前玩家的分数是一个 sus 数字，那么他们的分数会直接提升至下一个质数。
- 示例 1：
- 玩家有 14 分，掷出 2 个骰子，总共得到 7 分。他们的新分数将是 21，新分数 21 包含四个因子：1、3、7 和 21。因为 21 是 sus，所以玩家的分数增加到 23，即下一个质数。
- 示例 2：
- 玩家有 63 分，掷出 5 个骰子，总共得到 1 分。他们的新分数将是 64，它有 7 个因子：1、2、4、8、16、32 和 64。因为 64 不是 sus，所以玩家的分数保持不变。
- 示例 3：
- 玩家有 49 分，掷出 5 个骰子，总共得到 18 分。他们的新分数将是 67，这是一个质数，有 2 个因子：1 和 67。因为 67 不是 sus，所以玩家的分数保持不变。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
|
"""The Game of Hog."""
#./hog.py
#author:lamaper
from dice import six_sided, make_test_dice
from ucb import main, trace, interact
GOAL = 100 # The goal of Hog is to score 100 points.
######################
# Phase 1: Simulator #
######################
def roll_dice(num_rolls, dice=six_sided):
"""Simulate rolling the DICE exactly NUM_ROLLS > 0 times. Return the sum of
the outcomes unless any of the outcomes is 1. In that case, return 1.
num_rolls: The number of dice rolls that will be made.
dice: A function that simulates a single dice roll outcome. Defaults to the six sided dice.
"""
# These assert statements ensure that num_rolls is a positive integer.
assert type(num_rolls) == int, "num_rolls must be an integer."
assert num_rolls > 0, "Must roll at least once."
# BEGIN PROBLEM 1
"*** YOUR CODE HERE ***"
i = 0
total = 0
while(i < num_rolls):
roll = dice()
if roll == 1:
return 1
total += roll
i += 1
return total
# END PROBLEM 1
def boar_brawl(player_score, opponent_score):
"""Return the points scored when the current player rolls 0 dice according to Boar Brawl.
player_score: The total score of the current player.
opponent_score: The total score of the other player.
"""
# BEGIN PROBLEM 2
"*** YOUR CODE HERE ***"
a = player_score % 10
b = (opponent_score // 10) % 10
return max(3 * abs(a - b), 1)
# END PROBLEM 2
def take_turn(num_rolls, player_score, opponent_score, dice=six_sided):
"""Return the points scored on a turn rolling NUM_ROLLS dice when the
current player has PLAYER_SCORE points and the opponent has OPPONENT_SCORE points.
num_rolls: The number of dice rolls that will be made.
player_score: The total score of the current player.
opponent_score: The total score of the other player.
dice: A function that simulates a single dice roll outcome.
"""
# Leave these assert statements here; they help check for errors.
assert type(num_rolls) == int, "num_rolls must be an integer."
assert num_rolls >= 0, "Cannot roll a negative number of dice in take_turn."
assert num_rolls <= 10, "Cannot roll more than 10 dice."
# BEGIN PROBLEM 3
"*** YOUR CODE HERE ***"
if num_rolls == 0:
return boar_brawl(player_score, opponent_score)
else:
return roll_dice(num_rolls, dice)
# END PROBLEM 3
def simple_update(num_rolls, player_score, opponent_score, dice=six_sided):
"""Return the total score of a player who starts their turn with
PLAYER_SCORE and then rolls NUM_ROLLS DICE, ignoring Sus Fuss.
"""
score = player_score + take_turn(num_rolls, player_score, opponent_score, dice)
return score
def is_prime(n):
"""Return whether N is prime."""
if n == 1:
return False
k = 2
while k < n:
if n % k == 0:
return False
k += 1
return True
def num_factors(n):
"""Return the number of factors of N, including 1 and N itself."""
# BEGIN PROBLEM 4
"*** YOUR CODE HERE ***"
if n == 1:
return 1
if is_prime(n):
return 2
count = 0
for i in range(1, n + 1):
if n % i == 0:
count += 1
return count
# END PROBLEM 4
def sus_points(score):
"""Return the new score of a player taking into account the Sus Fuss rule."""
# BEGIN PROBLEM 4
"*** YOUR CODE HERE ***"
sus = num_factors(score)
if sus == 3 or sus == 4:
i = score
while not is_prime(i):
i += 1
return i
else :
return score
# END PROBLEM 4
def sus_update(num_rolls, player_score, opponent_score, dice=six_sided):
"""Return the total score of a player who starts their turn with
PLAYER_SCORE and then rolls NUM_ROLLS DICE, *including* Sus Fuss.
"""
# BEGIN PROBLEM 4
"*** YOUR CODE HERE ***"
score = take_turn(num_rolls, player_score, opponent_score, dice)
return sus_points(player_score + score)
# END PROBLEM 4
def always_roll_5(score, opponent_score):
"""A strategy of always rolling 5 dice, regardless of the player's score or
the opponent's score.
"""
return 5
def play(strategy0, strategy1, update, score0=0, score1=0, dice=six_sided, goal=GOAL):
"""Simulate a game and return the final scores of both players, with
Player 0's score first and Player 1's score second.
E.g., play(always_roll_5, always_roll_5, sus_update) simulates a game in
which both players always choose to roll 5 dice on every turn and the Sus
Fuss rule is in effect.
A strategy function, such as always_roll_5, takes the current player's
score and their opponent's score and returns the number of dice the current
player chooses to roll.
An update function, such as sus_update or simple_update, takes the number
of dice to roll, the current player's score, the opponent's score, and the
dice function used to simulate rolling dice. It returns the updated score
of the current player after they take their turn.
strategy0: The strategy for player0.
strategy1: The strategy for player1.
update: The update function (used for both players).
score0: Starting score for Player 0
score1: Starting score for Player 1
dice: A function of zero arguments that simulates a dice roll.
goal: The game ends and someone wins when this score is reached.
"""
who = 0 # Who is about to take a turn, 0 (first) or 1 (second)
# BEGIN PROBLEM 5
"*** YOUR CODE HERE ***"
while score0 < goal and score1 < goal:
if who == 0:
num_rolls = strategy0(score0, score1)
score0 = update(num_rolls, score0, score1, dice)
if score0 >= goal:
break
who = 1
else:
num_rolls = strategy1(score1, score0)
score1 = update(num_rolls, score1, score0, dice)
if score1 >= goal:
break
who = 0
# END PROBLEM 5
return score0, score1
#######################
# Phase 2: Strategies #
#######################
def always_roll(n):
"""Return a player strategy that always rolls N dice.
A player strategy is a function that takes two total scores as arguments
(the current player's score, and the opponent's score), and returns a
number of dice that the current player will roll this turn.
>>> strategy = always_roll(3)
>>> strategy(0, 0)
3
>>> strategy(99, 99)
3
"""
assert n >= 0 and n <= 10
# BEGIN PROBLEM 6
"*** YOUR CODE HERE ***"
def strategy(score, opponent_score):
"""Return the number of dice to roll."""
return n
return strategy
# END PROBLEM 6
def catch_up(score, opponent_score):
"""A player strategy that always rolls 5 dice unless the opponent
has a higher score, in which case 6 dice are rolled.
>>> catch_up(9, 4)
5
>>> strategy(17, 18)
6
"""
if score < opponent_score:
return 6 # Roll one more to catch up
else:
return 5
def is_always_roll(strategy, goal=GOAL):
"""Return whether STRATEGY always chooses the same number of dice to roll
for every possible combination of score and opponent_score
given a game that goes to GOAL points.
>>> is_always_roll(always_roll_5)
True
>>> is_always_roll(always_roll(3))
True
>>> is_always_roll(catch_up)
False
"""
# BEGIN PROBLEM 7
"*** YOUR CODE HERE ***"
for score in range(goal):
for opponent_score in range(goal):
if strategy(score, opponent_score) != strategy(0, 0):
return False
return True
# END PROBLEM 7
def make_averaged(original_function, times_called=1000):
"""Return a function that returns the average value of ORIGINAL_FUNCTION
called TIMES_CALLED times.
To implement this function, you will have to use *args syntax.
>>> dice = make_test_dice(4, 2, 5, 1)
>>> averaged_dice = make_averaged(roll_dice, 40)
>>> averaged_dice(1, dice) # The avg of 10 4's, 10 2's, 10 5's, and 10 1's
3.0
"""
# BEGIN PROBLEM 8
"*** YOUR CODE HERE ***"
def averaged_function(*args):
total = 0
for _ in range(times_called):
total += original_function(*args)
return total / times_called
return averaged_function
# END PROBLEM 8
def max_scoring_num_rolls(dice=six_sided, times_called=1000):
"""Return the number of dice (1 to 10) that gives the maximum average score for a turn.
Assume that the dice always return positive outcomes.
>>> dice = make_test_dice(1, 6)
>>> max_scoring_num_rolls(dice)
1
"""
# BEGIN PROBLEM 9
"*** YOUR CODE HERE ***"
max_score = 0
min_rolls = 11
for num_rolls in range(1, 11):
score = make_averaged(roll_dice, times_called)(num_rolls, dice)
if score > max_score:
max_score = score
min_rolls = num_rolls
elif score == max_score:
min_rolls = min(min_rolls, num_rolls)
return min_rolls
# END PROBLEM 9
def winner(strategy0, strategy1):
"""Return 0 if strategy0 wins against strategy1, and 1 otherwise."""
score0, score1 = play(strategy0, strategy1, sus_update)
if score0 > score1:
return 0
else:
return 1
def average_win_rate(strategy, baseline=always_roll(6)):
"""Return the average win rate of STRATEGY against BASELINE. Averages the
winrate when starting the game as player 0 and as player 1.
"""
win_rate_as_player_0 = 1 - make_averaged(winner)(strategy, baseline)
win_rate_as_player_1 = make_averaged(winner)(baseline, strategy)
return (win_rate_as_player_0 + win_rate_as_player_1) / 2
def run_experiments():
"""Run a series of strategy experiments and report results."""
six_sided_max = max_scoring_num_rolls(six_sided)
print("Max scoring num rolls for six-sided dice:", six_sided_max)
print("always_roll(6) win rate:", average_win_rate(always_roll(6))) # near 0.5
print("catch_up win rate:", average_win_rate(catch_up))
print("always_roll(3) win rate:", average_win_rate(always_roll(3)))
print("always_roll(8) win rate:", average_win_rate(always_roll(8)))
print("boar_strategy win rate:", average_win_rate(boar_strategy))
print("sus_strategy win rate:", average_win_rate(sus_strategy))
print("final_strategy win rate:", average_win_rate(final_strategy))
"*** You may add additional experiments as you wish ***"
def boar_strategy(score, opponent_score, threshold=11, num_rolls=6):
"""This strategy returns 0 dice if Boar Brawl gives at least THRESHOLD
points, and returns NUM_ROLLS otherwise. Ignore the Sus Fuss rule.
"""
# BEGIN PROBLEM 10
if boar_brawl(score, opponent_score) >= threshold:
return 0
else:
return num_rolls
# END PROBLEM 10
def sus_strategy(score, opponent_score, threshold=11, num_rolls=6):
"""This strategy returns 0 dice when rolling 0 increases the score by at least
THRESHOLD points, and returns NUM_ROLLS otherwise. Consider both the Boar Brawl and
Suss Fuss rules."""
# BEGIN PROBLEM 11
if sus_points(score + boar_brawl(score, opponent_score)) - score >= threshold:
return 0
else:
return num_rolls
# END PROBLEM 11
def final_strategy(score, opponent_score):
"""Write a brief description of your final strategy.
*** YOUR DESCRIPTION HERE ***
"""
# BEGIN PROBLEM 12
return 6 # Remove this line once implemented.
# END PROBLEM 12
##########################
# Command Line Interface #
##########################
# NOTE: The function in this section does not need to be changed. It uses
# features of Python not yet covered in the course.
@main
def run(*args):
"""Read in the command-line argument and calls corresponding functions."""
import argparse
parser = argparse.ArgumentParser(description="Play Hog")
parser.add_argument(
"--run_experiments", "-r", action="store_true", help="Runs strategy experiments"
)
args = parser.parse_args()
if args.run_experiments:
run_experiments()
|
一个简单的项目实现，主要难在语言不通，题设很巧妙，需要我们用到前六节课所学的知识。
最终python3 -i hog.py有如下测试结果：
1
2
3
4
5
6
7
8
9
10
|
>>> run_experiments()
Max scoring num rolls for six-sided dice: 7
always_roll(6) win rate: 0.494
catch_up win rate: 0.5125
always_roll(3) win rate: 0.34850000000000003
always_roll(8) win rate: 0.4635
boar_strategy win rate: 0.6685000000000001
sus_strategy win rate: 0.6910000000000001
final_strategy win rate: 0.511
|
与题设在问题10的预期“You should find that running now shows the boar_strategy win rate for close to 66-67%.”
Lecture 7 Function Abstruction
函数抽象，主要是进一步介绍高阶函数与lambda表达式。
在课程结尾还讲了Error和Traceback
Lecture 8 Function Examples
Python修饰器
在 Python 中，装饰器（Decorator）是一种强大的语法糖，允许在不修改原有函数代码的情况下，增强或修改函数的行为。它们本质上是一个可调用对象（函数、类等），接受一个函数作为输入，并返回另一个函数。
下面是一个例子：
1
2
3
4
5
6
7
8
9
|
def trace(fn):
def traced(x):
print("Calling",fn,"on argument",x)
return fn(x)
return traced
@trace
def square(x):
return x * x
|
其中，被trace修饰的squre可以等价于：
相当于把函数squre作为参数传入trace。
trace函数接收原始的square函数作为参数fn。trace内部定义了traced函数并返回它，这个traced函数会替代原始的square函数。- 新的
square实际上是trace返回的traced函数。
所以当调用square(5)时，参数5被传递给traced函数的x参数。
用C语言实现修饰器的效果则如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
typedef int (*Function)(int);
int square(int x){
return x * x;
}
Function trace(Function func){
static int traced(int x){
printf("Calling %p on argument %d\n", (void*)func, x);
return func(x);
}
return traced;
}
int main(){
//@trace
Function decorated = trace(square);
printf("Result: %d\n",decorated(5));
return 0;
}
|
Lecture 9 Recursion
递归，比较重要的章节，主要是思路，个人认为这里以Python的Environment来解释递归不如直接上树形结构来的直观。实际上下一节课（lecture 10）就是树形递归。
在Python中实现递归会比较方便，因为python提供了灵活的函数返回值，使我们可以返回若干不同类型的值，不同于C/C++，因而在写代码的时候会更简洁一点。
Lecture 10 Tree-Recursion
本节课在最后提到了用树形递归加速斐波那契数列问题，实际上这是一个子问题分解，也可以理解为一种特殊的动态规划。
传统的斐波那契直接遵循其递推关系描述：
1
2
3
4
|
def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n-1) + fib_recursive(n-2)
|
我们会发现其存在严重的重复计算问题，利用树形递归的思想，可以加速算法的实现：
1
2
3
4
5
6
7
8
9
10
|
def fib_iterative(n):
if n <= 1:
return n
a, b = 0, 1 # 初始化F(0)和F(1)
for _ in range(2, n+1):
c = a + b # 计算F(i) = F(i-1) + F(i-2)
a, b = b, c # 滑动窗口更新
return b
|
Lecture 11 Sequences
Python数据类型：List
列表（list）是有限长度的相同类型的数据的集合，可以类比其他语言的数组，但比它们更强大。
定义一个列表：
与其他语言相似地，列表的可以被索引访问，索引从0开始，因而dist[0]=1，利用相应函数可以获取列表的的长度，len(dist)的值为3。
python允许多维数组，如：
1
2
3
4
5
|
>>> pairs = [[10, 20], [30, 40]]
>>> pairs[1]
[30, 40]
>>> pairs[1][0]
30
|
python为使用者提供了语法糖，如：
1
2
3
|
>>> digits = [1, 8, 2, 8]
>>> [2, 7] + digits * 2
[2, 7, 1, 8, 2, 8, 1, 8, 2, 8]
|
可以发现digits被复制为2份。
列表的语法糖可以快速生成符合要求的序列：
1
2
3
|
>>> odds = [1,2,3,4,5,6,7,8,9,10]
>>> [x for x in odds if x % 2 == 0]
[2,4,6,8,10]
|
for循环
python优化了for循环，如果需要对digits进行遍历，可以有如下操作：
1
2
|
for elem in digits:
print(elem)
|
可以认为elem为digits的元素，并随着每次循环elem自动向后改变，直到最后一个元素。
range(x,y)是一个python内置序列，可以理解为一个左闭右开区间，如：
1
2
3
|
sum = 0
for i in range(1,11):
sum += i
|
可以等价于
$$
i \in [1,11) = [1,10]\\
sum = \sum^{10}_{i=1}i
$$
但是要注意，in作为运算符，其表达式返回一个布尔类型的值，如1 in digist的返回值为Ture。
此外，:运算符也可作为区间，依然符合左闭右开法则，左端省略则认为从0开始，右端省略则认为到最后。如dist[1:3]表示为从元素1到元素2的子序列
Lecture 12 Containers
List相关的内联函数
使用sum(<list>)可以简单实现列表的加和。
如：
1
2
3
4
|
>>> [2,3] + [4]
[2,3,4]
>>> sum([2,3],[4])
[2,3,4]
|
String
exec()可接受string类型的参数并作为命令执行。
可以将String理解为特殊的列表。
字典（Dictionary）
在 Python 里，字典（dict）的功能和其他编程语言中的 Map（或者叫哈希表、关联数组）是类似的。它们都借助 键值对（key-value pairs） 来存储数据，而且键都是唯一的，如果重复赋值，后面的值会覆盖前面的值。其中键必须是可哈希（不可变）的类型，像字符串、数字、元组（元组里的元素也得是可哈希的）。Python 3.7之后字典会保持插入顺序，迭代时会按照键值对插入的顺序返回。
Lecture 13 Data Abstraction
数据抽象是一个方法论，核心是改变一个功能时不影响另一个功能。
Lecture 14 Trees
主要讲述用列表实现树这个数据结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
def tree(root, branches=[]):
for branch in branches:
assert is_tree(branch)
return [root] + list(branches)
def root(tree):
return tree[0]
def branches(tree):
return tree[1:]
def is_tree(tree):
if type(tree) != list or len(tree) < 1 :
return False
for branch in branches(tree):
if not is_tree(branch):
return False
return Ture
def is_leaf(tree):
return not branches(tree)
|
本节课很有用，建议重复学习。
Lecture 15 Mutability
对象（Objects)
本节课终于讲到了对象。面向对象思想深深影响了现代编程语言，个人认为用Java学习面向对象会强过任何语言，因为Java的强面向对象性可以使我们更深刻的理解其特点。
面向对象要求对象拥有属性和方法，大多数编程语言调用对象的属性与方法都会使用.；
但这里只是简单的提及，后面应该会细讲
元组（Tuples）
元组相当于一个逗号序列，但是不可变，这不同于列表。列表是可变的。
这里所说的元组不可变是指大小或者结构，即空间不变，而非值不变。
可变性
在 Python 中，参数传递的方式既不是单纯的值传递，也不是单纯的引用传递，而是采用共享传递（Call by Sharing），也被称作对象引用传递。下面详细解释：
共享传递的核心特点
- 变量是对象的引用：Python 里，变量存放的是对象的引用，并非对象本身。
- 参数传递时引用被复制：当把参数传递给函数时，实际上是将变量的引用复制给了函数参数。这就使得函数内部的参数和外部的变量指向同一个对象。
- 对象的可变性决定了修改行为：
- 对于可变对象（如列表、字典、集合），在函数内部对其进行修改，外部的原始对象也会受到影响。
- 对于不可变对象（如整数、字符串、元组），由于无法修改对象本身，在函数内部对参数进行重新赋值时，只是让参数指向了一个新对象，不会改变外部的原始对象。
Lecture 16 Iterators
迭代器（Iterator）
在 Python 中，迭代器（Iterator）是实现了迭代器协议的对象，它允许你逐个访问集合中的元素，而无需预先加载整个集合到内存中。这一特性使得 Python 能够高效处理大规模数据，也是 Python 中循环、生成器和许多内置函数的核心机制。
迭代器必须实现两个核心方法：
__iter__()：返回迭代器自身（self），用于在for循环等场景中获取迭代器。__next__()：返回迭代器的下一个元素。当没有更多元素时，抛出StopIteration异常。
迭代器是一次性的，当next为None时结束迭代。
惰性计算（Lazy Evaluation）
在 Python 中，惰性计算（Lazy Evaluation） 是一种重要的编程策略，它允许程序在需要时才进行计算，而非提前计算所有结果。这一特性显著提升了内存效率和程序性能，尤其适用于处理大数据、无限序列或复杂计算。
许多Python的内置函数返回类型为迭代器：
-
map(func, iterable)：将函数应用到每个元素。
1
2
|
nums = [1, 2, 3]
squares = map(lambda x: x**2, nums) # 返回map对象（迭代器）
|
-
filter(predicate, iterable)：过滤符合条件的元素。
1
|
evens = filter(lambda x: x % 2 == 0, nums) # 返回filter对象
|
-
zip(*iterables)：并行迭代多个序列。
1
2
3
|
names = ['Alice', 'Bob']
ages = [25, 30]
zipped = zip(names, ages) # 返回zip对象
|
此外， itertools模块也提供了多种惰性工具。
Lecture 17 Generators
生成器
在Python中，生成器（Generators） 是实现惰性计算的一种特殊工具，它允许你在需要时才生成数据，而非一次性计算并存储所有结果。这使得代码更高效、更节省内存，尤其适合处理大数据或无限序列。生成器是一种特殊的迭代器，它的创建方式更简洁：
- 生成器函数：使用
yield关键字的函数。
- 生成器表达式：类似列表推导式，但用圆括号
()。
| 特性 |
普通函数 |
生成器函数 |
| 执行方式 |
一次性执行完毕 |
可以暂停和恢复执行 |
| 状态保存 |
不保存状态，每次调用重置 |
保存上一次暂停的状态 |
| 返回值 |
return返回单个值 |
yield返回迭代器（生成器） |
| 内存占用 |
可能高（存储所有结果） |
低（按需生成） |
使用yield关键字定义，每次调用next()时恢复执行：
1
2
3
4
5
6
7
8
9
10
11
12
|
def countdown(n):
while n > 0:
yield n # 暂停执行并返回当前值
n -= 1
# 创建生成器对象
c = countdown(3)
print(next(c)) # 3
print(next(c)) # 2
print(next(c)) # 1
print(next(c)) # StopIteration异常
|
执行流程：
- 调用生成器函数时，函数体不会立即执行，而是返回一个生成器对象。
- 每次调用
next()时，函数恢复执行，直到遇到yield暂停。
- 状态（变量值）会被保存，下次调用
next()时继续执行。
生成器表达式（Generator Expressions）语法类似列表推导式，但用圆括号：
1
2
3
4
5
6
7
8
|
# 列表推导式：立即生成列表
squares_list = [x**2 for x in range(5)] # [0, 1, 4, 9, 16]
# 生成器表达式：返回生成器对象
squares_gen = (x**2 for x in range(5)) # 生成器对象
print(next(squares_gen)) # 0
print(next(squares_gen)) # 1
|
高级生成器特性
send()方法
向生成器内部发送值并恢复执行：
1
2
3
4
5
6
7
8
9
|
def receiver():
while True:
item = yield # 接收外部发送的值
print(f"Received: {item}")
r = receiver()
next(r) # 启动生成器，必须先调用一次
r.send("Hello") # 发送值并恢复执行 → 输出: Received: Hello
r.send("World") # → 输出: Received: World
|
throw()和close()
throw()：向生成器抛出异常。close()：终止生成器。
1
2
3
4
|
gen = (x for x in range(5))
print(next(gen)) # 0
gen.close()
print(next(gen)) # StopIteration异常（生成器已关闭）
|
yield from（Python 3.3+）
委托子生成器：
1
2
3
4
5
6
7
8
9
|
def sub_generator():
yield 1
yield 2
def main_generator():
yield from sub_generator() # 委托子生成器
gen = main_generator()
print(list(gen)) # [1, 2]
|
Lecture 18 Objects
面向对象编程（Object-Oriented Programming，OOP）是一种编程范式，它将数据（属性）和操作数据的方法（行为）封装在对象中，并通过类来定义对象的结构和行为。Python 是一门支持面向对象编程的语言，提供了类、继承、多态等核心特性。类是对象的蓝图，定义了对象的属性和方法。对象是类的实例，具有类定义的属性和方法。
在Python中：
1
2
3
4
5
6
7
|
class Students:
#属性
name = "Jack"
age = 18
#方法
def drink():
print("drinking!")
|
在C++中：
1
2
3
4
5
6
7
8
9
10
11
12
|
class Students{
#属性
private:
string name;
int age;
#方法
public:
void drink(){
printf("drinking!\n");
}
};
|
在Java中：
1
2
3
4
5
6
7
8
|
public class Students{
private String name;
private int age;
public void drink(){
System.out.println("drinking!");
}
}
|
Lecture 19 Attributes
当我们需要调用创建对象时：
1
|
stu = Students() #python
|
1
|
Students stu = new Students(); //Java
|
此后如果需要调用对象的属性，可使用.来操作即可。
构造器/构造函数
在python中，如果需要在创建对象时对对象的属性进行初始化，则需要用到内联函数__init__():
1
2
3
4
5
6
7
8
|
class Students:
#没有特殊的初始化属性
def __init__(self, name, age):
self.name = name
self.age = age
Tom = Student('Tom',18)
print(Tom.name) #Tom
|
这里的self不是需要填写的形式参数，而是所有实例方法必须有的参数，指实例自己。
如果熟悉C/C++或Java的人会在这里感到迷惑，因为name和age并没有被显式地定义。事实上这在Python中是被允许的，但是在其它很多语言中是不被允许的，例如Java：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
public class Students{
private String name;//显式地定义属性，相当于实例化前的self.name
private int age;
public Student(String name,int age){
this.name = name;
this.age = age;
}
}
public class Main{
public static void main(String args[]){ //main函数
Students Tom = new Students("Tom",18);
System.out.println(Tom.name);
}
}
|
在Java中，初始化函数/构造函数被成为构造器，是一个不需要声明返回值的、和类名称相同的函数。this关键字类似于self，这里的this.age等于在前面声明的private int age，而age是形式参数中的age。
在C++中：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Students{
private:
string name;
int age;
public:
Students(string _name,int _age){
name = _name;
age = _age;
}
~Students(){
delete[] string;
delete age;
}
};
|
初始化函数/构造函数被成为构造函数，是一个不需要声明返回值的、和类名称相同的函数，与其匹配的是析构函数，在删除对象时调用。
Lecture 20 Inheritance
继承，即子类继承父类的属性和方法，可扩展或修改父类行为。可以认为是父类的拓展。
在python中：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Animal:
def speak(self):
return "Generic sound"
def drink(self):
return "drink"
class Cat(Animal): # 继承自Animal
def speak(self): # 方法重写
return "Meow"
cat = Cat()
print(cat.speak()) # → "Meow"
print(cat.drink()) # → "drink"
|
方法重写是指在子类中实现与父类同名的函数时，其功能会覆盖父类的功能，当你调用时，使用的是子类实现的功能。当子类没有实现时，依旧可以调用该功能，此时是父类实现的功能。
面向对象的核心奥义之一是：不要重复实现方法。这也是继承这一特性出现的原因。
Lecture 21 Representation
represent
在 Python 里，repr() 是一个内置函数，其作用是返回一个对象的字符串表示形式，并且这个字符串应当是可解析的，或者说能清晰展示对象内容。
这意味着使用repr()可以获取构造该对象的代码。
如：
1
2
3
4
5
6
|
import datetime
today = datetime.datetime.now()
print(str(today)) # 输出：2025-07-05 12:30:45.123456（便于用户阅读）
print(repr(today)) # 输出：datetime.datetime(2025, 7, 5, 12, 30, 45, 123456)（便于开发者理解）
|
1
2
|
points = [Point(0, 0), Point(1, 1)]
print(points) # 输出：[Point(0, 0), Point(1, 1)]
|
在自定义类中，我们可以通过 __repr__() 方法来定义对象的 repr() 输出。按照惯例，这个方法返回的字符串格式应该是 ClassName(arg1, arg2, ...)：
1
2
3
4
5
6
7
8
9
10
|
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __repr__(self):
return f'Point({self.x}, {self.y})'
p = Point(3, 4)
print(repr(p)) # 输出：Point(3, 4)
|
格式化字符串
Python 3.6之后引入了全新的格式化字符串方法，也就是课程视频中提到的F-String。直接在大括号中输入表达式即可。
如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
name = "David"
age = 40
print(f"Hello, {name}! You are {age} years old.")
# 输出：Hello, David! You are 40 years old.
x = 10
y = 20
print(f"The sum of {x} and {y} is {x + y}")
# 输出：The sum of 10 and 20 is 30
text = "hello"
print(f"Uppercase: {text.upper()}")
# 输出：Uppercase: HELLO
price = 9.99
print(f"Price: ${price:.2f}") # 保留2位小数
# 输出：Price: $9.99
person = {"name": "Eve", "age": 28}
print(f"{person['name']} is {person['age']} years old")
# 输出：Eve is 28 years old
|
这与C语言的格式化字符串有些许不同：
1
2
3
|
char name[] = "David";
int age = 40;
printf("Hello, %s! You are %d years old.\n",name,age);
|
魔术方法（Magic Methods）
在 Python 中，魔术方法（Magic Methods）也被称为特殊方法（Special Methods），是一类以双下划线 __ 开头和结尾的特殊方法。它们为类提供了丰富的内置功能，使得自定义类能够像内置类型一样进行各种操作（如加减乘除、迭代、比较等）。
初始化与销毁：
__init__(self, ...)类的构造函数，创建对象时自动调用。__del__(self)对象被销毁时调用（垃圾回收前），常用于资源释放。
字符串表示：
__str__(self)返回用户友好的字符串表示，用于 print() 和 str()。__repr__(self)返回开发者友好的字符串表示，用于调试和 repr()。
算术运算符：
__sub__：减法（-）__mul__：乘法（*）__truediv__：除法（/）__floordiv__：整除（//）__mod__：取模（%）__pow__：幂运算（**）
还有很多其他的，这里不过多阐述。
Lecture 22 Composition
链表（LInked List）
链表在C语言中已经学过：
1
2
3
4
5
6
7
8
9
10
11
12
|
struct node{
int id;
node *next;
}Node;
Node *phead = (*Node)malloc(sizeof(Node));
phead->id = -1;
phead->next = NULL;
void add(){
...
}
|
C++的STL（Standard TemplateLibrary，标准模版库）中已经实现好双端链表和单向链表：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
#include <iostream>
#include <list>
int main() {
std::list<int> myList;
myList.push_back(1); // 尾部插入
myList.push_front(0); // 头部插入
// 遍历链表
for (int num : myList) {
std::cout << num << " ";
}
myList.pop_front(); // 删除头部元素
std::cout << "\nSize: " << myList.size(); // 输出: 1
return 0;
}
|
其中std::list为双向链表， std::forward_list为单向链表
。
Java 的标准库中提供了 java.util.LinkedList 类，它实现了双向链表的功能，并实现了 List 和 Deque 接口，如：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
import java.util.LinkedList;
public class LinkedListExample {
public static void main(String[] args) {
// 创建链表
LinkedList<String> list = new LinkedList<>();
// 添加元素
list.add("Apple");
list.add("Banana");
list.addFirst("Cherry");
// 遍历链表
for (String fruit : list) {
System.out.println(fruit);
}
// 移除元素
list.removeFirst();
// 获取链表大小
System.out.println("Size: " + list.size());
}
}
|
而Python中并没有内置的链表结构，意味着我们需要自己实现。在课程中，老师给到一个单端链表的实现：
1
2
3
4
5
6
7
|
class List:
def __init__(self,id,next = empty):
assert next is Link empty or isinstance(next, Link)
self.id = id
self.next = next
s = List(1, List(2, List(3)))
|
Lecture 23 Efficiency
简单介绍了时间复杂度、空间复杂度和记忆化。
如果要了解或者深入研究应当参考《数据结构与算法》这门课。
Lecture 24 Decomposition
模块化设计，现场实现了一个Restaurant例子。
Lecture 25 Data Examples
给到了迭代器、链表的例子，建议跟代码敲一遍。
Lecture 30 Calculator
异常与异常处理
异常在前文Lecture 7已有提过，主要是程序运行时产生的错误，常见的错误有：
SyntaxError：语法错误TypeError：类型错误（如对非数字类型进行数学运算）ValueError：值错误（如 int("abc")）IndexError：索引越界KeyError：字典键不存在FileNotFoundError：文件不存在ZeroDivisionError：除零错误
在 Python 中，异常处理是一种捕获和响应程序运行时错误的机制。通过异常处理，程序可以在遇到错误时不会崩溃，而是执行特定的恢复或清理操作。 Python 异常处理的核心概念和用法有：
try-except 块
使用 try 块包裹可能出错的代码，except 块处理特定类型的异常，使用 except Exception as e 捕获所有异常，并通过变量 e 获取异常信息：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
try:
result = 10 / 0 # 可能引发 ZeroDivisionError
except ZeroDivisionError:
print("Error: 除数不能为零！")
#-------------------------
try:
num = int("abc") # 可能引发 ValueError
result = 10 / num # 可能引发 ZeroDivisionError
except ValueError:
print("Error: 输入不是有效的整数！")
except ZeroDivisionError:
print("Error: 除数不能为零！")
#-------------------------
try:
# 可能引发多种异常的代码
file = open("nonexistent.txt", "r")
except Exception as e:
print(f"发生错误: {e}") # 输出具体错误信息
|
使用 traceback 模块获取异常的堆栈跟踪信息：
1
2
3
4
5
6
|
import traceback
try:
result = 10 / 0
except ZeroDivisionError as e:
traceback.print_exc() # 打印完整的错误堆栈
|
else 块在 try 块没有引发异常时执行；而finally 块无论是否发生异常都会执行，常用于资源清理：
1
2
3
4
5
6
7
8
|
try:
result = 10 / 2
except ZeroDivisionError:
print("Error: 除数不能为零！")
else:
print(f"结果: {result}") # 当没有异常时执行
finally:
print("over")
|
使用 raise 手动触发异常：
1
2
3
4
5
6
7
8
9
|
def divide(a, b):
if b == 0:
raise ZeroDivisionError("除数不能为零！")
return a / b
try:
result = divide(10, 0)
except ZeroDivisionError as e:
print(e) # 输出: 除数不能为零！
|
通过继承 Exception 类可以创建自定义异常：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class InvalidAgeError(Exception):
def __init__(self, message="年龄不能为负数！"):
self.message = message
super().__init__(self.message)
def check_age(age):
if age < 0:
raise InvalidAgeError()
print(f"年龄有效: {age}")
try:
check_age(-5)
except InvalidAgeError as e:
print(e) # 输出: 年龄不能为负数！
|
Part2 Scheme
Lecture 28 Scheme
26、27不存在，课程从28继续开始按顺序编号。
从本章开始介绍一门全新的编程语言：Scheme。Scheme是Lisp的方言，Scheme只重视括号，而不关注缩进和空格。
从本节课开始，我们需要用Python编写一个Scheme解释器，这是一项很有挑战性的工程。
Lecture 29 Scheme Lists
<Scheme>
Lecture 30 Calculator
<Scheme>
Lecture 31 Interpreter
从本节课开始，正式介绍Scheme语言及实现其解释器的各种前置知识，可以认为是《编译原理》的启蒙和初级教学，
Lecture 32 Tail Calls (Optional)
尾递归。
<Scheme>
Lecture 33 Programs as Data
<Scheme>
Lecture 34 Macros
<Scheme>
Porject 4 Scheme
从节开始，进行最后一个项目的编写，可以在Scheme | CS自学社区查看中文版的任务。
项目中将要编辑的文件：
scheme_eval_apply.py：Scheme 表达式递归求值器scheme_forms.py：特殊形式求值scheme_classes.py：描述 Scheme 表达式的类questions.scm：需要实现的 Scheme 过程
问题 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
def define(self, symbol, value):
"""Define Scheme SYMBOL to have VALUE."""
# BEGIN PROBLEM 1
"*** YOUR CODE HERE ***"
self.bindings[symbol] = value
# END PROBLEM 1
def lookup(self, symbol):
"""Return the value bound to SYMBOL. Errors if SYMBOL is not found."""
# BEGIN PROBLEM 1
"*** YOUR CODE HERE ***"
if symbol in self.bindings:
return self.bindings[symbol]
# END PROBLEM 1
raise SchemeError('unknown identifier: {0}'.format(symbol))
|
问题 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
|
def scheme_apply(procedure, args, env):
"""Apply Scheme PROCEDURE to argument values ARGS (a Scheme list) in
Frame ENV, the current environment."""
validate_procedure(procedure)
if not isinstance(env, Frame):
assert False, "Not a Frame: {}".format(env)
if isinstance(procedure, BuiltinProcedure):
# BEGIN PROBLEM 2
"*** YOUR CODE HERE ***"
res = []
print(f"args: {args}, args.first: {args.first}, args.rest: {args.rest}")
while args is not nil:
res.append(args.first)
args = args.rest
if procedure.need_env:
res.append(env)
# END PROBLEM 2
try:
# BEGIN PROBLEM 2
"*** YOUR CODE HERE ***"
return procedure.py_func(*res)
# END PROBLEM 2
except TypeError as err:
raise SchemeError('incorrect number of arguments: {0}'.format(procedure))
elif isinstance(procedure, LambdaProcedure):
# BEGIN PROBLEM 9
"*** YOUR CODE HERE ***"
# END PROBLEM 9
elif isinstance(procedure, MuProcedure):
# BEGIN PROBLEM 11
"*** YOUR CODE HERE ***"
# END PROBLEM 11
else:
assert False, "Unexpected procedure: {}".format(procedure)
|
Python作为弱类型语言实在是令人抓狂，需要注意的是，args是一个Pair类型，可以在程序运行时发现，执行 print(f"args: {args}, args.first: {args.first}, args.rest: {args.rest}")时返回如下结果：
1
|
args: (2 2), args.first: 2, args.rest: (2)
|
这说明args和args.rest是相同类型，而args.first是数字类型。
问题 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
def scheme_eval(expr, env, _=None): # Optional third argument is ignored
"""Evaluate Scheme expression EXPR in Frame ENV.
>>> expr = read_line('(+ 2 2)')
>>> expr
Pair('+', Pair(2, Pair(2, nil)))
>>> scheme_eval(expr, create_global_frame())
4
"""
print(f"scheme_eval: {expr}, env: {env}")
# Evaluate atoms
if scheme_symbolp(expr):
print(f" scheme_symbolp(expr), scheme_eval: {expr}, env: {env}, return value: {env.lookup(expr)}")
return env.lookup(expr)
elif self_evaluating(expr):
print(f" self_evaluating(expr), scheme_eval: {expr}, return value: {expr}")
return expr
# All non-atomic expressions are lists (combinations)
if not scheme_listp(expr):
print(f" not scheme_listp(expr), scheme_eval: {expr}, raise SchemeError")
raise SchemeError('malformed list: {0}'.format(repl_str(expr)))
first, rest = expr.first, expr.rest
if scheme_symbolp(first) and first in scheme_forms.SPECIAL_FORMS:
print(f" scheme_symbolp(first) and first in scheme_forms.SPECIAL_FORMS, first: {first}, rest: {rest}, env: {env}, return value: {scheme_forms.SPECIAL_FORMS[first](rest, env)}")
return scheme_forms.SPECIAL_FORMS[first](rest, env)
else:
# BEGIN PROBLEM 3
"*** YOUR CODE HERE ***"
print(f" expr: {expr}, first: {first}, rest: {rest}, env: {env}, processer: {scheme_eval(first, env)}")
processer = scheme_eval(first, env)
args = rest.map(lambda x: scheme_eval(x, env))
return scheme_apply(processer, args, env)
# END PROBLEM 3
|
为了方便观察，我在代码中添加了print方便显示递归过程，有如下测试结果：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
scm> (+ 2 2)
scheme_eval: (+ 2 2), env: <Global Frame>
scheme_eval: +, env: <Global Frame>
scheme_symbolp(expr), scheme_eval: +, env: <Global Frame>, return value: #[+]
expr: (+ 2 2), first: +, rest: (2 2), env: <Global Frame>, processer: #[+]
scheme_eval: +, env: <Global Frame>
scheme_symbolp(expr), scheme_eval: +, env: <Global Frame>, return value: #[+]
scheme_eval: 2, env: <Global Frame>
self_evaluating(expr), scheme_eval: 2, return value: 2
scheme_eval: 2, env: <Global Frame>
self_evaluating(expr), scheme_eval: 2, return value: 2
args: (2 2), args.first: 2, args.rest: (2)
4
|
后记
proj写到这里暂时写不动了，不太适应这种弱类型语言，时间全都花费在找参数类型上，这违背了编程的初衷，等后期顿悟了再回来填空吧。
Part3 SQL
Lecture 35-39 SQL
SQL（Structured Query Language）是一种专门用于管理和操作关系型数据库的编程语言。
主要功能：
- 数据定义（DDL）：用于创建、修改和删除数据库对象，像表、视图、索引等。
- 数据操作（DML）：负责对数据进行插入、查询、更新和删除操作。
- 数据控制（DCL）：用于管理用户权限，例如授予或撤销权限。
- 事务控制（TCL）：对事务进行管理，包括提交或回滚事务。
基本语法规则：
- 不区分大小写：一般习惯将关键字大写，而表名和列名小写。
- 语句以分号结尾：在大多数数据库系统中，SQL 语句以分号作为结束标志。
- 注释：单行注释使用
--，多行注释使用/* ... */。
Select语句
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
SELECT [expression] AS [name], ...;
-- 简单查询
SELECT * FROM students;
-- 带条件查询
SELECT name, age FROM students WHERE age > 20;
-- 排序
SELECT * FROM students ORDER BY age DESC;
-- 去重
SELECT DISTINCT gender FROM students;
-- 分页
SELECT * FROM students LIMIT 10 OFFSET 20; -- MySQL语法
|
还有很多SQL语句，不在这里过多展示，可以进行查询获取。