基本介绍👋

CS61A是加州大学伯克利分校（UC Berkeley）计算机科学专业的入门课程，全名为Structure and Interpretation of Computer Programs。

这是入门的Python课程，因此这篇博客会默认读者没有很多的编程背景，讲的东西会比较基础，有编程经验的读者可以快速浏览。

首先贴上课程网址。
CS61A课程主页

感觉课程主页还是非常精美的，相比MIT6.828的课程主页来说。

这篇博客也根据日程表的日程来编写。

Week 1

这是第一周🪶，有两次课。可以看到Recording和Slides。前者需要Berkeley账号，咱也没有账号略过。

Wed Welcome

这是这个学期的第一节课，和国内一样讲一下课程内容，然后评分标签。首先可以阅读一下Slides，确实如此。

Disc00

Disc（Discussion）模块是课堂讨论模块，记录了课堂上讨论的一些问题，Disc00没有什么内容就跳过了。

Lab 00: Getting Started

准备工作

Lab就是实验模块了。第一个实验主要内容是配置熟悉一下编程环境。

CS61A使用的是Python编程，首先需要安装一个能够运行Python程序的软件，也就是Python的解释器(Interpreter)。

其他底层的操作系统的任务暂且不管，先就考虑这样一个简单的过程。

Lab中有引导的安装教程，就不复述了。

编程其实就是两件事情：

1. 写出代码
2. 运行代码（或者编译项目）

暂且遮蔽许多细节，就这样简单理解。

注意：环境变量
不管是在Linux上，还是Windows上，如果你安装好软件比如Python，如果你没有配置环境变量的话，你直接输入python命令，操作系统完全不知道去哪里找这个程序。

比如你下载好了Python，会有类似这样的一个文件夹。

Windows操作系统同业也提供了命令执行行终端。
按Win键+R唤起运行，输入cmd打开命令终端，如果觉得界面太过复古，可以去Microsoft Store下载一个Windows Terminal。

如果没有配置环境变量，输入python，没办法找到你的python解释器，也就没办法执行。

配置环境变量，就是把这个解释器所在的文件夹，放到当你敲入命令后操作系统遍历访问的若干文件夹，寻找相关的可执行程序。具体配置方法可以在网络上搜索一下，也可以问问GPT，或者私信我。

注意：编辑器
下面我使用的是VScode，编辑器本身并不能执行代码，编辑器的功能其实相当于一个高级的笔记本。你也可以使用Vim，参见我的博客，Vim的使用。

VScode安装一个Python插件基本就能用了，一些配置细节网络上文章很多不再赘述。它提供语法检查功能，帮你写出更加正确的代码。

当你打开VScode的时候，一般右下角可以选择解释器。

可以看到，出来我本来的python解释器，还有很多在conda内的环境里的解释器，conda也是一个非常方便的工具，我个人的理解是相当于一个python容器管理工具。

动手！

在配置好环境之后，根据课程提示可以下载lab00.zip。使用VScode打开文件夹，可以看到如下文件。

test文件夹里放的本使用的测试脚本，lab00.ok是交给ok的一个测试程序。

Q1
根据手册指引，需要打开终端(可以按Ctrl+反引号打开vscode下方终端，或者直接在目标目录右键打开cmd终端)执行：

python3 ok -q python-basics -u

注意：如果你的环境变量配置的和我一样的话，把python3改成python，其实课程文件里有地方讲过。我下面都改成python了。

在Q1其实有连接说明ok的用法，OK的用法。

键入

python ok -h

可以得到ok程序的所有选项说明，ok是Berkeley编写的测评程序，还是功能还是比较多的。

但是之前执行的时候，会让你登录Berkeley的账号，但是咱没有，可以在命令后面添加--local本地测评。

因此执行

python ok  -q python-basics -u --local

Q1的内容是让你分析表达式的值，核心是关注有没有进行赋值。
比较简单：

What would Python display? If you get stuck, try it out in the Python
interpreter!>>> x = 20
>>> x + 2
? 22
-- OK! -->>> x
? 20
-- OK! -->>> y = 5
>>> y = y + 3
>>> y * 2
? 16
-- OK! -->>> y + x
? 36
-- Not quite. Try again! --? 28
-- OK! --

如果输错了可以一直输入。

Q2

Q2是完成一个python函数的定义，返回一个值为2024表达式。具体关于Python如何定义和声明函数lab00还没有开始强调，我们只需把下划线(其实下划线是一个合法的变量的名字，只不过没有被声明)，换成2024即可，当然也可以是2023+1这些类似的式子。

def twenty_twenty_four():"""Come up with the most creative expression that evaluates to 2024using only numbers and the +, *, and - operators.>>> twenty_twenty_four()2024"""return 2024

完成代码之后，根据指示可以运行测试，但是如果你要本地测试，需要输入

python ok --local

得到结果如下：

PS D:\Desktop\cs61a\labs\lab00> python ok --local
=====================================================================
Assignment: Lab 0
OK, version v1.18.1
=====================================================================~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Running tests---------------------------------------------------------------------
Test summary2 test cases passed! No cases failed.Cannot backup when running ok with --local.

本节后面还有一些补充说明，比如doctest的使用，python的一些选项。

拓展一下

如果你是喜欢"钻牛角尖"的新手(like me)，可能会对这个ok程序感觉好奇，像一个黑盒子一样。

对了，在你运行了python ok --local之后，会出现一些.ok开头的文件，这些是应该是ok程序产生的缓存文件，还有__pycache__这个是python的缓存文件，详细可以问问搜索引擎或大模型。

读者可能有疑问，为什么python能直接运行ok，python不是只能运行python代码文件吗？

实际上，ok是一个zip格式的python源码压缩包。读者可以尝试把ok改成ok.zip，然后解压。python解释器支持解释压缩后的python项目，但是，zip压缩包当中必须要有__main__.py，文件，让解释器知道从哪里开始执行程序。

Fri Functions

开篇

本次课的标题是函数。

个人短评：函数是所有编程语言中都十分重要的概念，函数的抽象把一系列操作整合到一起。

笔者也可以说是刚学Py，虽然之前C/C++有比较多编程经验，python偶尔使用一下。这次课的内容也是有不少的收获，推荐读者不要仅仅去完成lab。

材料阅读

建议先阅读Ch1.1，Ch1.2和Ch1.3，里面对Python中函数，表达式，作用域的概念进行了总结，建议阅读一下，也就不再班门弄斧二次总结了。

我觉得有必要看一下slides里面的这个问题

这个问题就是说，有一个函数f(x)，它的功能是令x=x-1，函数g(x)，它的功能是令x=x*2，函数h(x,y)是将两个输根据字符拼接起来。嵌套调用上述的函数得到2024最少要多少次。这个程序写起来是不太容易的。

这里的代码运用了函数的类和类的一些特殊的函数，比较超前了。用到了fstring格式化输出。具体的可以问GPT。

Generator非常有趣，如果没有generate在递归的过程中要反复传递list，非常消耗空间和时间，我的理解是，generator不一下子把全部的结果求出，而且记录一个递归的关系，每次使用迭代器的时候就再递归一下算出一个结果。这样对于那些无限递归的问题，也能通过generator一个个获取值。yield和return不太一样，返回的是迭代器对象。目前对python理解不深。

HW 01: Functions, Control

Q1: A Plus Abs B

Q1挺坑的，你如果没有理解绑定变量的含义很可能想歪，它的测试程序会检查你是否用了其他的错误的做法。正解是把add和sub函数绑定(bind)到f变量上，可以注意到文件的开头特意导入了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 = subelse:f = addreturn 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)']"""

在手册里讲过，这些"""后面的>>>就是所谓的doctest，解释器会依次执行这些指令比较输出是否正确。这里用高端的正则表达式检查了你在上面那个函数里用的函数表达式的构造。

Q2: Two of Three

这个题让你在一行之内求出三个数最小两个数的平方和。在python中min和max可以输入许多个参数。最小值直接三个数取min，中间值就用三个减去最大值和最小值，平方使用**符号。

def two_of_three(i, j, k):"""Return m*m + n*n, where m and n are the two smallest members of thepositive 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 + (i + j + k - min(i, j, k) - max(i, j, k)) ** 2

Q3: Largest Factor

求最大的因子，我们就朴素遍历每个小于n的数，使用取模运算检查是否整除即可。

def largest_factor(n):"""Return the largest factor of n that is smaller than n.>>> largest_factor(15) # factors are 1, 3, 55>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 4040>>> largest_factor(13) # factor is 1 since 13 is prime1""""*** YOUR CODE HERE ***"ans = 1cur = 1while cur < n:if n % cur == 0:ans = curcur = cur + 1return ans

Q4: Hailstone

中文名应该是冰雹，根据它的意思写就行了，注意边界和整数除法用//。

def hailstone(n):"""Print the hailstone sequence starting at n and return itslength.>>> a = hailstone(10)105168421>>> a7>>> b = hailstone(1)1>>> b1""""*** YOUR CODE HERE ***"steps = 1while n > 1:steps = steps + 1print(n)if n % 2 == 0:n //= 2else:n = 3 * n + 1print(n)return steps

Week 2

Mon

Lab01: HW 01: Functions, Control

Q1: Return and Print

What would Python display? If you get stuck, try it out in the Python
interpreter!>>> def welcome():
...     print('Go')
...     return 'hello'
>>> def cal():
...     print('Bears')
...     return 'world'
>>> welcome()
(line 1)? Go
(line 2)? hello
-- OK! --

返回字符串类型，使用函数名的时候还有引号标识。print的时候则没有。

>>> print(welcome(), cal())
(line 1)? Go
(line 2)? Bears
(line 3)? hello world
-- OK! --

注意先调用子函数再调用print。

Q2: Debugging Quiz

这是一个关于debug的知识小测，没什么好讲的。

PS D:\Desktop\cs61a\labs\lab01> python ok -q debugging-quiz -u --local
=====================================================================
Assignment: Lab 1
OK, version v1.18.1
=====================================================================~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Unlocking testsAt each "? ", type what you would expect the output to be.
Type exit() to quit---------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 1
(cases remaining: 7)Q: In the following traceback, what is the most recent function call?
Traceback (most recent call last):File "temp.py", line 10, in <module>f("hi")File "temp.py", line 2, in freturn g(x + x, x)File "temp.py", line 5, in greturn h(x + y * 5)File "temp.py", line 8, in hreturn x + 0TypeError: must be str, not int
Choose the number of the correct choice:
0) f("hi")
1) g(x + x, x)
2) h(x + y * 5)
? 2
-- OK! -----------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 2
(cases remaining: 6)Q: In the following traceback, what is the cause of this error?
Traceback (most recent call last):File "temp.py", line 10, in <module>f("hi")File "temp.py", line 2, in freturn g(x + x, x)File "temp.py", line 5, in greturn h(x + y * 5)File "temp.py", line 8, in hreturn x + 0TypeError: must be str, not int
Choose the number of the correct choice:
0) there was a missing return statement
1) the code attempted to add a string to an integer
2) the code looped infinitely
? 1
-- OK! -----------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 3
(cases remaining: 5)Q: How do you write a doctest asserting that square(2) == 4?
Choose the number of the correct choice:
0) def square(x):'''>>> square(2)4'''return x * x
1) def square(x):'''square(2)4'''return x * x
2) def square(x):'''input: 2output: 4'''return x * x
3) def square(x):'''doctest: (2, 4)'''return x * x
? 0
-- OK! -----------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 4
(cases remaining: 4)Q: When should you use print statements?
Choose the number of the correct choice:
0) To investigate the values of variables at certain points in your code
1) For permanant debugging so you can have long term confidence in your code
2) To ensure that certain conditions are true at certain points in your code
? 0
-- OK! -----------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 5
(cases remaining: 3)Q: How do you prevent the ok autograder from interpreting print statements as output?
Choose the number of the correct choice:
0) You don't need to do anything, ok only looks at returned values, not printed values
1) Print with 'DEBUG:' at the front of the outputted line
2) Print with # at the front of the outputted line
? 1
-- OK! -----------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 6
(cases remaining: 2)Q: What is the best way to open an interactive terminal to investigate a failing test for question sum_digits in assignment lab01?
Choose the number of the correct choice:
0) python3 ok -q sum_digits --trace
1) python3 ok -q sum_digits -i
2) python3 ok -q sum_digits
3) python3 -i lab01.py
? 1
-- OK! -----------------------------------------------------------------------
debugging-quiz > Suite 1 > Case 7
(cases remaining: 1)Q: Which of the following is NOT true?
Choose the number of the correct choice:
0) It is generally good practice to release code with assertion statements left in
1) Testing is very important to ensure robust code
2) Debugging is not a substitute for testing
3) Code that returns a wrong answer instead of crashing is generally better as it at least works fine
4) It is generally bad practice to release code with debugging print statements left in
? 3
-- OK! -----------------------------------------------------------------------
OK! All cases for debugging-quiz unlocked.

Q3: Pick a Digit

选取倒数第几个数码，整除10的幂取模即可。

def digit(n, k):"""Return the digit that is k from the right of n for positive integers n and k.>>> digit(3579, 2)5>>> digit(3579, 0)9>>> digit(3579, 10)0"""return n // 10 ** k % 10

Q4: Middle Number

三个数取中间的数，去掉一个最大值去掉一个最小值即可。

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 a + b + c - min(a, b, c) - max(a, b, c)

Q5: Syllabus Quiz

教学大纲测试，略。

Q6: Falling Factorial

求排列数，注意0的时候是1

def falling(n, k):"""Compute the falling factorial of n to depth k.>>> falling(6, 3)  # 6 * 5 * 4120>>> falling(4, 3)  # 4 * 3 * 224>>> falling(4, 1)  # 44>>> falling(4, 0)1""""*** YOUR CODE HERE ***"cur = nans = 1for i in range(k):ans = ans * curcur = cur - 1return ans

Q7: Divisible By k

题目意思是找到所有小于n的k的倍数，打印。并且返回总数量。

def divisible_by_k(n, k):""">>> a = divisible_by_k(10, 2)  # 2, 4, 6, 8, and 10 are divisible by 2246810>>> a5>>> b = divisible_by_k(3, 1)  # 1, 2, and 3 are divisible by 1123>>> b3>>> c = divisible_by_k(6, 7)  # There are no integers up to 6 divisible by 7>>> c0""""*** YOUR CODE HERE ***"cur = kans = 0while cur <= n:ans = ans + 1print(cur)cur = cur + kreturn ans

Q8: Sum Digits

把全部的数码相加在一起，方法很多。

def sum_digits(y):"""Sum all the digits of y.>>> sum_digits(10) # 1 + 0 = 11>>> sum_digits(4224) # 4 + 2 + 2 + 4 = 1212>>> sum_digits(1234567890)45>>> a = sum_digits(123) # make sure that you are using return rather than print>>> a6""""*** YOUR CODE HERE ***"ans = 0while y > 0:ans = ans + y % 10y = y // 10return ans

Q9: WWPD: What If?

问答小测，关于流程控制语句的。

---------------------------------------------------------------------
What If? > Suite 1 > Case 1
(cases remaining: 2)What would Python display? If you get stuck, try it out in the Python
interpreter!>>> def ab(c, d):
...     if c > 5:
...         print(c)
...     elif c > 7:
...         print(d)
...     print('foo')
>>> ab(10, 20)
(line 1)? 10
(line 2)? foo
-- OK! -----------------------------------------------------------------------
What If? > Suite 1 > Case 2
(cases remaining: 1)What would Python display? If you get stuck, try it out in the Python
interpreter!>>> def bake(cake, make):
...    if cake == 0:
...        cake = cake + 1
...        print(cake)
...    if cake == 1:
...        print(make)
...    else:
...        return cake
...    return make
>>> bake(0, 29)
(line 1)? 1
(line 2)? 29
(line 3)? 29
-- OK! -->>> bake(1, "mashed potatoes")
(line 1)? mashed potatoes
(line 2)? 'mashed potatoes' 
-- OK! -----------------------------------------------------------------------
OK! All cases for What If? unlocked.

Q10: Double Eights

题目意思是否能找到相邻的两个8，可以使用find方法，如果找不到子串返回-1，类似C++的find方法。

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 ***"return str(n).find("88") != -1

Wed

待施工。。。(2024/10/29)

关于

如果读者想和我交个朋友可以加我的QQ，共同学习。笔者是学生，课业还是比较繁重的，可能回复不及时。笔者也正在四处寻找一些可以兼职锻炼知识并且补贴一些生活的工作，如果读者需要一些详细的辅导，或者帮助完成一些简易的lab也可以找我，笔者还是学生，自以为才学有限，也没有高价的理由📖