1、* 北京大学 1上堂课的主要内容n 程序设计语言（也被称为 “编程语言 ”，Programming Language）是人们 描述（编制） 程序 所使用的规范和方法（ 语言）。n 机器语言n 汇编语言n 高级语言第六讲 算法设计北京大学 信息科学技术学院* 北京大学 3主要内容n 了解算法的基本概念n 掌握描述算法的三种基本结构n 学会算法的流程图描述n 介绍几种基本算法* 北京大学 41 算法的基本概念n 计算机只是一个计算工具，它本身不能主动帮助我们做任何事情，需要我们告诉它如何进行计算。n 程序设计 就是要告诉计算机如何进行计算的。这与我们中学时代的数学解题过程是一样的，只不过描述的手段
2、有所变化而已。* 北京大学 51 算法的基本概念n 1984年图灵奖获得者 瑞士科学家 尼克劳斯 沃斯 （ Niklaus Wirth， Pascal语言的发明者和结构化程序设计创始者） 1976年出版了 算法 +数据结构 = 程序设计 一书，提出了著名的公式： “程序 数据结构 算法 ” 。n 程序：刻画现实世界，解决现实世界中的问题n 程序设计语言：实现的工具n 算法：问题的解的描述n 数据结构：现实世界的数据模型n 程序就是在 数据的某些特定的表示方式和结构 的基础上对抽象算法 的具体表述。* 北京大学 61 算法的基本概念n 算法的定义n 设计程序的目的是为了求解问题，为解决一个问题所
3、采取的方法和步骤，就称为 “算法 ”n 算法是 一个由一组严格定义的指令组成的过程 ，给定一个出始状态，这个过程能够结束在一个确定终止状态。n 大多数算法都可以用程序实现。n 常用算法一般都被实现为算法库，供程序员调用。* 北京大学 71 算法的基本概念一个实例：找出一组 正整数 中的最大的数* 北京大学 81 算法的基本概念n 逐步求解，定义算法的动作n S1: 设 Largest为第一个数n S2: 若第二个数比 Largest大，则设 Largest为第二个数n S3: 若第三个数比 Largest大，则设 Largest为第三个数n S4: 若第四个数比 Largest大，则设 Lar
4、gest为第四个数n S5: 若第五个数比 Largest大，则设 Largest为第五个数* 北京大学 91 算法的基本概念n 算法动作精化n S0: 设 Largest为 0n S1: 若 当前数 比 Largest大，则设 Largest为 当前数n S2: 若 当前数 比 Largest大，则设 Largest为 当前数n S3: 若 当前数 比 Largest大，则设 Largest为 当前数n S4: 若 当前数 比 Largest大，则设 Largest为 当前数n S5: 若 当前数 比 Largest大，则设 Largest为 当前数* 北京大学 101 算法的基本概念n 算法范化从 N个正整数中找出最大数的通用算法n S0: 设 Largest为 0，当前位置 p为 0n S1: 若当前数比 Largest大，则设 Largest为当前数n S2: 若 p比 N小，则 p增加 1，返回 S1，否则返回 Largest
