文件结构

exam：pdf格式的试题
hw-desciption：hw的描述文档，也就是hw的题目
hw01-10：家庭作业
lab00-12：实验
proj：项目代码
project -> tests: 测试案例在这里，也许可以找到测试答案也说不定(我做过的仓库代码里面才有哦！)

完结撒花🎉🎉🎉,原谅我的拖延,至此完结！

碎碎念: 原计划2-3周结束，没想到拖了这么久，有时候拖延真的很可怕，就像是滚雪球那样，越拖延就越拖延

这个课程并不难，希望你能克服对未知的恐惧，在课程中你的目的是基本了解编程的一些基本概念与抽象

2024/12/22 update README.md

文件结构

前言

这里是我学习CS61A 2024的一些记录和心得

一、CS61A是什么？

CS61A是加州大学伯克利分校（UC Berkeley）的计算机科学导论课程。这门课程旨在教授计算机科学的基本概念和编程技能，主要使用编程语言Python。它是许多学生的第一门计算机科学课程，涵盖了从程序设计基础到数据结构和算法的内容。

CS61A通常被认为是一门非常有挑战性但也非常有价值的课程，为学生提供了扎实的编程基础和计算机科学思维方式。

主要是用Python来掌握函数式编程、面向对象以及SQL等等

二、OK自动评分器的使用

py环境的配置我就不多提了，网上很多，我使用的是VS Code

使用

写完函数，测试时要呼出终端，但方式不止一种，这是vs的一种方式请添加图片描述

也可以在文件夹中打开测评

在这里插入图片描述

测试代码一般在文档之中都有写：

请添加图片描述在这里插入图片描述

后边加上 --local 表明在本地测试即可：

python3 ok -q falling --local
python3 ok -q digit_distance --local

此外

okpy命令生成器
有一种情况是py版本太高，ok不适用了，降降版本就行了
如果输入代码后报错，也可能是文件解压格式后的地址不正确

"...\CS61A\hw\hw01\hw01.py"
"...\CS61A\lab\lab01\lab01.py"
"...\CS61A\proj\cats\cats.py"
"...\CS61A\hw\hw05\hw05\hw05.py" （错误地址）有的时候解压完毕可能出现，两个hw05，这时就报错了

三、期间遇到的一些难点

我不会每个都有解析的，只是记录一下我学习时遇到的，每个人遇到的可能都不太一样，但还是希望帮助一下和我问题相似的同学当然，也可以看看我的例子，分享分享你的解法最后，希望各位同学勤于思考，不要太懒惰哦！

写题时的方法

这些题嘛倒不是很难，重要的是对题意的理解，以及上下文的分析

因为是英文，所有你可能需要一款沉浸式翻译的插件沉浸式翻译插件网址
首先，要明白函数的大致作用
其次，联系上下文，明白函数接收的参数是什么，返回的是什么
接着，你要根据例子，逐步理解函数内部是如何对数据进行操作的
最后，你可以开始根据你的经验和知识构筑函数啦

hogs -> Problem 8（make_averaged函数）

我只是稍作分析哈！

函数的作用：输入参数，调用original_function函数samples_count次，将其值累加汇总起来，求平均。需要注意的是original_function函数的运作，不然的话有些例子很难理解。
该函数接收：一个original_function函数，samples_count=1000（调用original_function的次数）
返回：一个函数，这个局部函数接收与original_function函数，具有相同数量的参数

def make_averaged(original_function, samples_count=1000):
    """Return a function that returns the average value of ORIGINAL_FUNCTION
    called SAMPLES_COUNT 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    嗨嗨嗨：注意这里，例子过不去，就要再会过头去理解理解roll_dice函数了。
    """
    # BEGIN PROBLEM 8
    def average(*args):
        count = 0
        for i in range(samples_count):
            count += original_function(*args)
        return count / samples_count
    return average
    # END PROBLEM 8

cats -> Problem 7 （minimum_mewtations函数）

这个题使用了动态规划算法（DP），和贪心有点像，但每一步操作都和上一个状态有关
typed: 起始字符串，需要通过编辑操作变换成 source。 source: 目标字符串，我们希望 typed 变换成它。 limit: 编辑操作的上限。写的时间长，我也忘了为什么没用它就过了
dp我使用了二维数组，一个维度代表移除，一个添加，两个加起来就是替换了，是不是很妙
我好像疏忽了点什么，limit应该是提前结束的一个标志，一旦操作数超过limit就自动结束，但是这在二维表里很难操作，不加反而过了

解题步骤，首先你要明白这几点

dp 数组（dp table）以及下标的含义 dp[i][j] 的含义：dp[i][j] 表示将 typed 的前 i 个字符转换为 source 的前 j 个字符所需的最少编辑次数。
确定递推公式
- 递推公式：
- 如果 dna1[i-1] == dna2[j-1]，则 dp[i][j] = dp[i-1][j-1]，即不需要任何编辑操作。
- 如果 dna1[i-1] != dna2[j-1]，则 dp[i][j] 可以通过以下三种操作之一得到：
  - 替换：dp[i-1][j-1] + 1
  - 删除：dp[i-1][j] + 1
  - 插入：dp[i][j-1] + 1
- 所以，dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
dp 数组如何初始化
- 初始化：
  - dp[0][j] 表示将空字符串转换为 typed 的前 j 个字符，需要 j 次插入操作。
  - dp[i][0] 表示将 source 的前 i 个字符转换为空字符串，需要 i 次删除操作。
确定遍历顺序
- 遍历顺序：从左到右，从上到下。
举例推导 dp 数组
结束条件
- 对于 dp[i][j] <= limit，即如果操作数超过 limit，则停止计算。【注】：可能很难操作

</details>

def minimum_mewtations(typed, source, limit):
    """A diff function that computes the edit distance from TYPED to SOURCE.
    This function takes in a string TYPED, a string SOURCE, and a number LIMIT.
    Arguments:
        typed: a starting word
        source: a string representing a desired goal word
        limit: a number representing an upper bound on the number of edits
    >>> big_limit = 10
    >>> minimum_mewtations("cats", "scat", big_limit)       # cats -> scats -> scat
    2
    >>> minimum_mewtations("purng", "purring", big_limit)   # purng -> purrng -> purring
    2
    >>> minimum_mewtations("ckiteus", "kittens", big_limit) # ckiteus -> kiteus -> kitteus -> kittens
    3
    """
    a = len(typed)
    b = len(source)

    #初始化
    dp = [[0] * (b+1) for _ in range(a+1)]
    for i in range(1, b+1):
        dp[0][i] = i
    for i in range(1, a+1):
        dp[i][0] = i
    
    #执行判断
    for i in range(0, a):
        for j in range(0, b):
            if typed[i] == source[j]:
                dp[i+1][j+1] = dp[i][j]
            else:
                dp[i+1][j+1] = min(dp[i][j] + 1,
                                   dp[i][j+1] + 1,
                                   dp[i+1][j] + 1)          
    return dp[a][b]

Ants

Hello，别想着在这里找太多教程了！这个项目目的就是为了让你搞懂它的结构。你可能会遇到一些“小麻烦”，但别慌，解决方案都藏在源码里。其实，它没什么复杂的算法，更多的是需要你细心发掘。预祝各位在这趟项目之旅中一路顺风！如果实在需要帮助，不妨翻翻本仓库的Ants项目，阅读源码也是一种乐趣。Good Luck！

self.place.bees：一个实例所存在的地点，该地点所存在的bees，返回一个bees列表。
有些问题或许在父类中直接解决会更好。
当你在遍历一个列表的同时对其进行修改时，可能会导致某些元素被跳过，这是因为遍历时列表的长度和索引会发生变化。

Scheme

这是旅程的最后一次冒险，他并非看起来那么困难，你只需要耐心阅读代码，理解其中的逻辑，即可wandering through the code. 本仓库是你最坚强的后盾！

余者不再多提，我只强调两点：

The first three parts：Pair类真的很重要，这涉及到一些格式问题，如果不能正确理解，你写出的代码可能无法运行。

Part IV：函数嵌套而已，注意不要在question.scm里使用中文注释，否则会发生如下报错：

scm> (load 'questions)
    Traceback (most recent call last):
    k (most recent call last):
    File "E:\Desktop files\code\py\CS61A\proj\scheme\ok\client\sources\ok_test\scheme.py", line 58, in evaluate
        result = timer.timed(self.timeout, self.scheme.scheme_eval,
                ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "E:\Desktop files\code\py\CS61A\proj\scheme\ok\client\utils\timer.py", line 33, in timed
        raise submission.error
    File "E:\Desktop files\code\py\CS61A\proj\scheme\ok\client\utils\timer.py", line 49, in run
        self.result = self.fn(*self.args, **self.kargs)
                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "E:\Desktop files\code\py\CS61A\proj\scheme\scheme_eval_apply.py", line 54, in scheme_eval
        return scheme_apply(procedure, args, env)  # 应用操作符到参数
            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    File "E:\Desktop files\code\py\CS61A\proj\scheme\scheme_eval_apply.py", line 75, in scheme_apply
        return procedure.py_func(*arr)
            ^^^^^^^^^^^^^^^^^^^^^^^
    File "E:\Desktop files\code\py\CS61A\proj\scheme\scheme_builtins.py", line 369, in scheme_load
        lines = infile.readlines()
                ^^^^^^^^^^^^^^^^^^
    UnicodeDecodeError: 'gbk' codec can't decode byte 0x80 in position 390: illegal multibyte sequence

Hw4 -> Q3: Balanced

移动式结构（Mobile）的定义：一个移动式结构由多个臂组成，每个臂可能悬挂一个行星（Planet）或另一个移动式结构（Mobile）。
平衡的定义：一个移动式结构被认为是平衡的，需要满足以下条件：
- 左右两边的扭矩相等。
- 每个悬挂在臂端的移动式结构或行星本身也是平衡的。
这个函数本身不难实现，难在对 arm 结构的理解与 total_mass(), end()函数的应用,
实现不是很难，理解以上三个定义即可顺利写出，我就不多说了

def arm(length, mobile_or_planet):
    """Construct an arm: a length of rod with a mobile or planet at the end."""
    assert is_mobile(mobile_or_planet) or is_planet(mobile_or_planet)
    return ['arm', length, mobile_or_planet]
    
def balanced(m):
    """Return whether m is balanced.

    >>> t, u, v = examples()
    >>> balanced(t)
    True
    >>> balanced(v)
    True
    >>> p = mobile(arm(3, t), arm(2, u))
    >>> balanced(p)
    False
    >>> balanced(mobile(arm(1, v), arm(1, p)))
    False
    >>> balanced(mobile(arm(1, p), arm(1, v)))
    False
    >>> from construct_check import check
    >>> # checking for abstraction barrier violat

CS61A

Install / Use

README