大学计算机第3讲-程序与递归-组合-抽象与构造.ppt

### 大学计算机课程第三讲知识点总结 #### 标题：大学计算机第3讲-程序与递归-组合-抽象与构造 #### 描述：大学计算机第3讲-程序与递归-组合-抽象与构造 #### 标签：无 #### 部分内容概述： 本次课程主要围绕着“程序与递归”的主题展开讨论，具体涉及到了如何通过组合基本动作、抽象以及构造来设计和实现一个系统。此外，还深入探讨了递归的概念以及其在构建复杂结构中的应用。 --- ### 知识点详解 #### 一、程序—组合、抽象与构造 **1.1 如何设计并实现一个系统** 在设计和实现一个基本计算系统时，我们首先需要了解的是所有高级的运算（如加减乘除）都可以简化为最基本的加法运算，进而这些加法运算又可以通过逻辑运算来实现。更进一步地，基本的逻辑运算（如与、或、非、异或等）可以通过简单的电子门电路来实现。基于这样的认识，我们可以按照以下步骤来设计和实现一个基本的计算系统： 1. **定义基本动作**：比如定义“与”、“或”、“非”、“异或”等基本逻辑操作。 2. **复杂动作的实现**：通过组合这些基本的动作来实现更为复杂的逻辑功能。 3. **指令与程序**：为了控制这些基本动作的执行顺序，我们需要定义指令，并将这些指令组合成程序，以便系统能够按一定的顺序执行这些动作。 **1.2 什么是程序？什么是组合？** - **程序**是由一系列指令组成的，这些指令控制基本动作的执行顺序，从而实现特定的功能。 - **组合**是指将不同的基本动作以某种方式排列组合，形成更为复杂的动作或者功能。例如，将“与”、“或”、“非”等逻辑运算组合在一起，可以实现复杂的逻辑判断。 **1.3 怎样表达程序？** - **程序的构造方法**：程序可以通过不同的构造方法来表达。常见的有两种：中缀表示法和前缀表示法。 - **中缀表示法**：运算符位于两个操作数之间，例如 `(a + b)`。 - **前缀表示法**：运算符位于操作数之前，例如 `(+ a b)`。前缀表示法更容易扩展到多个操作数的情况，例如 `(+ 100 205 300 400)` 表示的是四个数相加。 **1.4 组合的嵌套及其计算过程** - **组合的嵌套**：在程序中，我们可以将多个简单的组合嵌套起来形成更为复杂的表达式。例如 `(+ 100 (- 200 50))` 表示先计算括号内的差，再与100相加。 #### 二、递归 递归是一种重要的编程技巧，它允许我们使用有限的代码来处理无限或极其复杂的问题。递归通常涉及到两个关键部分： 1. **基本情况**（Base Case）：递归终止的条件，确保递归最终能够停止。 2. **递归步骤**（Recursive Step）：将问题分解为更小的部分，并对这些子问题应用相同的算法。 ### 小结 本节课重点介绍了程序设计的基础概念，包括如何通过基本动作的组合、抽象和构造来设计和实现一个系统。此外，还介绍了递归的概念及其在程序设计中的应用。理解这些基础理论对于学习计算机科学和编程至关重要。