《算法设计与分析》第01章课件

1、平时要求：平时要求： 按时上下课、勤动脑动手，有事请提前与辅导员请假；按时上下课、勤动脑动手，有事请提前与辅导员请假；考试成绩：考试成绩： 平时表现（考勤、随堂提问、作业等）：平时表现（考勤、随堂提问、作业等）：20%20% 实验（纸版和电子版）：实验（纸版和电子版）：10%10% 课堂测验（三至四次）：课堂测验（三至四次）：20%20% 期末考试（开卷）：期末考试（开卷）：50%50%（注意：无故缺勤超过（注意：无故缺勤超过6 6学时学时(3(3次次) )以上以上取消本课程考试资取消本课程考试资格，直接进入重修；）格，直接进入重修；）学习安排学习安排: :讲练结合讲练结合理论课时间：理论课时

2、间：第一至十四周第一至十四周算法设计与分析算法设计与分析(24+8(24+8或或28+4)28+4) Design and Analysis of Algorithms Design and Analysis of Algorithms 程序设计语言程序设计语言C+C+或或C C或或JavaJava，数据结构数据结构算法设计与分析算法设计与分析王晓东编著，电子工业出版社王晓东编著，电子工业出版社算法设计与分析算法设计与分析陈慧南编著，电子工业出版社陈慧南编著，电子工业出版社（algorithm）算法是一组明确的、有序的、可以执行的算法是一组明确的、有序的、可以执行的步骤步骤集合集合。 并具有以

3、下并具有以下5 5个特征个特征: :F 有穷性有穷性F 确切性确切性F 有有0 0个或多个输入个或多个输入F 有有1 1个或多个输出个或多个输出F 有效性（可行性）有效性（可行性）一个算法必须保证执行有一个算法必须保证执行有限步之后结束限步之后结束算法的每一步骤必须算法的每一步骤必须有确切的定义有确切的定义描述运算对象的初始情况，描述运算对象的初始情况，所谓所谓0个输入是指算法本个输入是指算法本身给出了初始条件。身给出了初始条件。一个算法有一个或多个输一个算法有一个或多个输出，以反映对输入数据的出，以反映对输入数据的加工的结果。加工的结果。算法能精确有效地运行。算法能精确有效地运行。 算法算法

4、在描述上一般使用在描述上一般使用半形式化半形式化的语言，而的语言，而程程序序是用是用形式化形式化的计算机语言描述的；的计算机语言描述的； 算法算法对问题求解过程的描述可以比程序对问题求解过程的描述可以比程序粗略粗略，算法经过算法经过细化细化以后可以得到计算机以后可以得到计算机程序程序。 一个计算机程序是一个算法的计算机语言表述，一个计算机程序是一个算法的计算机语言表述，而执行一个程序就是执行一个用计算机语言表而执行一个程序就是执行一个用计算机语言表述的算法。述的算法。 算法是计算机科学的算法是计算机科学的基础基础，更是程序的，更是程序的基基石石，只有具有良好的算法基础才能成为训练，只有具有良好

5、的算法基础才能成为训练有素的软件人才。有素的软件人才。 算法的基本结构算法的基本结构 用自然语言表示用自然语言表示 用流程图表示用流程图表示 用用N-SN-S流程图表示流程图表示 用伪代码表示用伪代码表示 用计算机语言表示用计算机语言表示ABBAPPA顺序结构选择结构循环结构算法的三种主要结构算法的三种主要结构当型循环当型循环直到型循环直到型循环算法的基本结构算法的基本结构PA流程图是通过箭头相互连接的几何图形流程图是通过箭头相互连接的几何图形来表达的方法。来表达的方法。 流程图流程图ANSI规规定的一些定的一些常用流程常用流程图符号。图符号。输入输出框输入输出框起止框起止框判断框判断框处理框

6、处理框流程线流程线N-SN-S流程图流程图是一种流程图形式，在这种流程图中完全去是一种流程图形式，在这种流程图中完全去掉了流程线，全部算法写在一个矩形框内。掉了流程线，全部算法写在一个矩形框内。顺序结构选择结构循环结构ABNoABPYesWhile P1AUntil P2A伪代码伪代码 伪代码是一种描述语言。伪代码是一种描述语言。 它只是一种描述程序执行过程的工具，是它只是一种描述程序执行过程的工具，是面向读者的，面向读者的，不能直接不能直接用于计算机，实际使用于计算机，实际使用时还需转换成某种计算机语言来表示。用时还需转换成某种计算机语言来表示。 n 伪码是一种在程序设计过程中表达想法的伪码

7、是一种在程序设计过程中表达想法的非正式的符号系统。非正式的符号系统。StartSum = 0n=1while n10 sum=sum+n n=n+1print sumend流程图即通过箭头相互连接的流程图即通过箭头相互连接的几何图形的表达方法几何图形的表达方法伪码是一种在程序伪码是一种在程序设计过程中表达想设计过程中表达想法的非正式的符号法的非正式的符号系统系统l 用自然语言描述用自然语言描述l 用流程图表示用流程图表示l 用用N-SN-S图表示图表示l 用伪码表示用伪码表示l 用用C C语言表示语言表示例例 用用 y = x2-2x+3 计算计算 当当 x=0,1,2,3,4,5 所对应的所

8、对应的y值值1. 置置x的下界为的下界为 0；2. 置置x的上界为的上界为 n=5；3. 当当xn时，重复执行如下三时，重复执行如下三 步，步， 否则算法停止。否则算法停止。F 用公式计算用公式计算y值值F 输出一组输出一组x和和y的值的值F x值增加值增加1l 用自然语言描述用自然语言描述l 用流程图描述用流程图描述开开 始始0 x5 nx n ?y = x2-2x+3输出：输出：x与与y值值增值：增值：x=x+1结结 束束YNl 用N-S图描述 0 x 5 n x=n 计算：计算： y = x2-2x+3 打印：打印： x与与y值值 增值：增值：x=x+1 l 用伪码描述startx=0n

9、 = 5while x=n y=x*x-2*x+3 print x,y x=x+1endl 用C语言描述#include main() int x, y, n; x=0; n=5; while( x = n) y=x*x-2*x+3; printf(%d %dn, x, y); x=x+1; problem solvingproblem solving）是寻找一种方法来）是寻找一种方法来实现目标。实现目标。计算机求解问题的关键之一是寻找一种计算机求解问题的关键之一是寻找一种（problem solving strategyproblem solving strategy），得到求解问题），得到

10、求解问题的算法，从而得到问题的解。的算法，从而得到问题的解。一般情况一般情况, ,问题求解过程包括问题求解过程包括: : 一个计算机程序的开发过程就是使用计算机求一个计算机程序的开发过程就是使用计算机求解问题的过程。解问题的过程。（software engineering software engineering ）将软件开）将软件开发和维护过程分成若干阶段，称为发和维护过程分成若干阶段，称为（system life cyclesystem life cycle）或）或划分为划分为: : 分析分析（analysisanalysis） 设计设计（designdesign） 编码编码（coding

11、 or programmingcoding or programming） 测试测试（testingtesting） 维护维护（maintenancemaintenance）等等5 5个阶段。个阶段。开发期开发期运行期运行期 算法分类算法分类一个一个（exact algorithmexact algorithm）总能保证求）总能保证求得问题的解。得问题的解。一个一个（heuristic algorithmheuristic algorithm）通过）通过使用某种规则、简化或智能猜测来减少问题求解使用某种规则、简化或智能猜测来减少问题求解时间。时间。 对于对于最优化最优化问题，一个算法如果致力于

12、寻问题，一个算法如果致力于寻找近似解而不是最优解，被称为找近似解而不是最优解，被称为（approximation algorithmapproximation algorithm）。）。 如果在算法中需做出某些如果在算法中需做出某些随机随机选择，则称选择，则称为为（randomized algorithmrandomized algorithm）。）。 确认一个算法是否正确的活动称为确认一个算法是否正确的活动称为（algorithm validationalgorithm validation）。）。使用数学方法证明算法的正确性，称为使用数学方法证明算法的正确性，称为（algorithm pr

13、oofalgorithm proof）。）。（program testingprogram testing）是指对程序模块或）是指对程序模块或程序总体，输入事先准备好的样本数据（称为程序总体，输入事先准备好的样本数据（称为，test casetest case），检查该程序的输出，来发现），检查该程序的输出，来发现程序存在的错误及判定程序是否满足其设计要求的程序存在的错误及判定程序是否满足其设计要求的一项积极活动。一项积极活动。（algorithm analysisalgorithm analysis）活动是指）活动是指对算法的执行时间和所需空间的估算。对算法的执行时间和所需空间的估算。当然在算法写成程序后，便可使用样本数据，当然在算法写成程序后，便可使用样本数据，实际测量一个程序所消耗的时间和空间，这称实际测量一个程序所消耗的时间和空间，这称为 程 序 的为 程 序 的（ p e r f o r m a n c e p e r f o r m a n c e measurementmeasurement）。）。实验题目 求两个自然数m和n的最大公约数。实验目的 1.复习数据结构课