日拱一卒,一起来上伯克利的实验课,让你的Python溜起来
作者 | 梁唐
出品 | 公众号:Coder梁(ID:Coder_LT)
大家好,日拱一卒,我是梁唐。
最近经同学提醒,补做了伯克利CS61A的实验,发现非常有意思,分享给大家。
虽然我们不是伯克利的学生,没办法提交实验,得到老师的反馈。但是大部分问题我们还是可以进行本地测试的,能够实时地看到我们的结果是否正确,因此是一个很好的锻炼机会。
本系列会持续更新,想要一起学习的同学不妨在评论区打个卡。
在之前的文章当中,可能没有特别说清楚这点,也许有些同学还不知道,所以这里再介绍一下。
首先,我们可以访问实验的官网,比如这个实验的链接是:
https://inst.eecs.berkeley.edu//~cs61a/sp18/lab/lab01/#using-python
复制链接进入之后,可以看到:

右侧是整个文档的目录,我们可以点击下载
lab01.zip
,里面有实验所需要的所有内容。包括单元测试以及框架代码等等。我们下载解压之后,使用命令行进入文件夹。之后就可以根据题目当中的命令提示进行测试了。
每道题目当中都会有测试命令的说明,比如本次实验的第一题中,需要我们使用命令来回答问题。

那么我们就遵循这个提示,在命令行输入对应的命令,就可以回答问题了。 这里最好使用python3.6的版本,版本太高可能会报错。

有些问题是直接进行测试,我们可以直接看到测试结果:

测试通过之后,会让我们输入学校的邮箱进行提交。我们当然是没办法提交的,这时候直接Ctrl + D退出就好了。或者可以在测试命令之后加上后缀
--local
,表示本地测试,不进行上传。
这次的实验课是一个Python的基础练习,带我们熟悉和掌握Python的基础语法。
What Would Python Display (Part 1)?
第一部分,根据代码推测Python的输出结果。
Q1: WWPD: Veritasiness
交互命令:
python3 ok -q short_circuiting -u
在命令行当中进行答题,一共有14题:
>>> True and 13
______
>>> False or 0
______
>>> not 10
______
>>> not None
______
>>> True and 1 / 0 and False
______
>>> True or 1 / 0 or False
______
>>> True and 0
______
>>> False or 1
______
>>> 1 and 3 and 6 and 10 and 15
______
>>> 0 or False or 2 or 1 / 0
______
>>> not 0
______
>>> (1 + 1) and 1
______
>>> 1/0 or True
______
>>> (True or False) and False
______
这些题不难我就不专门放答案了,如果大家吃不准结果,直接复制出来在Python里运行一下即可。
核心注意点只有两个,第一个是在
and
计算时,如果结果都为
True
,会返回最后一个为
True
的结果,比如:
1 and 3 and 6 and 10 and 15
最后的结果是15.
第二个点是,进行
or
计算时,遇到为
True
的值之后,后面的运算会停止。比如
0 or False or 2 or 1 / 0
,虽然最后
1/0
是非法操作,但由于之前出现了
2
是
True
,所以阻断了
1/0
的执行。
Q2: WWPD: Loops
本地测试命令:
python3 ok -q loops -u
交互答题,一共有7题:
>>> n = 3
>>> while n >= 0:
... n -= 1
... print(n)
______
>>> n = 4
>>> while n > 0:
... n += 1
... print(n)
______
>>> def go(n):
... if n % 2 != 0:
... print(n / 2)
... return
... while n > 0:
... print(n)
... n = n // 2
>>> go(4)
______
>>> go(5)
______
>>> zero = 2
>>> while zero != 0:
... zero = zero // 2
... print(zero)
______
>>> positive = 28
>>> while positive:
... print("positive?")
... positive -= 3
______
>>> positive = -9
>>> negative = -12
>>> while negative:
... if positive:
... print(negative)
... positive += 3
... negative += 3
______
同样如果拿不准,在Python里运行一下就可以了。不过还是建议大家人肉答题,这样当出乎意料的结果出现时,比较锻炼人。
Coding Practice
代码练习
Q3: Repeated
实现
repeated
函数,它接收一个参数
f
表示一个函数,一个正整数
n
和一个参数
x
。它返回如下表达式的结果:f(f(...f(x)...)),即嵌套了n层f之后的结果。
参考样例:
>>> def square(x):
... return x * x
>>> repeated(square, 2, 3) # square(square(3)), or 3 ** 4
>>> repeated(square, 1, 4) # square(4)
>>> repeated(square, 6, 2) # big number
18446744073709551616
>>> def opposite(b):
... return not b
>>> repeated(opposite, 4, True)
>>> repeated(opposite, 5, True)
False
>>> repeated(opposite, 631, 1)
False
>>> repeated(opposite, 3, 0)
完成之后,进行测试:
python3 ok -q repeated
答案
如果理解递归,使用递归非常简单。
def repeated(f, n, x):
"""Returns the result of composing f n times on x.
"*** YOUR CODE HERE ***"
if n == 1:
return f(x)
return f(repeated(f, n-1, x))
不用递归其实也不麻烦,我们循环n-1次也一样可以得到答案:
def repeated(f, n, x):
"""Returns the result of composing f n times on x.
"*** YOUR CODE HERE ***"
ret = x
for _ in range(n):
ret = f(ret)
return ret
Q4: Sum Digits
实现一个函数,它接收一个非负整数,返回这个整数所有数字的和(使用整除和取模运算)
参考样例:
>>> sum_digits(10) # 1 + 0 = 1
>>> sum_digits(4224) # 4 + 2 + 2 + 4 = 12
>>> sum_digits(1234567890)
完成之后,进行测试:
python3 ok -q sum_digits
答案
这题和上一题一样的套路,使用递归和不使用递归都很简单。
递归版本:
def sum_digits(n):
"""Sum all the digits of n.
"*** YOUR CODE HERE ***"
if n < 10:
return n
return sum_digits(n // 10) + n % 10
非递归版本:
def sum_digits(n):
"""Sum all the digits of n.
"*** YOUR CODE HERE ***"
ret = 0
while n > 0:
ret += n % 10
n //= 10
return ret
Q5: Double Eights
实现一个函数,它接收一个数,返回它的数字当中是否包含两个相邻的8
参考样例:
>>> double_eights(8)
False
>>> double_eights(88)
>>> double_eights(2882)
>>> double_eights(880088)
>>> double_eights(12345)
False
>>> double_eights(80808080)
False
测试命令:
python3 ok -q double_eights
答案
这道题可能迭代的方法会稍微直观一点,我们只需要将这个数字转化成字符串,然后返回是否拥有'88'的子串即可。
代码实现只有一行:
def double_eights(n):
"""Return true if n has two eights in a row.
"*** YOUR CODE HERE ***"
return '88' in str(n)
如果不使用转化成字符串这种取巧的办法,我们还可以每次取出n的最后两位,如果这两位等于88,则返回
True
,否则将n除以10,相当于去掉最后一位,继续判断最后两位是否是88,直到n小于10为止。
def double_eights(n):
"""Return true if n has two eights in a row.
"*** YOUR CODE HERE ***"
while n > 10:
if n % 100 == 88:
return True
n //= 10
return False
基于上面迭代的方法,我们也可以写出递归的解法,本质上思路是一样的,只是代码实现略有不同。
def double_eights(n):
"""Return true if n has two eights in a row.
"*** YOUR CODE HERE ***"
if n < 10:
return False
pref, suff = (n % 100) // 10, n % 10
return (pref == 8 and suff == 8) or double_eights(n // 10)
附加题
What Would Python Display (Part 2)?
根据代码推测Python的输出结果第二弹。
Q6: WWPD: Truthiness
真假值判断,交互命令:
python3 ok -q truthiness -u
在命令行中答题,一个有6题:
>>> 0 or True
______
>>> not '' or not 0 and False
______
>>> 13 and False
______
>>> False or 1
______
>>> '' or 1 and 1/0
______
>>> not 0 and 12 or 0
______
套路和之前差不多,稍微多加了几种情况。
Q7: WWPD: What If?
命令行中答题,if语句,交互命令:
python3 ok -q what_if -u
下列函数的代码在
lab01.py
中,当你被难住的时候,可以使用命令
python3 -i lab01.py
进行实验。
>>> def xk(c, d):
... if c == 4:
... return 6
... elif d >= 4:
... return 6 + 7 + c
... else:
... return 25
>>> xk(10, 10)
______
>>> xk(10, 6)
______
>>> xk(4, 6)
______
>>> xk(0, 0)
______
>>> def how_big(x):
... if x > 10:
... print('huge')
... elif x > 5:
... return 'big'
... elif x > 0:
... print('small')
... else:
... print("nothin'")
>>> how_big(7)
______
>>> how_big(12)
______
>>> how_big(1)
______
>>> how_big(-1)
______
>>> def so_big(x):
... if x > 10:
... print('huge')
... if x > 5:
... return 'big'
... if x > 0:
... print('small')
... print("nothin'")
>>> so_big(7)
______
>>> so_big(12)
______
>>> so_big(1)
______
>>> def ab(c, d):
... if c > 5:
... print(c)
... elif c > 7:
... print(d)
... print('foo')
>>> ab(10, 20)
______
>>> 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)
______
>>> bake(1, "mashed potatoes")
______
题目不难,稍微有一些阴险,有时候需要转个弯。
More Coding Practice
更多编程练习
Q8: Fix the Bug
下列代码片段有bug,找出其中的bug并修复
def both_positive(x, y):
"""Returns True if both x and y are positive.
>>> both_positive(-1, 1)
False
>>> both_positive(1, 1)
return x and y > 0 # You can replace this line!
完成之后进行测试:
python3 ok -q both_positive
答案
症结在于Python当中只有0是
False
,所以应该改成:
return x > 0 and y > 0
Q9: Falling Factorial
让我们来实现一个函数
failing
,它接收两个参数
n
和
k
,返回从n开始k个递减数的乘积
参考样例:
>>> falling(6, 3) # 6 * 5 * 4
>>> falling(4, 0)
>>> falling(4, 3) # 4 * 3 * 2
>>> falling(4, 1) # 4
测试命令:
python3 ok -q falling
答案
几乎没有难度,非递归版本:
def falling(n, k):
"""Compute the falling factorial of n to depth k.
"*** YOUR CODE HERE ***"
ret = 1
for i in range(n, n-k, -1):
ret *= i
return ret
递归版本:
def falling(n, k):
"""Compute the falling factorial of n to depth k.
"*** YOUR CODE HERE ***"
if k == 0:
return 1
return n * falling(n-1, k-1)
I Want to Play a Game
让我们来玩一个猜数游戏,选一个数,让Python来猜测它,直到猜中。
猜数游戏的完整代码在
label01_extra.py
中,在你的命令行中输入
python3-ilab01_extra.py
来和Python程序进行交互。
guess_random
函数会让你先选一个数,然后循环你若干次它的猜测是否正确。如果它猜对了,输入
y
,否则输入
n
。Python并不擅长猜数,所以可能会猜很久,你可以通过
Ctrl-C
来终止程序。

随机猜测可行,但你需要开发更好的策略。
Q10: Guess Linear
guess_random
策略的一个弱点就是它可能会重复猜测某些错误的数字,所以我们可以使用线性猜测让它更加合理。
注意:
is_correct
函数会循环用户它是否猜对了,如果猜对了会返回
True
,否则会返回
False
。当你实现
guess_linear
时,可以随意参考
guess_random
代码
框架代码:
def guess_linear():
"""Guess in increasing order and return the number of guesses."""
prompt_for_number(LOWER, UPPER)
num_guesses = 1
guess = LOWER
"*** YOUR CODE HERE ***"
return num_guesses
答案
很简单,一直猜测,直到猜对为止
def guess_linear():
"""Guess in increasing order and return the number of guesses."""
prompt_for_number(LOWER, UPPER)
num_guesses = 1
guess = LOWER
"*** YOUR CODE HERE ***"
while guess <= UPPER:
correct = is_correct(guess)
if correct:
break
guess += 1
num_guesses += 1
return num_guesses
Q11: Guess Binary
挑战性问题:
guess_linear
在我们的数字很大的时候,一样会陷入很长的时间。所以我们还可以进一步优化,采取
binary search
即二分的思路来猜测。
整体的思路是从范围的中间开始猜测,如果猜错了,通过
is_too_high
函数询问猜测的结果是太大了还是太小了,你可以每次缩小一半的猜测范围。
is_too_high
的用法如下:

框架代码:
def guess_binary():
"""Return the number of attempted guesses. Implement a faster search
algorithm that asks the user whether a guess is less than or greater than
the correct number.
Hint: If you know the guess is greater than the correct number, then your
algorithm doesn't need to try numbers that are greater than guess.
prompt_for_number(LOWER, UPPER)
num_guesses = 1
lower, upper = LOWER, UPPER