伯克利 CS61A 课堂笔记 10 —— Trees
本系列为加州伯克利大学著名 Python 基础课程 CS61A 的课堂笔记整理,全英文内容,文末附词汇解释。
目录
01 Trees 树
Ⅰ Tree Abstraction
Ⅱ Implementing the Tree Abstraction
02 Tree Processing 建树过程
Ⅰ Fibonacci tree
Ⅱ Tree Processing uses recursion
Ⅲ Creating Trees
03 Example: Printing Trees
04 Example: Summing Paths
05 Example: Counting Paths
附:词汇解释
01 Trees 树
Ⅰ Tree Abstraction
Recursive description (wooden trees):
A tree has a root label and a list of branches.
Each branch is a tree.
A tree with zero branches is called a leaf.
Relative description (family trees):
Each location in a tree is called a node.
Each node has a label that can be any value.
One node can be the parent/child of another.
Ⅱ Implementing the Tree Abstraction
>>> tree(3, [tree(1), tree(2, [tree(1), tree(1)])])
[3, [1], [2, [1], [1]]]
#Treesdef tree(label, branches=[]):#Verifies the tree definitionfor branch in branches:assert is_tree(branch)return [label] + list(branches)def label(tree):return tree[0]def branches(tree):return tree[1:]def is_leaf(tree):return not branches(tree)def is_tree(tree):#Verifies the tree definitionif type(tree) != list or len(tree) < 1:return falsefor branch in branches(tree):if not is_tree(branch):return falsereturn true
>>> tree(1)
[1]
>>> is_leaf(tree(1))
true>>> t = tree(1, [tree(5, [tree(7)]), tree(6)])
>>> t
[1, [5, [7]], [6]]
>>> label(t)
1
>>> branches(t)
[[5, [7]], [6]]
>>> branches(t)[0]
[5, [7]]
>>> is_tree(branches(t)[0])
true
>>> label(branches(t)[0])
5
02 Tree Processing 建树过程
Ⅰ Fibonacci tree
def fib_tree(n):if n <= 1:return tree(n)else:left, right = fib_tree(n-2), fib_tree(n-1)return tree(label(left)+label(right), [left, right])
>>> fib_tree(0)
[0]
>>> fib_tree(1)
[1]
>>> fib_tree(2)
[1, [0], [1]]
>>> fib_tree(4)
[3, [1, [0], [1]], [2, [1], [1, [0], [1]]]]
>>> label(fib_tree(4))
3
Ⅱ Tree Processing uses recursion
Processing a leaf is often the base of a tree processing function.
The recursive case typically makes a recursive call on each branch, then aggregates the results.
def count_leaves(t):"""Count the leaves of a tree."""if is_leaf(t):return 1else:#寻找分支的叶子return sum([count_leaves(b) for b in branches(t)])
>>> count_leaves(fib_tree(4))
5
>>> count_leaves(fib_tree(10))
89
Implement leaves, which returns a list of the leaf of a tree.
Hint: If you sum a list of lists, you get a list containing the elements of those lists.
>>> sum([[1], [2, 3], [4]], [])
[1, 2, 3, 4]
>>> sum([[1]], [])
[1]
>>> sum([[[1]], [2]], [])
[[1], 2]
def leaves(tree):"""Return a list containing the leaf labels of tree.>>> leaves(fib_tree(4))[0, 1, 1, 0, 1]"""if is_leaf(tree):return [label(tree)]else:#寻找分支的叶子return sum([leaves(b) for b in branches(tree)], [])
Ⅲ Creating Trees
A function that creates a tree from another tree is typically also recursive.
def increment_leaves(t):"""Return a tree like t but with leaf labels incremented."""if is_leaf(t):return tree(label(t) + 1)else:return tree(label(t), [increment_leaves(b) for b in branches(t)])def increment(t):"""Return a tree like t but with all labels incremented."""return tree(label(t) + 1, [increment_leaves(b) for b in branches(t)])
03 Example: Printing Trees
#原始版
def print_tree(t):print(label(t))for b in branches(t):print_tree(b)
>>> print_tree(fib_tree(4))
3
1
0
1
2
1
1
0
1
#升级版
def print_tree(t, indent=0){print(' ' * indent + str(label(t)))for b in branches(t):print_tree(b, indent + 1)
}
>>> print_tree(fib_tree(4))
310121101
04 Example: Summing Paths
def fact(n):"Return n * (n-1) * ... * 1"if n == 0:return 1else:return n * fact(n - 1)def fact_times(n, k):"Return k * n * (n-1) * ... * 1"if n == 0:return kelse:return fact_times(n - 1, k * n)def fact_plus(n):return fact_times(n, 1)
>>> fact_plus(4)
24
from tree import *numbers = tree(3, [tree(4), tree(5, [tree(6)])])haste = tree('h', [tree('a', [tree('s'),tree('t')]),tree('e')])def print_sums(t, so_far):so_far = so_far + label(t)if is_leaf(t):print(so_far)else:for b in branches(t):print_sums(b, so_far)
>>> print_sums(numbers, 0)
7
14
>>> print_sums(haste, '')
has
hat
he
05 Example: Counting Paths
Count paths that have a total label sum.
def count_paths(t, total):"""Return the number of paths from the root to any node in tree tfor which the labels along the path sum to total.>>> t = tree(3, [tree(-1), tree(1, [tree(2, [tree(1)]), tree(3)]), tree(1, [tree(-1)])])>>> count_paths(t, 3)2>>> count_paths(t, 4)2>>> count_paths(t, 5)0>>> count_paths(t, 6)1>>> count_paths(t, 7)2"""if label(t) == total:found = 1else:found = 0return found + sum(count_paths(b, total - label(t)) for b in branches(t))
附:词汇解释
verify 证明、definition 定义、aggregate / ˈæɡrɪɡət / 合计、hint / hɪnt / 提示、increment / ˈɪŋkrəmənt / 增长、indent / ɪnˈdent / 缩进、factorial / fækˈtɔːriəl / 阶乘
相关文章:
伯克利 CS61A 课堂笔记 10 —— Trees
本系列为加州伯克利大学著名 Python 基础课程 CS61A 的课堂笔记整理,全英文内容,文末附词汇解释。 目录 01 Trees 树 Ⅰ Tree Abstraction Ⅱ Implementing the Tree Abstraction 02 Tree Processing 建树过程 Ⅰ Fibonacci tree Ⅱ Tree Process…...
Springboot 高频面试题
以下是Spring Boot的高频面试题及答案和底层原理解释: 基础概念 什么是Spring Boot,其主要特点是什么? 答案: Spring Boot本质上是一个建立在Spring框架之上的快速应用开发框架。其主要特点包括: 启动器:一…...
从零开始玩转TensorFlow:小明的机器学习故事 2
你好,TensorFlow!——从零开始的第一个机器学习程序 1. 为什么要写这个“Hello, TensorFlow!”? 无论学习什么新语言或新框架,“Hello World!”示例都能帮助我们快速确认开发环境是否就绪,并掌握最基本的使用方式。对…...
第四届图像、信号处理与模式识别国际学术会议(ISPP 2025)
重要信息 会议官网:www.icispp.com 会议时间:2025年3月28-30日 会议地点:南京 简介 由河海大学和江苏大学联合主办的第四届图像、信号处理与模式识别国际学术会议(ISPP 2025) 将于2025年3月28日-30日在中国南京举行。会议主…...
阿里云通过docker安装skywalking及elasticsearch操作流程
系统 本文使用系统为 Alibaba Cloud Linux 3.2104 LTS 64位 配置为 4核8G PS:最低配置应为2核4G,配置过低无法启动 安装docker 1.卸载旧版本docker yum remove docker \docker-client \docker-client-latest \docker-common \docker-latest \docker-…...
Linux·spin_lock的使用
自旋锁 内核当发生访问资源冲突的时候,可以有两种锁的解决方案选择: 一个是原地等待一个是挂起当前进程,调度其他进程执行(睡眠) Spinlock 是内核中提供的一种比较常见的锁机制,自旋锁是“原地等待”的方…...
企业内部真题
文章目录 前端面试题:一个是铺平的数组改成树的结构问题一解析一问题一解析二前端面试题:for循环100个接口,每次只调3个方法一:使用 `async/await` 和 `Promise`代码解释(1):代码解释(2):1. `fetchApi` 函数2. `concurrentFetch` 函数3. 生成 100 个接口地址4. 每次并…...
MySQL基本操作——包含增删查改(环境为Ubuntu20.04,MySQL5.7.42)
1.库的操作 1.1 创建数据库 语法: 说明: 大写的表示关键字 [] 是可选项 CHARACTER SET: 指定数据库采用的字符集 COLLATE: 指定数据库字符集的校验规则 1.2 创建案例 创建一个使用utf8字符集的db1数据库 create database db1 charsetutf8; …...
程序代码篇---Python指明函数参数类型
文章目录 前言简介一、函数参数的类型指定1. 基本类型提示2. 默认参数3. 可变参数4. 联合类型(Union)5. 可选类型(Optional)6. 复杂类型 二、返回值的类型指定1. 基本返回类型2. 无返回值(None)3. 返回多个…...
AIGC视频扩散模型新星:SVD——稳定扩散的Video模型
大家好,这里是好评笔记,公主号:Goodnote,专栏文章私信限时Free。本文详细介绍慕尼黑大学携手 NVIDIA 等共同推出视频生成模型 Video LDMs。NVIDIA 在 AI 领域的卓越成就家喻户晓,而慕尼黑大学同样不容小觑,…...
MySql面试宝典【刷题系列】
文章目录 一、Mysql 的存储引擎 myisam 和 innodb 的区别。二、MySQL数据库作发布系统的存储,一天五万条以上的增量,预计运维三年,怎么优化?三、对于大流量的网站,您采用什么样的方法来解决各页面访问量统计问题?四、锁的优化策略…...
银河麒麟系统安装mysql5.7【亲测可行】
一、安装环境 cpu:I5-10代; 主板:华硕; OS:银河麒麟V10(SP1)未激活 架构:Linux 5.10.0-9-generic x86_64 GNU/Linux mysql版本:mysql-5.7.34-linux-glibc2.12-x86_64.ta…...
CTF-内核pwn入门1: linux内核模块基础原理
本文由A5rZ在2025-2-18-21:00编写 1.可加载内核模块是什么? 内核可加载模块(*.ko 文件)是内核的一种扩展机制,可以在不重启系统的情况下加载和卸载代码。它们允许动态地向内核添加新的功能或支持。 以下是一些内核模块常见的功能&…...
第4章 4.1 Entity Framework Core概述
4.1.1 什么是ORM ORM (object tralstional mapping ,对象关系映射)中的“对象”指的就是C#中的对象,而“关系”是关系型数据库,“映射”指搭建数据库与C#对象之间的“桥梁”。 比如使用ORM ,可以通过创建C#对象的方式把数据插入数据库而不需…...
【C语言】自定义类型:联合体和枚举
1. 联合体 1.1 联合体类型的声明 像结构体一样,联合体也是由一个或者多个成员构成,这些成员可以是不同的类型。 但是编译器只为最大的成员分配足够的内存空间。联合体的特点是所有成员共用同一块内存空间。所以联合体也叫:共用体。 给联合…...
企业组网IP规划与先关协议分析
目录 一、IP编址 1、IP地址组成 2、IP地址表达 3、IP 地址分类 4、IP地址类型 5、IP网络通信 6、子网掩码 7、默认子网掩码 8、IP 地址规划 9、有类IP编制缺陷 10、VLSM 11、变长子网掩码案例 12、网关 13、无类域间路由 一、IP编址 网络层位于数据链路层与传输层之间…...
数据结构之【顺序表简介】
1.顺序表的概念 顺序表 是 用一段物理地址连续的存储单元 依次 存储数据元素的线性结构 一般情况下采用数组存储 2.顺序表的结构 既然顺序表可以用来存储数据元素, 那就少不了 增删查改 的操作 此时,单一地只创建数组满足不了上述操作 创建相应的结构…...
如何调用 DeepSeek API:详细教程与示例
目录 一、准备工作 二、DeepSeek API 调用步骤 1. 选择 API 端点 2. 构建 API 请求 3. 发送请求并处理响应 三、Python 示例:调用 DeepSeek API 1. 安装依赖 2. 编写代码 3. 运行代码 四、常见问题及解决方法 1. API 调用返回 401 错误 2. API 调用返回…...
一周学会Flask3 Python Web开发-flask3模块化blueprint配置
锋哥原创的Flask3 Python Web开发 Flask3视频教程: 2025版 Flask3 Python web开发 视频教程(无废话版) 玩命更新中~_哔哩哔哩_bilibili 我们在项目开发的时候,多多少少会划分几个或者几十个业务模块,如果把这些模块的视图方法都写在app.py…...
vxe-table实现动态列
vxe-table实现动态列 1.动态列解释2.解决步骤2.1将后端返回的动态列表头,按照格式拼接在固定列表头上2.2将后端返回的列表数据按照键值对格式组装 1.动态列解释 正常列表是有固定的列;我的需求是,最初只知道表格的固定两列,查询数…...
day16_推荐系统和总结
文章目录 day16_推荐系统和总结一、推荐实现1、基于流行度推荐(掌握)1.1 近期热门商品推荐1.2 个人热门商品推荐 2、基于隐语义模型的协同过滤推荐(了解)2.1 ALS算法介绍2.2 推荐代码 3、基于物品的协同过滤推荐(了解&…...
Scifinder数据库专利检索实操教程
在上期的内容里,我为大家分享了查询专利的数据库。发出后有小伙伴问,怎么没有大佬Scifinder!这不,应大家的呼声,今天就来给大家好好讲讲 Scifinder专利检索!! SciFinder,由美国化学会…...
Linux下 <用户名> is not in the sudoers file
参考链接 https://blog.csdn.net/weixin_49192027/article/details/114702099 原因 当前的用户没有加入到sudo的配置文件里 解决方案 切换到root用户 su 编辑配置文件 vim /etc/sudoers 如果没有安装vim 运行命令 sudo apt-get install vim vim的使用教程 参考链接…...
Linux下基本指令(4)
Linux权限的概念 Linux下有两种用户:超级用户(root)、普通用户。 超级用户:可以再linux系统下做任何事情,不受限制 普通用户:在linux下做有限的事情。 超级用户的命令提示符是“#”,普通用户…...
【算法与数据结构】字典树(Trie)详解
目录 一,字典树的定义 二,字典树的代码实现 完整代码详细注释: 测试用例测试结果: 三,处理其他字符 四,内存优化与扩展 1. 内存优化 2. 扩展功能 五,扩展功能支持通配符匹配 六&…...
el-table树状表格,默认展开第一个节点的每一层
效果如图 <template><el-table:data"tableData"style"width: 100%":tree-props"{ children: children, hasChildren: hasChildren }":expand-row-keys"expandRowKeys"row-key"id"expand-change"handleExpan…...
RPA-实例(UiPath )
UiPath 是一个流行的机器人流程自动化(RPA)工具,用于自动化重复性任务。以下是一个简单的实例,展示如何使用 UiPath 自动化一个常见的任务:从 Excel 文件中读取数据并将其输入到网页表单中。 实例:从 Excel 读取数据并自动填写网页表单 步骤 1:准备工作 安装 UiPath S…...
【RabbitMQ业务幂等设计】RabbitMQ消息是幂等的吗?
在分布式系统中,RabbitMQ 自身不直接提供消息幂等性保障机制,但可通过业务逻辑设计和技术组合实现消息处理的幂等性。以下是 8 种核心实现方案及最佳实践: 一、消息唯一标识符 (Message Deduplication) 原理 每条消息携带全局唯一IDÿ…...
Spring Boot项目开发常见问题及解决方案(上)
启动相关问题 问题 1:项目启动时报错“找不到主类” 在使用 Spring Boot 打包成可执行 JAR 文件后启动,有时会遇到这个头疼的问题。通常是因为打包配置有误或者项目结构不符合要求。 解决方案: 首先,检查 pom.xml(Ma…...
具有整合各亚专科医学领域知识能力的AI智能体开发纲要(2025版)
整合各亚专科医学领域知识能力的AI代理的开发与研究 一、引言 1.1 研究背景 在科技飞速发展的当下,人工智能(AI)已成为推动各行业变革的关键力量,医疗领域也不例外。近年来,AI 在医疗行业的应用取得了显著进展,从医学影像诊断到疾病预测,从药物研发到个性化医疗,AI 技…...
Selenium实战案例1:论文pdf自动下载
在上一篇文章中,我们介绍了Selenium的基础用法和一些常见技巧。今天,我们将通过中国科学:信息科学网站内当前目录论文下载这一实战案例来进一步展示Selenium的web自动化流程。 目录 中国科学:信息科学当期目录论文下载 1.网页内…...
进程的介绍--进程状态/切换
1.冯 • 诺依曼体系结构 1.1 体系结构 冯•诺依曼结构也称普林斯顿结构,是一种将程序指令存储器和数据存储器合并在一起的存储器结构。数学家冯•诺依曼提出了计算机制造的三个基本原则,即采用二进制逻辑、程序存储执行以及计算机由五个部分组成&#x…...
一文详解U盘启动Legacy/UEFI方式以及GPT/MBR关系
对于装系统的老手而说一直想研究一下装系统的原理,以及面对一些问题时的解决思路,故对以前的方法进行原理上的解释,主要想理解其底层原理。 引导模式 MBR分区可以同时支持UEFI和Legacy引导,我们可以看一下微pe制作的启动盘&#…...
【面试】Redis 常见面试题
一、介绍一下什么是 Redis,有什么特点? Redis 是一个高性能的 key-value 内存数据库。 不同于传统的 MySQL 这样的关系型数据库,Redis 主要使用内存存储数据(当然也支持持久化存储到硬盘上),并非是使用 “表” 这样…...
扩散模型中,Flow Matching的训练方式相比于 DDPM 训练方法有何优势?
在扩散模型中,Flow Matching(FM)相比DDPM(Denoising Diffusion Probabilistic Models)的训练方法具有以下核心优势: 1. 更简单的训练目标 DDPM:通过逐步预测噪声来间接优化数据分布的变分下界(ELBO),需要设计多步的噪声调度策略,训练目标依赖马尔可夫链的分解。Flow…...
Unity FBXExport导出的FBX无法在Blender打开
将FBX转换为obj: Convert 3D models online - free and secure...
【无标题】基于Unity写一个DelayInvoke方法
没想到来得这么块,程序员可能比司机先失业了。。。。。。。。 //测试过一定要这么调用??奇怪的是,不能(mono 直接引用)??///但AI还是给出了能用的代码 MonoBehaviourExtensions.DelayInvoke(this,()=> { },3); /* 方案一,使用示例(): public class ExampleUsag…...
JavaScript 语言基础之标签语句
标签语句的语法 label: statement label 表示标签名,可以是任何合法的标识符,但不能是 JavaScript 中的保留字。statement 表示被标记的语句块,可以是任何合法的 JavaScript 语句。 用法 标签语句的主要用途是在代码中进行跳转࿰…...
【网络编程】网络编程基础:TCP/UDP 协议
一、什么是网络? 网络是信息传输,接收和共享的虚拟世界,通过把网络上的信息汇聚在一起,将这些资源进行共享。 初衷:知识共享。这里不得不提到Internet 的历史-它其实是“冷战”的产物: 1957年…...
idea 部署 AJ-Report 启动的注意事项
AJ-Report 入门参考: AJ-Report 初学(入门教程) gitee 下载:https://gitee.com/anji-plus/report/releases 根据上面提供的 gitee 下载链接,点击直接下载 最上面的就是最新版本的,旧版本往下拉就可以找到,有三个下载…...
C# 生成二维码隐藏ASCII码
在 C# 中生成二维码时,如果需要隐藏或过滤掉 ASCII 码中的控制字符或不可见字符,可以在生成二维码之前对输入文本进行处理。以下是完整的实现步骤和代码示例: 1. 过滤 ASCII 码中的控制字符 ASCII 码中,0 到 31 以及 127 是控制字…...
python有没有不同精度的整型类型?
在 Python 中,不像 C、Java 等语言有明确的不同精度整型类型(如 int8、int16、int32、int64 等),Python 提供了统一的整数类型 int,它可以处理任意大小的整数,没有固定的精度限制。不过,Python …...
Python多线程编程理解面试题解析
一、多线程介绍 Python 的多线程是一种实现并发编程的方式,允许程序同时执行多个任务。然而,由于 Python 的全局解释器锁(GIL)的存在,多线程在某些场景下可能无法充分利用多核 CPU 的性能。以下是对 Python 多线程的理…...
网络协议相关知识有哪些?
前言 网络协议的基础是OSI和TCP/IP模型,这两个模型是理解协议分层的关键。 正文(仅是个人理解,如有遗漏望海涵) 网络协议是网络中设备间通信的规则和标准,涉及数据传输、路由、错误控制等多个方面。以下是网络协议相关知识的系统梳理: 一、网络协议分层模型 1、OSI七…...
【并发压测】高并发下Linux流量监控
在高并发环境下,Linux流量监控至关重要,可以帮助您确保网络性能和稳定性。以下是一些常用的Linux流量监控工具和方法: 1. **iftop**:iftop 是一款实时的网络流量监控工具,可以显示当前服务器上每个网络接口的流量使用情…...
Spring Boot项目中解决跨域问题(四种方式)
目录 一,跨域产生的原因二,什么情况下算跨域三,实际演示四,解决跨域的方法 1,CrossOrigin注解2,添加全局过滤器3,实现WebMvcConfigurer4,Nginx解决跨域5,注意 开发项目…...
革新之力:数字科技——重塑未来的超越想象之旅
在21世纪的科技浪潮中,数字科技如同一股不可阻挡的洪流,正以前所未有的速度和广度改变着我们的生活、工作乃至整个社会的结构。它不仅是技术的简单迭代,更是对人类社会认知边界的拓宽,对经济模式、社会治理、文化形态等多方面的深…...
matlab和java混合编程经验分享
最常用的就是可以查到再控制栏deploytool选择library complier打包,但是有问题就是比如果用了外部的求解器比如yalmip或者cplex的话用这个方法会找不到外部的求解器,网上找了很多,基本都大同小异。 后面分享一个亲测有效的打包方法࿰…...
rk3588/3576板端编译程序无法运行视频推理
图片推理可以,但是视频不行,运行视频推理报错:segment fault. 我遇到的问题原因是ffmpeg安装有问题,可以先在板端运行:ffmpeg -version ffmpeg version 4.2.4-1ubuntu1.0firefly6 Copyright (c) 2000-2020 the FFmpe…...
MATLAB在数据分析和绘图中的应用:从基础到实践
引言 股票数据分析是金融领域中的重要研究方向,通过对历史价格、成交量等数据的分析,可以帮助投资者更好地理解市场趋势和做出决策。MATLAB作为一种强大的科学计算工具,提供了丰富的数据处理和可视化功能,非常适合用于股票数据的…...