<对变量进⾏迭代> { 3. <需要重复执⾏的命令> 4. } 例如，我们可以反复执⾏n次输出操作 1. let mut i = 0 2. while i < 2, i = i + 1 { 3. println("Output") 4. } // 重复输出2次 12 循环 我们进⼊循环时 判断是否满⾜继续循环的条件 执⾏命令 对变量进⾏迭代 重复以上过程 例如 1. let mut <-- 0 < 2，因此继续执⾏，输出第⼀次 4. } // <-- 此时，我们执⾏i = i + 2 13 循环 我们进⼊循环时 判断是否满⾜继续循环的条件 执⾏命令 对变量进⾏迭代 重复以上过程 例如 1. // 此时 i 等于 1 2. while i < 2, i = i + 1 { // <-- 此处，我们判断 i < 2 是否为真 3. println("Output") <-- 1 < 2，因此继续执⾏，输出第⼆次 4. } // <-- 此时，我们执⾏i = i + 2 14 循环 我们进⼊循环时 判断是否满⾜继续循环的条件 执⾏命令 对变量进⾏迭代 重复以上过程 例如 1. // 此时 i 等于 2 2. while i < 2, i = i + 1 { // <-- 此处，我们判断 i < 2 是否为真，结果为假 3. } // <-- 跳过

列表与递归 Hongbo Zhang 1 基本数据类型：函数 2 函数 在数学上，描述对应关系的⼀种特殊集合 对于特定的输⼊，总是有特定的输出 在计算机中，对相同运算的抽象，避免⼤量重复定义 计算半径为1的圆的⾯积： 3.1415 * 1 * 1 计算半径为2的圆的⾯积： 3.1415 * 2 * 2 计算半径为3的圆的⾯积： 3.1415 * 3 * 3 …… fn ⾯积(半径: Int)) -> (Int, Int, Int) 接受⼀个元组并返回⼀个元组 11 数据类型：列表 12 列表：⼀个数据的序列 我们有时会收到⼀些数据，具备以下特征： 数据是有序的 数据是可以重复的 数据的数量是不定的 举例来说 ⼀句话中的⽂字：� '⼀' '句' '话' '中' '的' '⽂' '字' � DNA序列：� G A T T A C A � …… 13 列表的接⼝ { 1L } else { fib(num - 1) + fib(num - 2) } 3. } 我们观察到了⼤量的重复计算 34 动态规划 将问题分解为与原问题相似的、规模更⼩的问题来求解 适⽤于⼦问题 有重叠⼦问题：动态规划对每个⼦问题求解⼀次，将其保存，避免重复运算 有最优⼦结构：局部最优解可以决定全局最优解 动态规划分为⾃顶向下和⾃底向上 ⾃顶向下：针对每个⼦问题，如果已求解，直接使⽤缓存结果；否则求解并缓

缺点：对于复杂表达式容易出错 数值微分： 缺点：计算机⽆法精准表达⼩数，且绝对值越⼤，越不精准 符号微分： Mul(Const(2), Var(1)) -> Const(2) 缺点：计算结果可能复杂；可能重复计算；难以直接利⽤语⾔原⽣控制流 1. // 需要额外定义原⽣算⼦以实现相同效果 2. fn max[N : Number](x : N, y : N) -> N { 3. if x.value() 缺点：对于复杂表达式容易出错 数值微分： 缺点：计算机⽆法精准表达⼩数，且绝对值越⼤，越不精准 符号微分： Mul(Const(2), Var(1)) -> Const(2) 缺点：计算结果可能复杂；可能重复计算；难以直接利⽤语⾔原⽣控制流 ⾃动微分：利⽤复合函数求导法则、由基本运算组合进⾏微分 分为前向微分和后向微分 14 符号微分 我们以符号微分定义表达式构建的⼀种语义 1. enum Symbol

现代编程思想 泛型与⾼阶函数 Hongbo Zhang 1 设计良好的抽象 软件⼯程中，我们要设计良好的抽象 当代码多次重复出现 当抽出的逻辑具有合适的语义 编程语⾔为我们提供了各种抽象的⼿段 函数、泛型、⾼阶函数、接⼝…… 2 泛型函数与泛型数据 3 堆栈 栈是⼀个由⼀系列对象组成的⼀个集合，这些对象的插⼊和删除遵循后进先出原则 （Last In First Out） Cons(hd, tl) => f(hd, fold_right(tl, f, b)) 5. } 6. } ⾼阶函数：接受函数作为参数或以函数作为运算结果的函数 18 函数是⼀等公⺠ 重复⼀个函数的运算 1. fn repeat[A](f: (A) -> A) -> (A) -> A { // repeat的类型是((A) -> A) -> (A) -> A 2. fn (a)

Plus = "+" 每⼀⾏对应⼀个匹配规则 "xxx" ：匹配内容为xxx的字符串 a b ：匹配规则a，成功后匹配规则b a / b ：匹配规则a，匹配失败则匹配规则b *a ：重复匹配规则a，可匹配0或多次 %x30 ：UTF编码⼗六进制表示为30的字符（ "0" ） 4 词法分析 算术表达式的词法定义 1. Number = %x30 / (%x31-39) *(%x30-39) { 4. None => parser2.parse(input) 5. Some(_) as result => result 6. } }) } 10 解析器组合⼦ 重复解析 a ，零或多次，直到失败为⽌ 1. fn many[Value](self: Lexer[Value]) -> Lexer[List[Value]] { 2. Lexer(fn(input)

涉及哪些概念，它们之间存在怎样的联系？ �. 定义接⼝ 程序应当如何与环境互动？ �. 写测试案例 对于典型输⼊，程序应当如何表现？对于⾮正常输⼊呢？ �. 实现规定的⾏为 经常需要将问题分解为更简单的⼦问题并对各⼦问题重复以上流程 7 ⼀个设计例题 超市正在促销，你可以⽤ num_exchange 个空⽔瓶从超市兑换⼀瓶⽔。最开始，你 ⼀共购⼊了 num_bottles 瓶⽔。 如果喝掉了⽔瓶中的⽔，那么⽔瓶就会变成空的。

} 每⼀种可能的情况即是构造器 1. let monday: DaysOfWeek = Monday 2. let tuesday: DaysOfWeek = Tuesday 枚举类型定义可能重复，需要加上 <类型>:: 加以区分 1. enum Repeat1 { A; B } 2. enum Repeat2 { A; B } 3. let x: Repeat1 = Repeat1::A

IntTree { 2. Node(Int, IntTree, IntTree) // 存储的数据，左⼦树，右⼦树 3. Empty 4. } 9 ⼆叉树的遍历 树的遍历是指以某种规律，不重复地访问树的所有节点的过程 深度优先遍历：总是先访问⼀个⼦树，再访问另⼀个⼦树 ⼴度优先遍历：从根节点开始，访问深度相同节点 10 ⼆叉树的遍历 前序遍历：先访问根节点，再访问左⼦树，再访问右⼦树

现代编程思想 哈希表与闭包 Hongbo Zhang 1 回顾 表 键值对的集合，其中键不重复 简单实现：⼆元组列表 添加时向队⾸添加 查询时从队⾸遍历 树实现：⼆叉平衡树 基于第五节课介绍的⼆叉平衡树，每个节点的数据为键值对 对树操作时⽐较第⼀个参数 2 哈希表 哈希函数/散列函数 Hash function 将任意⻓度的数据映射到某⼀固定⻓度的数据 在⽉兔的 Hash