《大学计算机第6讲-程序与递归-组合-抽象与构造幻灯片课件》由会员分享，可在线阅读，更多相关《大学计算机第6讲-程序与递归-组合-抽象与构造幻灯片课件（56页珍藏版）》请在金锄头文库上搜索。
1、第6讲程序与递归 组合 抽象与构造 程序是实现系统复杂功能的一种重要手段 程序的本质是组合 抽象与构造 构造的基本手段是递归 一种表达相似性对象及动作的无限性构造的方法 程序与递归 组合 抽象与构造1 程序的作用和本质 程序的作用和本质 计算系统与程序 程序 组合 抽象与构造 指令 控制基本动作执行的命令 与 动作 或 动作 非 动作 ANDORNOT 系统 AANDB ANDC OR NOTC 复杂动作 拆解开 X AANDBX XANDCY NOTCX XORY 程序 由基本动作指令构造的 若干指令的一个组合或一个执行序列 用以实现复杂动作 如何设计实现一个基本计算系统 1 程序的作用和本
2、质1 2什么是程序 指令 控制基本动作执行的命令 与 动作 或 动作 非 动作 ANDORNOT 系统 AANDB ANDC OR NOTC 复杂动作 程序执行机构 自动解释程序中的各种组合 并按次序调用指令 基本动作 予以执行 程序 由基本动作指令构造的 若干指令的一个组合或一个执行序列 用以实现复杂动作 如何设计实现一个基本的计算系统 1 程序的作用和本质1 3程序能否自动执行 基本动作对基本动作的抽象与控制 与 动作AND 或 动作OR 非 动作NOT 复杂动作 基本动作的各种方式的组合 AiXORBi XORCi AiXORBi ANDCi OR AiANDBi 解释这种组合 并按次序
3、调用基本动作予以执行 程序执行机构 程序 指令 计算系统 基本动作 指令 程序执行机构指令 对可执行基本动作的抽象 即控制基本动作执行的命令程序 基本动作指令的一个组合或执行序列 用以实现复杂的动作程序执行机构 负责解释程序即解释指令之间组合 并按次序调用指令即调用基本动作执行的机构 基本动作 1 程序的作用和本质1 4计算系统与程序 基本动作对基本动作的抽象与控制 加 动作 减 动作 乘 动作x 除 动作 复杂动作 基本动作的各种方式的组合 V1 V2 x V3 V4 V5 V1 V2x V3 V4 V5xV6 解释这种组合 并按次序调用基本动作予以执行 程序 程序执行机构 指令 一种较高抽
4、象层次的系统 抽象 抽象 将经常使用的 可由低层次系统实现的一些复杂动作 进行命名 以作为高层次系统的指令被使用 一种较低抽象层次的系统 1 程序的作用和本质1 5程序 组合 抽象 构造 程序构造示例 I 运算组合式的表达 组合 抽象与构造 命名计算对象和构造中使用名字及计算中以计算对象替换名字 程序与递归 组合 抽象与构造2 程序构造示例 I 2 程序构造示例 I 2 1运算组合式 100 205 由数值 到基本运算组合式 中缀表示法 用运算符 即前述的指令 将两个数值组合起来 运算符在中间 100205 100 205 实际的数值 前缀表示法 用运算符 即前述的指令 将两个数值组合起来 运
5、算符在前面 将运算符表示的操作应用于后面的一组数值上 求出结果 100205 20050 2005 20542 20542 20542 由数值 到基本运算组合式 2 程序构造示例 I 2 1运算组合式 运算组合式的 嵌套 及其计算过程 100205 6040 305100 3 24 35 107 6 计算过程 3 24 35 107 6 3 88 36 316 9 489 432 2 程序构造示例 I 2 2如何构造运算组合式 组合 defineheight2 height40 305height 名字的定义 定义名字height与2关联 以后可以用height来表示2一种类型的名字 数值型的
6、名字 50height 100height 名字的使用 命名计算对象和构造中使用名字及计算中以计算对象替换名字 2 程序构造示例 I 2 3如何用名字简化运算组合式的构造 抽象 definepi3 14159 defineradius10 pi radiusradius definecircumference 2piradius circmference20 命名计算对象和构造中使用名字及计算中以计算对象替换名字 2 程序构造示例 I 2 3如何用名字简化运算组合式的构造 抽象 程序构造示例 II 组合 抽象与构造 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 带有条件的运算组合
7、式 程序与递归 组合 抽象与构造3 程序构造示例 II define squarex xx 名字的定义 定义名字square为一个新的运算 即过程或称函数另一种类型的名字 运算符型的名字 名字的使用 新运算符 即过程名或函数名 形式参数 使用时将被实际参数所替代 过程体 用于表示新运算符的具体计算规则 其为关于形式参数x的一种计算组合 square3 square6 x2 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 3 程序构造示例 II 3 1如何用名字简化运算组合式的构造 抽象 名字的使用 square10 square 28 square square3 square s
8、quare 25 define SumOfSquarexy squarex squarey SumOfSquare34 SumOfSquare34 height x2 y2 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 3 程序构造示例 II 3 2程序构造 组合与抽象 define NewProca SumOfSquare a1 a2 NewProc3 NewProc 31 a 1 2 a 2 2 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 3 程序构造示例 II 3 2程序构造 组合与抽象 NewProc 31 的两种计算过程示意 NewProc 31 New
9、Proc4 SumOfSquare 41 42 SumOfSquare58 Square5 Square8 55 88 2564 89 先求值 再代入 含名字的运算组合式的计算方法 求值 代入 计算 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 3 程序构造示例 II 3 3构造程序的执行 求值 代入与计算 NewProc 31 的两种计算过程示意 NewProc 31 SumOfSquare 31 1 31 2 Square 31 1 Square 31 2 89 31 1 31 1 31 2 31 2 41 41 42 42 55 88 2564 先代入 后求值 代入阶段 求
10、值阶段 含名字的运算组合式的计算方法 代入 求值 计算 命名新运算符和构造中使用新运算符及执行中以过程替换新运算符 3 程序构造示例 II 3 3构造程序的执行 求值 代入与计算 cond define absx cond x0 x x0 0 x0 x 3 程序构造示例 II 3 4有条件的运算如何表达 带有条件的运算组合式 问题1 用前缀表示法书写下述表达式 10 4 8 12 6 4 5 3 6 2 12 7 问题2 请定义一个过程 求某一数值的立方 a3 3 程序构造示例 II 3 5你能表达与构造程序吗 cond define fx cond x0 Squarex x x0 0 x0
11、x Squarex 问题4 请定义一个过程 计算下列函数 3 程序构造示例 II 3 5你能表达与构造程序吗 递归的概念 为什么需要递归 递归能解决什么问题 程序与递归 组合 抽象与构造4 递归的概念 24 递归 Recursion 从前有座山 山里有座庙 庙里有个老和尚 正在给小和尚讲故事呢 故事是什么呢 从前有座山 山里有座庙 庙里有个老和尚 正在给小和尚讲故事呢 故事是什么呢 从前有座山 山里有座庙 庙里有个老和尚 正在给小和尚讲故事呢 故事是什么呢 从前 11 2 3 4 n 怎样在表达中既去掉省略号 而又能表达近乎无限的内容 4 递归的概念4 1为什么需要递归 25 递归的典型视觉形
12、式 自相似性事物的无限重复性构造 4 递归的概念4 2什么情况需要递归 26 递归的典型视觉形式 自相似性事物的无限重复性构造 4 递归的概念4 2什么情况需要递归 27 4 递归的概念4 3如何表达延续不断却相似或重复的事物或过程 数学中的递推式 一个数列的第n项an与该数列的其他一项或多项之间存在某种对应关系 被表达为一种公式 称为递推式 等差数列递推公式a0 5an an 1 3当n 1时 等比数列递推公式a0 5an an 1 20当n 1时 第1项 或前K项 的值是已知的 递推基础 由第n项或前n项计算第n 1项 递推规则 递推步骤 由前向后 可依次计算每一项 等差数列的产生a0 5
13、a1 a0 3 8a2 a1 3 11a3 a2 3 14a4 a3 3 17 28 数学中的数学归纳法 数学归纳法是一种用于证明与自然数有关的命题正确性的证明方法 该方法能用有限的步骤解决无穷对象的论证问题 由归纳基础和归纳步骤构成 假定对一切正整数n 有一个命题P n 若以下证明成立 则P n 为真 1 归纳基础 证明P 1 为真 2 归纳步骤 证明对任意的i 若P i 为真 则P i 1 也为真 证明 1 归纳基础 当n 1时 等式成立即1 1 2 归纳步骤 设对任意k P k 成立 即1 3 5 2K 1 K2 则P K 1 1 3 5 2K 1 2 K 1 1 K2 2K 1 K 1
14、 2 则当P k 成立时P K 1 也成立 根据数学归纳法该命题得证 证毕 求证命题P n 从1开始连续n个奇数之和是n的平方 即公式 1 3 5 2n 1 n2成立 4 递归的概念4 3如何表达延续不断却相似或重复的事物或过程 什么是递归 递归的思想源于数学的递推式和数学归纳法 递归是一种表达相似性对象及动作的无限性构造的方法 递归是一种关于抽象的表达方法 用递归定义无限的相似事物递归是一种算法或程序的构造技术 自身调用自身 高阶调用低阶 构造无限的计算步骤递归是一种典型的计算过程 由后向前代入 再由前向后计算递归递归基础 定义 构造和计算的起点 直接给出 递归步骤 由前n项或第n项定义第n
15、 1项 由低阶f k 且k n 来构造高阶f n 1 执行 由后向前代入 直至代入到递归基础 再由递归基础向后计算直至计算出最终结果 4 递归的概念4 4什么是递归 原始递归 原始递归 复合 组合 与构造 程序与递归 组合 抽象与构造5 原始递归 31 5 原始递归5 1原始递归函数及其递归基础 原始递归函数是接受自然数x或自然数的元组 x1 xn 作为参数 并产生自然数的一个映射 记为f x 或f x1 xn 接受n个参数的函数称作n元函数 处处有定义的函数被称作全函数 未必处处有定义的函数称作半函数或部分函数 最基本的原始递归函数 也被称为本原函数有三个 1 初始函数 0元函数即常数无需计
16、算 或者常数函数 对于每个自然数n和所有的k 有f x1 x2 xK n 2 后继函数 1元后继函数S 它接受一个参数并返回给出参数的后继数 例如S 1 2 S x x 1 其中x为任意自然数 3 投影函数 对于所有n 1和每个1 i n的i n元投影函数Pin 它接受n个参数并返回它们中的第i个参数 即Pin x1 x2 xn xi 32 1 复合 给定原始递归函数f x1 xk 和k个原始递归函数g1 gk 则f和g1 gk的复合是函数h 即h x1 xm f g1 x1 xm gk x1 xm 简单而言 复合是将一系列函数作为参数代入到另一个函数中 又被称为代入 复合是构造新函数的一种方法 复合是表达组合的一种方法 结构fvs 构件g1 gk g1 gk的组合关系fvs 运算组合式g1 gk g1 gk的指令组合关系fvs 基本指令g1 gk 5 原始递归5 2原始递归函数如何构造 组合 复合 33 2 原始递归 给定原始递归函数f和g 则新函数h可由f和g递归的定义 其中h 0 x1 xk f x1 xk h S n x1 xk g h n x1 xk n x1 xk 简单而言
