C++程序设计课件第02章.ppt
第第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.4 N/S盒图方式盒图方式2.1.5 PAD图方式图方式算法的描述方式很多，不同描述风格适用于不同场合，算法的描述方式很多，不同描述风格适用于不同场合，在面向对象技术出现之前，人们倾向于在算法的描述在面向对象技术出现之前，人们倾向于在算法的描述中对未来程序的层次结构进行一定程度的控制，而不中对未来程序的层次结构进行一定程度的控制，而不仅仅是描述具体的数据处理过程。本节介绍算法的常仅仅是描述具体的数据处理过程。本节介绍算法的常见描述方法。见描述方法。2.1.12.1.1自然语言方式自然语言方式算法表示如下：算法表示如下：S1S1：输入输入n n的值的值S2S2：2 2 i (i i (i 作为除数）作为除数）S3:n S3:n 被被 i i 除，得余数除，得余数 r rS4:S4:如果如果 r r 等于等于 0 0，表示表示 n n 能能 被被 i i 整除，则打印整除，则打印 n n“不是素数不是素数”，算法结束；否则执行，算法结束；否则执行S5S5S5S5：i+1 i+1 i i S6:S6:如果如果 i i n-1,n-1,返回返回S3S3；否则，打印否则，打印 n“n“是素数是素数”，算，算法结束。法结束。例例1 1：对一个大于或等于：对一个大于或等于3 3的正整数，判断它是不是一个素数的正整数，判断它是不是一个素数方法：将方法：将 n(n(其中其中n n 3)3)作为被除数，作为被除数，将将2 2 到（到（n-1)n-1)各个整数轮流各个整数轮流作为除数，如果都不能被整除，则作为除数，如果都不能被整除，则n n为素数。为素数。2.1.22.1.2伪代码方式伪代码方式预先规定了描述规则和关键词，以接近某程序设计语言预先规定了描述规则和关键词，以接近某程序设计语言的风格描述算法。同时具有易理解和趋于形式化的优点。的风格描述算法。同时具有易理解和趋于形式化的优点。Begin input n 2 i while（i n-1）n mod i r if(0=r)output n is not Prime；exit /退出循环 i+1 i if（i=n）output n is Prime End 此地用到了循环结构2.1.32.1.3程序流程图方式程序流程图方式算法由若干张流程图描述，每张流程图由结点和有向边构算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。逻辑顺序。流程图的常用结点及控制结构描述如下流程图的常用结点及控制结构描述如下：循环结构循环结构或或是是条件条件否否处理处理当型循环当型循环条件条件处理处理否否是是直到循环直到循环端点符端点符处理处理判断判断预定义功能预定义功能连接符连接符条件条件处理处理1 1处理处理2 2选择结构选择结构处理处理1 1处理处理2 2顺序结构顺序结构流程线流程线2.1.32.1.3程序流程图方式程序流程图方式开始输入n的值i=n-1i=2r=n%ir=0YNi=i+1输出 n 不是素数输出 n 是素数结束YN此地都可采用平行四边形框输入和输出时可采用该框2.1.4改进的流程图-N/S流程图o略2.1.52.1.5PADPAD图图（Problem Analysis DiagramProblem Analysis Diagram）方式方式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图方式图方式 i=n-1n算法开始算法开始算法结束算法结束i=2i=2r=n%ir=0i=i+1i=i+1n 不是素数n 是素数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 if(c2)则则 if(c4)则则 blk3 否则否则 blk4 否则否则 if(c3)则则 blk1 否则否则 blk2 while(c1)blk5c1c2c4blk3blk4c3blk1blk2blk52.2.22.2.2算法设计算法设计问题描述问题描述解题思路解题思路顺序（主体结构）过程细化顺序（主体结构）过程细化循环过程细化循环过程细化选择过程细化选择过程细化模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理条件条件模糊的处理模糊的处理模糊的功能模糊的功能循环条件循环条件模糊的处理模糊的处理1.1.主体结构设计主体结构设计2.2.22.2.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,b,ca,b,c算法开始算法开始“错误输入错误输入”“无实数解无实数解”x1,x2x1,x2a=0a=0q qb*b-4*a*cb*b-4*a*cq 0q 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”“DecemberDecember”为为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;k1)在求解过程中不断调用相同的求解阶乘方法，直到转化为求为求得1的阶乘（已知），最后返回计算n的阶乘。
