程序：刻画现实世界，解决现实世界中的问题 程序设计语言：实现的工具 算法：问题的解的描述 数据结构：现实世界的数据模型
程序就是在数据的某些特定的表示方式和结构的基 础上对抽象算法的具体表述。一行行代码、语言
1 算法的基本概念
2020/10/11
北京大学
4
算法的定义
设计程序的目的是为了求解问题，为解决一个问题 所采取的方法和步骤，就称为“算法”
2020/10/11
1 算法的基本概念
北京大学
9
算法范化
从N个正整数中找出最大数的通用算法
循环结构
S0: 设Largest为0，当前位置p为0 S1: 若当前数比Largest大，则设Largest为当前数 S2: 若p比N小，则p增加1，并返回S1；否则返回Largest
2020/10/11
2020/10/11
1 算法的基本概念
北京大学
8
算法动作精化
S0: 设Largest为0 S1: 若当前数比Largest大，则设Largest为当前数 S2: 若当前数比Largest大，则设Largest为当前数 S3: 若当前数比Largest大，则设Largest为当前数 S4: 若当前数比Largest大，则设Largest为当前数 S5: 若当前数比Largest大，则设Largest为当前数
17
现实生活中的示例
选择 二选一 条条道路通罗马
如果明天天晴
小明就去郊游
否则
就在家里看书
如果分数达到一本线
录取到一本大学
如果分数达到二本线
录取到二本大学
如果分数达到三本线
录取到三本大学
如果分数达到专科线
录取到专科学校
否则
落榜
2.2 分支结构
2020/10/11
北京大学
顺序执行，每个动作只执行一次， 各动作对执行结果产生的影响是 独立的
动作1 动作2 动作3 … 动作n
动作1 动作2 动作3
… 动作n
2.1 顺序结构
2020/10/11
北京大学
15
现实生活中的示例
按部就班 先来后到 循序渐进 接连不断
起床 刷牙 吃早饭 上课 吃中饭 午休 上课 吃晚饭 晚自习 洗漱 睡觉
算法是一个由一组严格定义的动作组成的过程，给 定一个出始状态，这个过程能够结束在一个确定终 止状态。
大多数算法都可以用程序实现。 常用算法一般都被实现为算法库，供程序员调用。
2020/10/11
1 算法的基本概念
北京大学
5
算法的基本思想
如何把大象关在冰箱里?
分3步：
第一步：打开冰箱门; 第二步：把大象推进冰箱; 第三步：关上冰箱门;
1 算法的基本概念
2020/10/11
北京大学
12
不了解施加于数据上的算法就无法决定如 何构造数据；反之，算法的结构和选择却 常常在很大程度上依赖于作为基础的数据 结构。简而言之，程序的构成（算法） 与数据结构是两个不可分割地联系在一 起的问题。
2020/10/11
1 算法的基本概念
北京大学
13
程序设计就是要告诉计算机如何进行计算 的。这与我们中学时代的数学解题过程是 一样的，只不过描述的手段有所变化而已。
2020/10/11
1 算法的基本概念
北京大学
3
1984年图灵奖获得者瑞士科学家尼克劳斯·沃斯（Niklaus Wirth，Pascal语言的发明者和结构化程序设计创始者）1976 年出版了《算法+数据结构 = 程序设计》一书，提出了著名 的公式：“程序 ＝ 数据结构 ＋ 算法” 。
一个实例：找出一组正整数中的最大的数
2020/10/11
1 算法的基本概念
北京大学
7
逐步求解，定义算法的动作
S1: 设Largest为第一个数 S2: 若第二个数比Largest大，则设Largest为第二个数 S3: 若第三个数比Largest大，则设Largest为第三个数 S4: 若第四个数比Largest大，则设Largest为第四个数 S5: 若第五个数比Largest大，则设Largest为第五个数
内结束，并给出明确的计算结果。 离散性：算法的输入数据及输出数据都应是离散的符号。
1 算法的基本概念
2020/10/11
北京大学
11
算法的基本要求
正确 易维护（可读，易修改） 方便使用空间复杂度低 算法的效率可以测试，用大量输入数据测量运行的时间和 占用的内存，通过比较判别和选择效率高的算法。 更重要的是可以在编程前进行分析和估计（算法分析）， 即理论的计算，给出事前的判断。高斯，查字典
2.1 顺序结构
2020/10/11
北京大学
16
分支结构：根据条件判
断执行什么动作（序列），
最多只有一个动作（序列）
被执行
是 条件成立？ 否
如果 条件成立 则
动作（或动作序列）1
否则
动作（或动作序列） 2
分支结束
动作（序列）1 动作（序列）2
2.2 分支结构
2020/10/11
北京大学
1 算法的基本概念
北京大学
10
算法的基本性质
通用性：即适用于某一类问题中的所有个体，而不只是用 来解决一个具体的问题。
有效性：即应有明确的步骤一步一步地引导计算的进行。 确定性：即每个步骤都是机械的、有明确定义的动作，不
需要计算者临时动脑筋。 有限性：对满足算法要求的输入数据，算法应在有限多步
18
循环结构：重复执行
一系列动作
当 条件成立 做
动作1 动作2 … 动作n
循环结束处
第七讲 算法
北京大学信息学院 2013年10月
了解算法的基本概念 掌握描述算法的三种基本结构 学会算法的流程图描述 介绍几种基本算法
难、有意思、数学、编程的基础
主要内容
2020/10/11
北京大学
2
计算机是一个计算工具，它本身不能主动 帮助我们做任何事情，需要我们告诉它如 何进行计算。
计算机科学家已经证明，只使用如下三种 结构，就可以描述任何算法，且算法结构 优良
顺序结构（Sequence） 分支结构（Decision） 循环结构（Repetition）
每一种基本结构分别只有一个入口和一个 出口
2 描述算法的三种基本结构
2020/10/11
北京大学
14
顺序结构：动作（语句）序列，