相关文章推荐
才高八斗的钢笔  ·  中国黑鹰直升机只剩20架4架失事多因气候恶劣 ...·  1 年前    · 
失眠的烤地瓜  ·  金瓶掣签·  1 年前    · 
越狱的扁豆  ·  这些好听的纯音乐你一定会喜欢|久石让|恩雅| ...·  1 年前    · 
健壮的烤地瓜  ·  2021,感受中国军校的时代脉动- 中国军网·  1 年前    · 
深沉的香槟  ·  国际期刊- 上海交通大学材料科学与工程学院·  1 年前    · 
小百科  ›  日拱一卒,一起来上伯克利的实验课,让你的Python溜起来开发者社区
python函数 python3 递归函数 guess
慷慨大方的脸盆
1 年前
作者头像
TechFlow-承志
0 篇文章

日拱一卒,一起来上伯克利的实验课,让你的Python溜起来

前往专栏
腾讯云
开发者社区
文档 意见反馈 控制台
首页
学习
活动
专区
工具
TVP
文章/答案/技术大牛
发布
首页
学习
活动
专区
工具
TVP
返回腾讯云官网
社区首页 > 专栏 > TechFlow > 正文

日拱一卒,一起来上伯克利的实验课,让你的Python溜起来

发布 于 2022-09-21 12:05:00
209 0
举报

作者 | 梁唐

出品 | 公众号: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
 
推荐文章
才高八斗的钢笔  ·  中国黑鹰直升机只剩20架4架失事多因气候恶劣|中国黑鹰直升机_新浪 ...
1 年前
失眠的烤地瓜  ·  金瓶掣签
1 年前
越狱的扁豆  ·  这些好听的纯音乐你一定会喜欢|久石让|恩雅|歌曲|演奏|纯音乐_手机 ...
1 年前
健壮的烤地瓜  ·  2021,感受中国军校的时代脉动- 中国军网
1 年前
深沉的香槟  ·  国际期刊- 上海交通大学材料科学与工程学院
1 年前
今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
删除内容请联系邮箱 2879853325@qq.com
小百科 - 百科知识指南
© 2024 ~ 沪ICP备11025650号