算法设计基础.pptx

第第2 2章章 算法设计基础算法设计基础2.1 算法的描述算法的描述2.2 结构化算法设计初步结构化算法设计初步2.3 算法的计算复杂性算法的计算复杂性2.4 常用算法设计策略常用算法设计策略 学习目的：学习目的：掌握算法的流程图和掌握算法的流程图和PADPAD图描述方式；图描述方式；初步掌握结构化算法设计；初步掌握结构化算法设计；能够进行简单的算法复杂性分析；能够进行简单的算法复杂性分析；初步了解分治与递归。初步了解分治与递归。2.1 2.1 算法的描述算法的描述 2.1.1自然语言方式自然语言方式2.1.2伪代码方式伪代码方式2.1.3程序流程图方式程序流程图方式2.1.4N/S盒图方式盒图方式2.1.5PAD图方式图方式算法的描述方式很多，不同描述风格适用于不同场合，算法的描述方式很多，不同描述风格适用于不同场合，在面向对象技术出现之前，人们倾向于在算法的描述在面向对象技术出现之前，人们倾向于在算法的描述中对未来程序的层次结构进行一定程度的控制，而不中对未来程序的层次结构进行一定程度的控制，而不仅仅是描述具体的数据处理过程。本节介绍算法的常仅仅是描述具体的数据处理过程。本节介绍算法的常见描述方法。见描述方法。2.1.12.1.1自然语言方式自然语言方式 例例2.1 2.1 算法描述示例，算法描述示例，1.1.11.1.1中排序算法的自然语言描述。中排序算法的自然语言描述。2.1.22.1.2伪代码方式伪代码方式预先规定了描述规则和关键词，以接近某程序设计语言的风格描预先规定了描述规则和关键词，以接近某程序设计语言的风格描述算法。同时具有易理解和趋于形式化的优点。述算法。同时具有易理解和趋于形式化的优点。2.1.32.1.3程序流程图方式程序流程图方式算法由若干张流程图描述，每张流程图由结点和有向边构成，该图算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。描述了算法中所进行的操作以及这些操作执行的逻辑顺序。流程图的常用结点及控制结构描述如下流程图的常用结点及控制结构描述如下：端点符端点符处理处理判断判断预定义功能预定义功能连接符连接符条件条件处理处理1 1处理处理2 2选择结构选择结构循环结构循环结构或或是是条件条件否否处理处理do-whiledo-while条件条件处理处理否否是是repeat-untilrepeat-until处理处理1 1处理处理2 2顺序结构顺序结构2.1.42.1.4N/SN/S盒图方式盒图方式开始开始读读n个数到数组个数到数组anfor i=1 to n-1 step 1k=ifor j=i+1 to n step 1 查找第查找第 i 个数据后面的最小元素个数据后面的最小元素aj ak否否是是 k=ji!=k否否是是交换两个元素交换两个元素x=aj aj=ak ak=x结束结束算法2.2的N/S盒图描述2.1.52.1.5PADPAD图方式图方式PADPAD图结点与控制结构描述图结点与控制结构描述b b 选择结构选择结构d d 循环结构循环结构c c 多选择结构多选择结构a a 顺序结构顺序结构P P1 1P P2 2CP P1 1P P2 2P Pn n L L1 1L L2 2 X=X=L Ln nP PA A或或while cwhile cuntil cuntil cP P1 1P P2 2输入输出输入输出重复重复子算法子算法定义定义选择选择语句标号语句标号处理处理2.1.52.1.5PADPAD图方式图方式算法算法2.22.2的的PADPAD图描述图描述i！=kkiki i1；i=n-1；ii+1xaj；aj ak；ak x j1；j=n；jj+1kjkjajakajakanan算法开始算法开始算法结束算法结束2.22.2结构化算法设计初步结构化算法设计初步2.2.1 算法描述算法描述2.2.2 算法设计算法设计将组成算法的多个操作按照不同的层次组织在一起，每一组代表将组成算法的多个操作按照不同的层次组织在一起，每一组代表一种复杂的一种复杂的相对独立的复合操作相对独立的复合操作，各复合操作的内部亦可进行层，各复合操作的内部亦可进行层次划分，从而形成整个算法的嵌套层次结构。次划分，从而形成整个算法的嵌套层次结构。每一组操作具有每一组操作具有惟一惟一的入口和的入口和惟一惟一的出口的出口，即一端进一端出。这，即一端进一端出。这样的操作组置于其样的操作组置于其他他操作中时，算法的执行顺序必定是从前一组操作中时，算法的执行顺序必定是从前一组操作的出口到本组操作的入口，经过本组内部的运算，到达本组操作的出口到本组操作的入口，经过本组内部的运算，到达本组操作的操作的惟一惟一出口。出口。各组之间利用各组之间利用顺序、选择和循环顺序、选择和循环等三种控制结构在不同组之间进等三种控制结构在不同组之间进行连接，从而形成更高层次的算法结构。行连接，从而形成更高层次的算法结构。2.2.12.2.1算法描述算法描述1.1.结构化算法的流程图结构化算法的流程图 结点与控制结构结点与控制结构功能结点功能结点判定结点（分支结点）判定结点（分支结点）连接结点连接结点顺序结构顺序结构分支结构分支结构循环结构循环结构2.2.12.2.1算法描述算法描述1.1.结构化算法的流程图结构化算法的流程图 CBAc1blk5 c2truec4true blk3blk4 blk2 c3true blk1true.do if(c2)则则 if(c4)则则 blk3 否则否则 blk4 否则否则 if(c3)则则 blk1 否则否则 blk2 while(c1)blk52.2.12.2.1算法描述算法描述2.2.结构化算法的结构化算法的PADPAD图图.do ifc2)则则 if(c4)则则 blk3 否则否则 blk4 否则否则 if(c3)则则 blk1 否则否则 blk2 while(c1)blk5c1c2c4blk3blk4c3blk1blk2blk52.2.22.2.2算法设计算法设计问题描述问题描述解题思路解题思路顺序（主体结构）过程细化顺序（主体结构）过程细化循环过程细化循环过程细化选择过程细化选择过程细化模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理条件条件模糊的处理模糊的处理模糊的功能模糊的功能循环条件循环条件模糊的处理模糊的处理1.1.主体结构设计主体结构设计2.2.22.2.2算法设计算法设计问题处理核心模块问题处理核心模块善后处理模块善后处理模块初始化模块初始化模块依依次次找找出出未未排排序序部部分分中中的的最最小小数数，通通过过交交换换，顺顺序序地地放放入入anan的开始部分的开始部分读数据到读数据到anan算法的主体结构：算法的主体结构：算法开始标志块、初始化处理模块、问题处理核心模块、算法开始标志块、初始化处理模块、问题处理核心模块、善后处理模块、算法结束标志块。善后处理模块、算法结束标志块。算法主体结构算法主体结构算法算法2.22.2的调用结构的调用结构2.2.顺序结构设计顺序结构设计2.2.22.2.2算法设计算法设计例例2.3 求底面半径为求底面半径为r，高度为，高度为h的圆柱体的侧面积和体积。的圆柱体的侧面积和体积。算法输入：算法输入：圆柱的底面半径和高圆柱的底面半径和高算法输出：算法输出：圆柱的侧面积与体积圆柱的侧面积与体积数据结构：数据结构：r，Peri_bottom，S_bottom，S_side，V，h均为浮点数，均为浮点数，分别为底面半径、底面周长、底面面积，以及侧面面积，分别为底面半径、底面周长、底面面积，以及侧面面积，圆柱体积和高。圆柱体积和高。Peri_bottom3.14*2*rS_sidePeri_bottom*hS_bottom3.14*r*rVS_bottom*hr,hS_side,VPeri_bottom3.14*2*rS_sidePeri_bottom*hS_bottom3.14*r*rVS_bottom*hr,hS_side,V2.2.22.2.2算法设计算法设计3.3.选择结构设计选择结构设计-双分支结构双分支结构 例例2.4 求解一元二次方程求解一元二次方程ax2+bx+c=0算法输入：算法输入：一元二次方程的系数一元二次方程的系数a、b、c。算法输出：算法输出：一元二次方程的两个根。一元二次方程的两个根。数据结构：数据结构：三个系数三个系数a，b，c为浮点数。方程的两个根为浮点数。方程的两个根X1和和x2为浮点为浮点数。数。q存储中间结果，为浮点数。存储中间结果，为浮点数。算算法法结结束束a a,b b,c c算算法法开开始始“错错误误输输入入”“无无实实数数解解”x x1 1,x x2 2a a=0 0q qb b*b b-4 4*a a*c cq q 0 02.2.22.2.2算法设计算法设计3.3.选择结构设计选择结构设计-多分支结构多分支结构 例例2.5 2.5 输入年份，判断该年是否为闰年。输入年份，判断该年是否为闰年。算法输入：算法输入：年份年份x x算法输出：算法输出：年份年份x x是否为闰年的提示信息是否为闰年的提示信息数据结构：数据结构：x x为正整数，其值代表年份为正整数，其值代表年份算法开始算法开始算法结束算法结束x x 输入年份输入年份 x x是是400400的倍数的倍数 或者或者 x x是是4 4的倍数但不是的倍数但不是100100的倍数的倍数“x x是闰年是闰年”“x x不是闰年不是闰年”2.2.22.2.2算法设计算法设计3.3.选择结构设计选择结构设计-多分支结构多分支结构 例例2.62.6 设计一个根据输入的月份序号输出相应月份英文设计一个根据输入的月份序号输出相应月份英文名称的算法。名称的算法。算法输入：算法输入：月份序号月份序号MonthMonth算法输出：算法输出：与与MonthMonth对应的英文月份名对应的英文月份名数据结构：数据结构：MonthMonth为为0 01212的正整数，其值代表某一月份。的正整数，其值代表某一月份。“JanuaryJanuary”“December”“December”为为1212个月份的英文名（常字符串）。个月份的英文名（常字符串）。Month算法结束算法结束算法开始算法开始.“January”“December”“February”Month=1212.2.2.22.2.2算法设计算法设计3.3.循环结构设计循环结构设计 例例 2.7 2.7 求任意正整数的阶乘。求任意正整数的阶乘。算法输入：算法输入：正整数正整数n n算法输出：算法输出：正整数正整数n n的阶乘的阶乘数据结构：数据结构：n n、k k、p p均为正整数，分别代表待求阶乘整数、已循均为正整数，分别代表待求阶乘整数、已循环次数和部分积。环次数和部分积。假假k=nk=nkk+1pp*k算法结束算法结束算法开始算法开始输入输入nk0；p1真真直到型循环直到型循环步长型循环步长型循环算法开始算法开始 n p1k0;k0，一个算法能够在，一个算法能够在Cn2的时的时间内处理完规模大小为间内处理完规模大小为n的输入，则该算法的时间的输入，则该算法的时间复杂性记为复杂性记为O(n2)，称作，称作n2级级。例例2.9 分析算法时间复杂性：将一个字符串倒序。分析算法时间复杂性：将一个字符串倒序。2.3 2.3 算法的计算复杂性算法的计算复杂性算法算法 2.3 2.3 字符串倒序字符串倒序。数据结构：数据结构：strnstrn为为n n元素字符数组；元素字符数组；k k为字符型中间变量。为字符型中间变量。算法结束算法结束i0i0；i=int(n/2)i=int(n/2)；ii+1ii+1kstrikstristristrn-istristrn-istrn-ikstrn-ik算法开始算法开始2.4 2.4 常用算法设计策略常用算法设计策略2.4.1 分治法分治法2.4.2 递归技术递归技术2.4.3 贪心法贪心法*2.4.4 回溯法回溯法*对科学研究和计算中的一些常见问题人们形成了一些对科学研究和计算中的一些常见问题人们形成了一些常用的算法及其设计策略。常用的算法及其设计策略。2.4.1 2.4.1 分治法分治法二进制乘法：二进制乘法：分而治之之法：分而治之之法：将复杂问题分解成一系列简单组成部将复杂问题分解成一系列简单组成部分，这些组成部分的复杂性低，易解决，将所有组成部分，这些组成部分的复杂性低，易解决，将所有组成部分解决后组合到一起得到复杂问题的解答。分解决后组合到一起得到复杂问题的解答。分治法通常与递归技术一同使用。分治法通常与递归技术一同使用。1011100110110000000010111100011移位相加移位相加-时间复杂性为时间复杂性为O(n2)O(n2)2.4.1 2.4.1 分治法分治法分治法计算二进制数乘法分治法计算二进制数乘法令令于是于是其中其中只需只需3 3次次n/2n/2位二进制乘法，位二进制乘法，2 2次移位（乘次移位（乘2 2n n及及2 2n/2n/2），），6 6次加次加减法，如仅考虑减法，如仅考虑U U是是n/2n/2位的情况，则运算时间复杂性为：位的情况，则运算时间复杂性为：=O（n1.59）一种以有限方式描述规模任意大问题的方法一种以有限方式描述规模任意大问题的方法 2.4.2 2.4.2 递归技术递归技术1st 1st 集合集合A A由含有同样多个字符由含有同样多个字符a a和和b b的所有字符串组成的所有字符串组成2nd 2nd 空空串属于集合串属于集合A A3rd 3rd 若字符串若字符串S S属于属于A A，则字符串则字符串abSabS、aSbaSb、SabSab、baSbaS、bSabSa、SbaSba也属于也属于A A除此之外没有其他的字符串属于除此之外没有其他的字符串属于A A，且长度比，且长度比S S多多2 2。算法与程序设计中的递归是狭义的递归，指将问题按层次划分算法与程序设计中的递归是狭义的递归，指将问题按层次划分为多个层次的子问题，各子问题难度随层次降低，每一层次的为多个层次的子问题，各子问题难度随层次降低，每一层次的问题都由低一层次的子问题组成，而且相应的各层次问题的解问题都由低一层次的子问题组成，而且相应的各层次问题的解题算法相同。于是解决某一层次问题的算法将由调用相同算法题算法相同。于是解决某一层次问题的算法将由调用相同算法解决子问题组成。解决子问题组成。