[计算机软件及应用]算法及其描述ppt课件

1、n各常用算法的概念与设计要点。各常用算法的概念与设计要点。n重点讲授重点讲授应用算法设计求解根本的典型案例，应用算法设计求解根本的典型案例，并通过相关程序，引导设计变通。并通过相关程序，引导设计变通。n在根本案例引导下在根本案例引导下自学自学相关联案例求解。相关联案例求解。n小组讨论小组讨论与根本案例相关的拓展与引申案例求与根本案例相关的拓展与引申案例求解，为解，为“课程设计课程设计作准备。作准备。 培养案例求解兴趣培养案例求解兴趣 自觉完成布置的作业自觉完成布置的作业 加深对算法应用的理解加深对算法应用的理解 擅长变通、拓展与改进擅长变通、拓展与改进 上机环境：上机环境：VC+6.0VC+6

2、.0 上机通过每章指定的案例求解程序与习题上机通过每章指定的案例求解程序与习题 按要求填写实验报告按要求填写实验报告 教学要求教学要求理解理解算法概念、算法特征及算法的描绘算法概念、算法特征及算法的描绘建立建立算法的复杂性概念算法的复杂性概念掌握构造化掌握构造化程序设计程序设计的根本方法的根本方法 本章重点本章重点应用应用 c c 语言描绘算法语言描绘算法掌握算法时间复杂度分析掌握算法时间复杂度分析算法是程序设计的根底，是计算机科学的核心。算法是程序设计的根底，是计算机科学的核心。 1.1.1 1.1.1 算法定义算法定义 算法是计算机解决问题的过程，是解决某一问题算法是计算机解决问题的过程，

3、是解决某一问题的运算序列。或者说算法是的运算序列。或者说算法是问题求解过程的运算问题求解过程的运算描绘描绘。 当面临某一问题时，需要找到用计算机解决这个当面临某一问题时，需要找到用计算机解决这个问题的方法与步骤，算法就是问题的方法与步骤，算法就是解决这个问题的方解决这个问题的方法与步骤的描绘法与步骤的描绘。 算法由操作、控制构造与数据构造算法由操作、控制构造与数据构造三者组成。三者组成。1 1 操作：算术运算，关系运算，逻辑运操作：算术运算，关系运算，逻辑运算；输入、输出、赋值等操作。算；输入、输出、赋值等操作。2 2 控制构造：顺序构造，选择构造，循控制构造：顺序构造，选择构造，循环构造，模

4、块调用。环构造，模块调用。3 3 数据构造：数据之间的逻辑关系。数据构造：数据之间的逻辑关系。 一个算法由有限条可完全机械地执一个算法由有限条可完全机械地执行的、有确定结果的指令组成，具行的、有确定结果的指令组成，具有以下特性：有以下特性： 1 1 确定性确定性 2 2 可行性可行性 3 3 有穷性有穷性 4 4 算法有零个或多个输入算法有零个或多个输入 5 5 算法有一个或多个输出算法有一个或多个输出 1 1一个问题可以设计不同的算法来求解；一个问题可以设计不同的算法来求解； 同一个算法可以采用不同的形式来表述。同一个算法可以采用不同的形式来表述。 2 2描绘算法可以有：描绘算法可以有：自然

5、语言方式、流程图方自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格式、伪代码方式、计算机语言表示方式与表格方式方式等等。 3 3当一个算法使用计算机程序设计语言描绘时，当一个算法使用计算机程序设计语言描绘时，就是程序。就是程序。 本书采用本书采用C C语言与自然语言相结合来描绘算法。语言与自然语言相结合来描绘算法。 1 1 数数 a a 除以除以 b b 得余数得余数 r r；假设；假设r=0r=0，那，那么么b b为所求的最大公约数。为所求的最大公约数。2 2 假设假设 r0r0，以，以b b为为a a，r r为为b b，继续，继续1 1. .欧几里德算法详细描绘如下：欧几里德

6、算法详细描绘如下：inputinputa,ba,b； / / 输入的简单表示输入的简单表示r=a%b;r=a%b;whilewhiler!=0r!=0 / / 施行辗转相除施行辗转相除 a=b; b=r; r=a%b; a=b; b=r; r=a%b; printprintb b; ; / / 输出的简单表示输出的简单表示 1 1 试模拟整数竖式除法：试模拟整数竖式除法：可以证明，可以证明，n n是存在的，且不大于是存在的，且不大于20202020，因此以，因此以上竖式运算总会停顿。当除运算的余数为上竖式运算总会停顿。当除运算的余数为“0 0时，数一数被除数中有多少个时，数一数被除数中有多少个

7、“1 1即可。即可。设整数竖式除法每次试商的被除数为设整数竖式除法每次试商的被除数为a, a, 除数为除数为20202020，每次试商的余数为，每次试商的余数为c c。循环以余数循环以余数c0c0作为循环条件。循环外赋初值：作为循环条件。循环外赋初值：c=1111c=1111，n=4n=4或或c=111c=111，n=3n=3等等。等等。设置竖式除法模拟循环，循环中被除数设置竖式除法模拟循环，循环中被除数a=ca=c* *10+110+1，试商余数，试商余数c=a%2020c=a%2020。假设余数假设余数c=0c=0，完毕循环，输出结果；，完毕循环，输出结果；否那么，计算否那么，计算a=ca

8、=c* *10+110+1为下一轮运算的被除数，为下一轮运算的被除数，继续试商。每商一位，统计被除数中继续试商。每商一位，统计被除数中“1 1的个的个数的变量数的变量n n增增1 1。c=1111;n=4; / c=1111;n=4; / 变量变量c c与与n n赋初值赋初值 whilewhilec!=0c!=0 / / 模拟竖式除法模拟竖式除法 a=c a=c* *10+1;10+1; c=a%2020; c=a%2020; n=n+1; / n=n+1; / 每试商一位每试商一位n n增增1 1 printprintn n; / ; / 输出的简单表示输出的简单表示算法的复杂性越高，所需的

9、计算机资源算法的复杂性越高，所需的计算机资源越多。越多。最重要的计算机资源是时间资源与空间最重要的计算机资源是时间资源与空间资源。资源。 需要计算机时间资源的量称为时间复杂需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间度，需要计算机空间资源的量称为空间复杂度。复杂度。时间复杂度与空间复杂度集中反映算法时间复杂度与空间复杂度集中反映算法的效率。的效率。 要想充分理解算法并有效地应用算法求解实际案要想充分理解算法并有效地应用算法求解实际案例，关键是对算法的分析。通常我们可以利用例，关键是对算法的分析。通常我们可以利用实实验比照方法、数学方法验比照方法、数学方法来分析算法来分析

10、算法。 实验比照分析很简单，两个算法互相比较求解时实验比照分析很简单，两个算法互相比较求解时间间 。 数学方法能在严密的逻辑推理根底上判断算法的数学方法能在严密的逻辑推理根底上判断算法的优劣。优劣。 在算法分析中，我们往往采用能近似表达性能的在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。方法来展示某个算法的性能指标。 一条语句的数量级即执行它的频数，一个算一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。法的数量级是指它所有语句执行频数之和。在分析算法时，隐藏细节的数学表示方法为在分析算法时，隐藏细节的数学表示方法为大写字母大写字母“OO记法

11、，它可以帮助我们简化记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主要成分算法复杂度计算的许多细节，提取主要成分。3 3 for fort=1,k=1;k=n;k+t=1,k=1;k=n;k+n t=t t=t* *2;2;n for forj=1;j=t;j+j=1;j=t;j+n s=s+j; s=s+j; n n例如对给定的例如对给定的n n个整数个整数a a1 1,a,a2 2,a,an n 排序：排序：n forfori=1;i=ni=1;i=n1;i+1;i+n for forj=i+1;j=n;j+j=i+1;jajaiaj h=ai;ai=aj;aj=h; h=ai;a

12、i=aj;aj=h; 算法的空间复杂度是指算法运行的存储空间，是实现算法所需的内存空间的大小。 计算机的一切操作都是由程序控制的，分开了程序，计算机的一切操作都是由程序控制的，分开了程序，计算机将一事无成。从这个意义来说，计算机的本计算机将一事无成。从这个意义来说，计算机的本质是程序的机器，程序是计算机的灵魂。质是程序的机器，程序是计算机的灵魂。 数据构造数据构造 + 算法算法 = 程序程序 例例1-7 编写程序实现求两个整数编写程序实现求两个整数a,bab的最的最大公约数大公约数a,b的欧几里德算法的欧几里德算法 n#include#includenvoid mainvoid mainn l

13、ong a,b,c,r; long a,b,c,r;n scanf scanf%ld,%ld,&a,&b%ld,%ld,&a,&b;/ ;/ 输入整数输入整数a,b a,b n r=a%b; r=a%b;n while whiler!=0r!=0n a=b; b=r; r=a%b; a=b; b=r; r=a%b; n printf printf=%ldn,b=%ldn,b; / ; / 输出求解结输出求解结果果 n n1 自顶向下，逐步求精自顶向下，逐步求精n2 模块化设计模块化设计n3 构造化编码构造化编码 / / 实现欧几里德算法的函数实现欧几里德算法的函数,c135,c