第10章 程序设计基础

Ø
Ø Ø
Ø
10.2.3 算法的评价
算法评价标准 Ø 正确性 运行结果正确 Ø 可读性 指算法的简单性 Ø 通用性 适用一类问题的求解 Ø 高效率 时间与空间 算法效率的度量 Ø 时间度量：执行一种简单操作所需的平均时间与 进行简单操作的次数的乘积。通常把算法中包含 简单操作的次数的多少称为算法的时间复杂度 。 Ø 空间度量：主要考虑在算法运行过程中临时占用 的存储空间，称为算法的空间复杂度。
例10­2 算法：
1) 输入一个数，放在存储单元max中。 2) 设置用来统计比较次数的单元i，初始值为1。 3) 若i<=9，做第4）步，否则做第8）步。 4) 输入一个数，放在存储单元x中。 5) 比较max和x中的数，若x>max，则将x的值送给 max，否则，max值不变。 6) i增加1。 7) 返回到第3）步。 8) 输出max中的数，此时max中的数就是10个数中 最大的数
10.4 程序设计方法
随着计算机技术的不断发展，人们对程序设计方 法的研究也在不断深入。早期程序设计的好坏常 以运行速度快、占用内存少为主要标准，然而在 计算机的运算速度大大提高，存储容量不断扩大 的情况下，程序具有良好的结构成为第一要求， 一个结构良好的程序虽然在效率上不一定最好， 但结构清晰，易于阅读和理解，便于验证其正确 性。当前程序设计的主要方法有结构化程序设计 和面向对象的程序设计
10.2.2 算法的特性
Ø
有穷性：算法中执行的步骤总是有限次数的，不能 无止境地执行下去。 确定性：算法中的每一步操作必须具有确切的含 义，不能有二义性。 有效性：算法中的每一步操作必须是可执行的。 输入：算法中操作的对象是数据，因此应提供有关 数据。 输出：一个算法要有输出，以反映输入数据加工后 的结果，没有输出的算法是毫无意义的。
2．汇编语言（Assembly language）
汇编语言：用助记符表示的机器指令。 特点：直观性增强了，但与机器指令一一对应。
3．高级语言（High level language）
高级语言：接近自然语言和数学表达式的一种语言。 特点：直观、通用性，便于推广交流。 两种执行方式：编译方式和解释方式。
冒泡排序示意
4．查找算法 查找是根据给定的某个值，在表中查找等于给定 值的数据元素，若表中存在这样的数据元素，称 此查找是成功的。若表中不存在关键字等于给定 值的数据元素，称此查找是不成功的。 顺序查找 顺序查找是最常用的查找方法，其查找过程为： 从第一个元素起，逐个将给定值与数据元素的关 键字进行比较，若某个元素的关键字与给定值相 等，则认为查找是成功的，否则，查找失败。
模 块 2­1
模 块 2­2
模 块 2­3
模 块 2­2­1
模 块 2­2­2
10.4.2 面向对象程序设计
n
传统的程序设计是基于求解过程来组织程序流程，将 问题分解为过程。在这类程序中，以对数据进行操作 的过程作为程序的主体，数据和施加于数据的操作是 独立设计的。扩展性和重用性差。 面向对象程序设计将问题分解为对象，以对象作为程 序的主体。对象是数据和操作的“封装体”，封装在对 象内的程序通过“消息”来驱动运行。在图形用户界面 上，消息可通过键盘或鼠标的某种操作来传递。
Ø
Ø
10.2 算 法
10.2.1 算法的概念 计算机解决问题的方法和步骤，是一组明确的可 以执行的步骤的有序集合。
算法举例：
例10­1：欧几里德（Euclid）算法求两个正整数m 和n的最大公约数。 例10­2 输入10个数，要求找出其中最大的数。
例10­1 算法（辗转相除法） 步骤如下： 1）比较m和n的大小，把大数放在m，把 小数放在n中； 2）用m除以n，余数存于r；若r等于0，则 n就是最大公约数，输出n； 3）否则，将n赋值给m，r赋值给n，返回 到第2步。
（1）对象(Object) 指现实世界中客观存在的事物。 对象的静态特性：属性（包括自己特有的属性和同类对象 的共同属性） 。属性反映了对象自身特征； 对象的动态特性：行为。行为通过方法和事件来表达，事 件指发生在对象上的动作，或者对对象所做的操作，方法 指对象所固有的完成某种任务的功能，与事件过程类似， 都是为了完成某个任务。 一个对象是属性和行为的封装体。 （2） 类(Class) 是具有相同属性和方法的一组对象的集合，它为属于该类 的全部对象提供了统一的抽象描述。类是创建对象实例的 模板，而对象是类的一个实例。。
第10 章 程序设计基础 10
10.1 程序设计的概念 10.2 算法 10.3 程序设计语言 10.4 程序设计方法
10.1 程序设计的概念
程序：指计算机完成特定功能的指令的集合，是解 题方法和步骤的描述。主要描述两部分问题：描述 问题的每个对象和对象之间的关系及对对象的处理 规则。 程序的核心：数据结构和算法。 程序设计（Programming）：先对问题进行分析并建 立数学模型（对数值计算问题）或提出对数据处理 的需求（对非数据计算问题），然后进行算法的设 计，并用某一种程序设计语言编写程序，最后调试 程序，使之运行后能产生预期的结果。
n
r m
n
m除以n，得余数r
顺序结构：由若干个前后衔接的矩形块顺序组成，依
次顺序执行不同的程序块，是最简单的基本结构。
A
流程图
B
选择结构：在此结构内有两个分支，它表示当给定的
条件P满足时执行A块的操作，否则执行B块的操作
真 P A
假
B
流程图
P
假
当型循环结构
真 A
A
直到型循环结构
10.2.4 算法的描述 常用流程图、N­S图、伪代码等 1. 用传统的流程图描述算法：通过流程线、几何图形、 文字说明来描述算法。 2. 用N­S图描述算法 Ø 程序的三种基本结构：顺序结构、选择结构和循环 结构。 Ø 结构化流程图（N­S图） 3. 用伪代码描述算法：伪代码是介于自然语言和高级语 言之间的一种文字和符号描述工具，它不涉及图形， 而是结合某种高级语言一行一行、自上而下描述算法。
使用二分查找法，查找出John
10.3 程序设计语言
10.3.1
言语器机
程序设计语言的分类
言语编汇 言语级高
面向过程 面向对象
10.3.1 程序设计语言的分类 1．机器语言（Machine language）
机器语言：计算机系统可以直接识别的指令集合，由二进制代 码组成，是计算机可直接识别和执行的“语言” 。 特点：繁琐冗长、不直观、容易出错、程序不通用。
折半查找
基本思想：如果查找表中的数 据元素按关键字有序排序，则 在查找时不必逐个顺序比较， 而采用跳跃的方式：首先与“中 间位置”的元素比较，若相等则 查找成功；若给定值大于“中间 位置”的元素值，则在后半部继 续进行折半查找；否则在前半 部进行折半查找。当在长度为n 的表中使用折半查找法查找 时，最差情况下的查找长度不 超过log n。 2
Байду номын сангаас
3．排序算法 所谓排序，就是将一组数据元素按照某个关键字递增或递减 的次序排列起来。 选择排序实现过程：首先找出表中关键字最小的元素，将其 与第一个元素进行交换，然后，再在其余元素中找出关键字 最小的元素，将其与第二个元素进行交换。依次类推，直到 将表中所有关键字按由小到大的顺序排列好为止。
选择排序示意
高级语言程序的编译执行过程：
编译程序工作过程:
10.3.2 高级语言的基本特征
1．数据类型 各种高级语言都提供了丰富的数据类型，这些数据类型可以 分为两大类：简单类型和构造类型。其中简单类型一般有整 型、实型、字符型、逻辑型等，构造类型有数组类型、集合 类型、记录类型、指针类型、文件类型等。 2．运算与表达式 （1）常量 （2）变量 （3）表达式 3．语句
（1）赋值语句 （2）输入输出语句 （3）程序的控制结构语句
4．子程序、函数与过程
它们是高级语言中提供的实现模块化程序设计和简化程序代码 的途径，用来完成某一特定的功能。
10.3.3 常用高级语言
1. 传统高级语言 （1）FORTRAN语言：FORTRAN 66、FORTRAN 77、FORTRAN 90 （2）BASIC语言：BASIC、Visual Basic、Visual 。 （3）PASCAL语言 （4）C语言：C、C++、C＃ （5）COBOL语言 2．网络编程语言 （1）Java语言：简单易学、面向对象、平台无关、分布式、 可靠安全等特点网络编程语言。 （2）脚本语言（Scripting Language）：服务器脚本 （JavaScript、VBScript、Perl、PHP）和客户端脚本 （JavaScript、VBScript） 。 3．科学计算语言：MATLAB 讨论：如何学习一种高级语言？如何选择高级语言？
假
P 真
用VB伪代码描述求任意10个数中的最大数的算法 把第一个值送给Max 1→I While i≤9 {把下一个值送给x if x≥max x→max endif i+1→i } Print max
10.2.5 算法示例
1．迭代算法 迭代是一种建立在循环基础上的算法。在数学中，迭代 经常被用来进行数值计算，例如求方程的解，不断用变 量原来的值递推求新的值的过程。 例如：求若干个数之和或乘积的问题。 2．穷举算法 穷举法也叫枚举法，它的基本思路是对众多可能解，按 某种顺序进行逐一枚举和检验，并从中找出那些符合要 求的可能解，作为问题的解。穷举的计算量是相当大 的，但对于计算机来说，做起来很容易。穷举算法是一 种重要的算法设计策略，可以说是计算机解题的一大特 点。 例如：求方程x+2y+5z=100的整数解。
程序设计的基本步骤：
Ø
分析问题，确定数学模型或方法。 明确要准备解 决的问题，确定好编程目标，定义好需要输入的 数据和想要得到的输出结果。 设计算法，画出流程图。 选择编程工具，按算法编写程序。 调试程序，分析输出结果。