日拱一卒，一起来上伯克利的实验课，让你的Python溜起来
日拱一卒，一起来上伯克利的实验课，让你的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
81
>>> repeated(square, 1, 4) # square(4)
16
>>> repeated(square, 6, 2) # big number
18446744073709551616
>>> def opposite(b):
... return not b
...
>>> repeated(opposite, 4, True)
True
>>> repeated(opposite, 5, True)
False
>>> repeated(opposite, 631, 1)
False
>>> repeated(opposite, 3, 0)
True
"""
完成之后，进行测试：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
1
>>> sum_digits(4224) # 4 + 2 + 2 + 4 = 12
12
>>> sum_digits(1234567890)
45
完成之后，进行测试：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)
True
>>> double_eights(2882)
True
>>> double_eights(880088)
True
>>> 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)
True
"""
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
120
>>> falling(4, 0)
1
>>> falling(4, 3) # 4 * 3 * 2
24
>>> falling(4, 1) # 4
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
guess = (lower + upper) // 2
"*** YOUR CODE HERE ***"
return num_guesses
如果你选择的数字在1到10之间，那么不超过4次就找出答案了。
最好的测试方法是交互式地运行，思考一些边界条件——可能会导致你的算法出错的情况。你可能需要经常重启、终止你的程序来进行反复测试。
目前为止，我们的范围只有1到10，如果我们把它延伸到1到100会怎么样，你觉得在1到100的范围内，每一个算法会需要猜测多少次能猜到答案？
A Second Look
让我们来试着可视化我们刚刚开发的两个算法，我们提供了现成的代码来运行算法1000次，并且绘制程序猜测的次数。每次猜测的数字都是随机从1到100中选的。
python3 guessing_game_graph.py guess_linear
python3 guessing_game_graph.py guess_binary
每一个柱表示了算法找到正确结果的猜测次数，高度表示了对应的频次。仔细观察每个坐标轴，对比一下这两张图。你会发现guess_linear有时候用了100次才猜到答案，而guess_binary最多用了多少次？
这里提供一下我绘制出的图的情况，首先是guess_linear：
然后是guess_binary:
答案是二分法最多需要8次，而线性猜测最多需要100次，这是一个非常巨大的差距，侧面体现除了算法的重要。一个好的算法带来的优化和价值在一些场景中是非常非常巨大的。
喜欢本文的话不要忘记三连~
腾讯云开发者
