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

-,1,计算机常用算法与程序设计案例教程,杨克昌,请用PowerPoint2003播放,-,2,课堂讲授：,学时安排：36（讲授）18（上机）(可根据实际教学计划进行调整),各常用算法的概念与设计要点。重点讲授应用算法设计求解基本的典型案例，并通过相关程序，引导设计变通。在基本案例引导下自学相关联案例求解。小组讨论与基本案例相关的拓展与引申案例求解，为“课程设计”作准备。,-,3,上机实践：,学习建议：,学会归纳、总结和提炼；,自觉调整学习状态：,培养案例求解兴趣自觉完成布置的作业加深对算法应用的理解善于变通、拓展与改进,注重算法设计，提高解决实际案例的能力。,上机环境：VC+6.0上机通过每章指定的案例求解程序与习题按要求填写实验报告,-,4,教学要求了解算法概念、算法特征及算法的描述建立算法的复杂性概念掌握结构化程序设计的基本方法本章重点应用c语言描述算法掌握算法时间复杂度分析,算法与程序设计概述,-,5,1.1算法及其描述,算法是程序设计的基础，是计算机科学的核心。1.1.1算法定义算法是计算机解决问题的过程，是解决某一问题的运算序列。或者说算法是问题求解过程的运算描述。当面临某一问题时，需要找到用计算机解决这个问题的方法与步骤，算法就是解决这个问题的方法与步骤的描述。,-,6,1.算法的三要素,算法由操作、控制结构与数据结构三者组成。(1)操作：算术运算，关系运算，逻辑运算；输入、输出、赋值等操作。(2)控制结构：顺序结构，选择结构，循环结构，模块调用。(3)数据结构：数据之间的逻辑关系。,-,7,2.算法的基本特征,一个算法由有限条可完全机械地执行的、有确定结果的指令组成，具有以下特性：(1)确定性(2)可行性(3)有穷性(4)算法有零个或多个输入(5)算法有一个或多个输出,-,8,1.1.2算法描述,（1）一个问题可以设计不同的算法来求解；同一个算法可以采用不同的形式来表述。（2）描述算法可以有：自然语言方式、流程图方式、伪代码方式、计算机语言表示方式与表格方式等。（3）当一个算法使用计算机程序设计语言描述时，就是程序。本书采用C语言与自然语言相结合来描述算法。,-,9,例1-1求两个整数a,b的最大公约数的欧几里德算法,(1)数a除以b得余数r；若r=0，则b为所求的最大公约数。(2)若r0，以b为a，r为b，继续(1).欧几里德算法具体描述如下：input(a,b)；/输入的简略表示r=a%b;while(r!=0)/实施辗转相除a=b;b=r;r=a%b;print(b);/输出的简略表示,-,10,例1-2由n个1组成的整数能被2011整除，求n至少为多大？,(1)试模拟整数竖式除法：,-,11,可以证明，n是存在的，且不大于2011，因而以上竖式运算总会停止。当除运算的余数为“0”时，数一数被除数中有多少个“1”即可。设整数竖式除法每次试商的被除数为a,除数为2011，每次试商的余数为c。循环以余数c0作为循环条件。循环外赋初值：c=1111，n=4或c=111，n=3等等。设置竖式除法模拟循环，循环中被除数a=c*10+1，试商余数c=a%2011。若余数c=0，结束循环，输出结果；否则，计算a=c*10+1为下一轮运算的被除数，继续试商。每商一位，统计被除数中“1”的个数的变量n增1。,-,12,(2)竖式除法模拟描述,c=1111;n=4;/变量c与n赋初值while(c!=0)/模拟竖式除法a=c*10+1;c=a%2011;n=n+1;/每试商一位n增1print(n);/输出的简略表示,-,13,1.2算法的复杂性分析,算法的复杂性越高，所需的计算机资源越多。最重要的计算机资源是时间资源与空间资源。需要计算机时间资源的量称为时间复杂度，需要计算机空间资源的量称为空间复杂度。时间复杂度与空间复杂度集中反映算法的效率。,-,14,1.2.1时间复杂度,要想充分理解算法并有效地应用算法求解实际案例，关键是对算法的分析。通常我们可以利用实验对比方法、数学方法来分析算法。实验对比分析很简单，两个算法相互比较求解时间。数学方法能在严密的逻辑推理基础上判断算法的优劣。在算法分析中，我们往往采用能近似表达性能的方法来展示某个算法的性能指标。,-,15,一个算法的时间复杂度是指算法运行所需的时间。一个算法的运行时间取决于算法所需执行的语句（运算）的多少。算法的时间复杂度通常用该算法执行的总语句（运算）的数量级决定。,一条语句的数量级即执行它的频数，一个算法的数量级是指它所有语句执行频数之和。在分析算法时，隐藏细节的数学表示方法为大写字母“O”记法，它可以帮助我们简化算法复杂度计算的许多细节，提取主要成分。,-,16,算法的执行频数的数量级直接决定算法的时间复杂度。,-,17,2个语句各执行1次，共执行2次。时间复杂度为O(1),(1)x=x+1;s=s+x;,例1-3试计算下面三个程序段的时间复杂度,(2)for(k=1;k=n;k+)x=x+y;y=x+y;s=x+y;,“k=1”执行1次；“k=n”与“k+”各执行n次；3个赋值语句，每个赋值语句各执行n次；共执行5n+1次.时间复杂度为O(n).,-,18,例1-3试计算下面三个程序段的执行频数,(3)for(t=1,k=1;k=n;k+)t=t*2;for(j=1;j=t;j+)s=s+j;,“t=1”与“k=1”各执行1次；“k=n”与“k+”各执行n次；“t=t*2”执行n次；“j=1”执行n次；“j=t”、“j+”与内循环的赋值语句“s=s+j”各执行频数为:总的执行频数为：,-,19,时间复杂度符号O的两个定理:,-,20,在估算算法的时间复杂度时，为简单计，以后只考虑内循环语句的执行频数，而不细致计算各循环设计语句及其它语句的执行次数，这样简化处理不影响算法的时间复杂度。,例1-4估算以下程序段所代表算法的时间复杂度。for(k=1;k=n;k+)for(j=1;jb)的最大公约数(a,b)的欧几里德算法,#includevoidmain()longa,b,c,r;scanf(%ld,%ld,/输出求解结果,-,28,1.3.2结构化程序设计,任何简单或复杂的算法都可以由顺序结构、选择结构和循环结构这三种基本结构组合而成。所以，顺序结构、选择结构和循环结构被称为程序设计的三种基本结构，也是结构化程序设计必须采用的结构。,结构化程序设计方法是目前国内外普遍采用的一种程序设计方法。结构化程序设计方法在实践中不断发展和完善，已成为软件开发的重要方法讨论。,-,29,结构化程序设计的基本要点:,（1）自顶向下，逐步求精（2）模块化设计（3）结构化编码,逐步求精总是和自顶向下结合使用，将问题求解逐步具体化的过程，一般把逐步求精看作自顶向下设计的具体体现。,-,30,模块化是结构化程序设计的重要原则。一个程序是由一个主控模块和若干子模块组成。主控模块用来完成某些公用操作及功能选择;而子模块用来完成某项特定的功能。,-,31,例1-8把欧几里德算法设计成子模块，通过主模块调用实现求n个整数的最大公约数。,/实现欧几里德算法的函数,c135（可加c135在VC+6.0的链接）,/求n个整数的最大公约数,c136(调用c135,可加c136在VC+6.0的链接),-,32,在设计好一个结构化的算法之后，还需进行结构化编码，将已设计好的算法用计算机语言来表示，编写出能在计算机上进行编译与运行的程序。结构化程序设计的过程就是将问题求解由抽象逐步具体化的过程。这种方法符合人们解决复杂问题的普遍规律，可以提高程序设计的质量和效率。,-,33,第1章作业,习题1:1,2,3,4