算法设计基础.pptx

《算法设计基础.pptx》由会员分享，可在线阅读，更多相关《算法设计基础.pptx（24页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、2.1 2.1 算法的描述算法的描述 2.1.1自然语言方式2.1.2伪代码方式2.1.3程序流程图方式2.1.4N/S盒图方式2.1.5PAD图方式算法的描述方式很多，不同描述风格适用于不同场合，在面向对象技术出现之前，人们倾向于在算法的描述中对未来程序的层次结构进行一定程度的控制，而不仅仅是描述具体的数据处理过程。本节介绍算法的常见描述方法。第1页/共24页2.1.12.1.1自然语言方式自然语言方式 例例2.1 2.1 算法描述示例，算法描述示例，1.1.11.1.1中排序算法的自然语言描述。中排序算法的自然语言描述。2.1.22.1.2伪代码方式伪代码方式预先规定了描述规则和关键词，以

2、接近某程序设计语言的风格描述算法。同时具有易理解和趋于形式化的优点。第2页/共24页2.1.32.1.3程序流程图方式程序流程图方式算法由若干张流程图描述，每张流程图由结点和有向边构成，该图描述了算法中所进行的操作以及这些操作执行的逻辑顺序。流程图的常用结点及控制结构描述如下：端点符处理判断预定义功能连接符条件处理1 1处理2 2选择结构循环结构或是条件否处理do-whiledo-while条件处理否是repeat-untilrepeat-until处理1 1处理2 2顺序结构第3页/共24页2.1.42.1.4N/SN/S盒图方式盒图方式开始开始读读n个数到数组个数到数组anfor i=1

3、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盒图描述第4页/共24页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 cunt

4、il cuntil cP P1 1P P2 2输入输出输入输出重复重复子算法子算法定义定义选择选择语句标号语句标号处理处理第5页/共24页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算法开始算法结束第6页/共24页2.22.2结构化算法设计初步结构化算法设计初步2.2.1 算法描述2.2.2 算法设计将组成算法的多个操作按照不同的层次组织在一起，每一组代表将组成算法的多个操作按照不同的层次组织在一起，每一组代表一种复杂的

5、一种复杂的相对独立的复合操作相对独立的复合操作，各复合操作的内部亦可进行层，各复合操作的内部亦可进行层次划分，从而形成整个算法的嵌套层次结构。次划分，从而形成整个算法的嵌套层次结构。每一组操作具有每一组操作具有惟一的入口和惟一的出口惟一的入口和惟一的出口，即一端进一端出。这，即一端进一端出。这样的操作组置于其他操作中时，算法的执行顺序必定是从前一组样的操作组置于其他操作中时，算法的执行顺序必定是从前一组操作的出口到本组操作的入口，经过本组内部的运算，到达本组操作的出口到本组操作的入口，经过本组内部的运算，到达本组操作的惟一出口。操作的惟一出口。各组之间利用各组之间利用顺序、选择和循环顺序、选择

6、和循环等三种控制结构在不同组之间进等三种控制结构在不同组之间进行连接，从而形成更高层次的算法结构。行连接，从而形成更高层次的算法结构。第7页/共24页2.2.12.2.1算法描述算法描述1.1.结构化算法的流程图结构化算法的流程图 结点与控制结构结点与控制结构功能结点功能结点判定结点（分支结点）判定结点（分支结点）连接结点连接结点顺序结构顺序结构分支结构分支结构循环结构循环结构第8页/共24页2.2.12.2.1算法描述算法描述1.1.结构化算法的流程图结构化算法的流程图 CBAc1blk5 c2truec4true blk3blk4 blk2 c3true blk1true.do if(c2

7、)则 if(c4)则 blk3 否则 blk4 否则 if(c3)则 blk1 否则 blk2 while(c1)blk5第9页/共24页2.2.12.2.1算法描述算法描述2.2.结构化算法的结构化算法的PADPAD图图.do if(c2)则 if(c4)则 blk3 否则 blk4 否则 if(c3)则 blk1 否则 blk2 while(c1)blk5c1c2c4blk3blk4c3blk1blk2blk5第10页/共24页2.2.22.2.2算法设计算法设计问题描述解题思路顺序（主体结构）过程细化顺序（主体结构）过程细化循环过程细化循环过程细化选择过程细化选择过程细化模糊的处理模糊的

8、处理模糊的处理模糊的处理模糊的处理模糊的处理模糊的处理条件模糊的处理模糊的功能循环条件模糊的处理第11页/共24页1.1.主体结构设计主体结构设计2.2.22.2.2算法设计算法设计问题处理核心模块善后处理模块初始化模块依次找出未排序部分中的最小数，通过交换，顺序地放入anan的开始部分读数据到anan算法的主体结构：算法的主体结构：算法开始标志块、初始化处理模块、问题处理核心模块、算法开始标志块、初始化处理模块、问题处理核心模块、善后处理模块、算法结束标志块。善后处理模块、算法结束标志块。算法主体结构算法主体结构算法算法2.22.2的调用结构的调用结构第12页/共24页2.2.顺序结构设计顺

9、序结构设计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

10、*r*rVS_bottom*hr,hS_side,VPeri_bottom3.14*2*rS_sidePeri_bottom*hS_bottom3.14*r*rVS_bottom*hr,hS_side,V第13页/共24页2.2.22.2.2算法设计算法设计3.3.选择结构设计选择结构设计-双分支结构双分支结构 例例2.4 求解一元二次方程求解一元二次方程ax2+bx+c=0算法输入：算法输入：一元二次方程的系数一元二次方程的系数a、b、c。算法输出：算法输出：一元二次方程的两个根。一元二次方程的两个根。数据结构：数据结构：三个系数三个系数a，b，c为浮点数。方程的两个根为浮点数。方程的两个根

11、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 0第14页/共24页2.2.22.2.2算法设计算法设计3.3.选择结构设计选择结构设计-多分支结构多分支结构 例例2.5 2.5 输入年份，判断该年是否为闰年。输入年份，判断该年是否为闰年。算法输入：算法输入：年份年份x x算法输出：算法输出：年份年份x x是否为闰年的提示信息是否为闰年的提示信息数据结构：数据结构：x x为正整数，其值代表年份为正整数，其

12、值代表年份算法开始算法结束x x 输入年份 x x是400400的倍数 或者 x x是4 4的倍数但不是100100的倍数“x x是闰年”“x x不是闰年”第15页/共24页2.2.22.2.2算法设计算法设计3.3.选择结构设计选择结构设计-多分支结构多分支结构 例例2.62.6 设计一个根据输入的月份序号输出相应月份英文设计一个根据输入的月份序号输出相应月份英文名称的算法。名称的算法。算法输入：算法输入：月份序号月份序号MonthMonth算法输出：算法输出：与与MonthMonth对应的英文月份名对应的英文月份名数据结构：数据结构：MonthMonth为为0 01212的正整数，其值代表

13、某一月份。的正整数，其值代表某一月份。“JanuaryJanuary”“December”“December”为为1212个月份的英文名（常字符串）。个月份的英文名（常字符串）。Month算法结束算法开始.“January”“December”“February”Month=1212.第16页/共24页2.2.22.2.2算法设计算法设计3.3.循环结构设计循环结构设计 例例 2.7 2.7 求任意正整数的阶乘。求任意正整数的阶乘。算法输入：算法输入：正整数正整数n n算法输出：算法输出：正整数正整数n n的阶乘的阶乘数据结构：数据结构：n n、k k、p p均为正整数，分别代表待求阶乘整数、

14、已循均为正整数，分别代表待求阶乘整数、已循环次数和部分积。环次数和部分积。假k=nk=nkk+1pp*k算法结束算法开始输入nk0；p1真直到型循环步长型循环算法开始 n p1k0;k0，一个算法能够在，一个算法能够在Cn2的时的时间内处理完规模大小为间内处理完规模大小为n的输入，则该算法的时间的输入，则该算法的时间复杂性记为复杂性记为O(n2)，称作，称作n2级级。第18页/共24页例2.9 分析算法时间复杂性：将一个字符串倒序。2.3 2.3 算法的计算复杂性算法的计算复杂性算法 2.3 2.3 字符串倒序。数据结构：strnstrn为n n元素字符数组；k k为字符型中间变量。算法结束i

15、0i0；i=int(n/2)i=int(n/2)；ii+1ii+1kstrikstristristrn-istristrn-istrn-ikstrn-ik算法开始第19页/共24页2.4 2.4 常用算法设计策略常用算法设计策略2.4.1 分治法2.4.2 递归技术2.4.3 贪心法*2.4.4 回溯法*对科学研究和计算中的一些常见问题人们形成了一些常用的算法及其设计策略。第20页/共24页2.4.1 2.4.1 分治法分治法二进制乘法：二进制乘法：分而治之之法：将复杂问题分解成一系列简单组成部分，这些组成部分的复杂性低，易解决，将所有组成部分解决后组合到一起得到复杂问题的解答。分治法通常与递

16、归技术一同使用。1011100110110000000010111100011移位相加-时间复杂性为O(n2)O(n2)第21页/共24页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）第22页/共24页一种以有限方式描述规模任意大问题的方法一种以有限方式描述规模任意大问题的方法 2.4.2 2.4.2 递归技术递归技术1st 1st 集合集合A A由含有同样多个字符由含有

17、同样多个字符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。算法与程序设计中的递归是狭义的递归，指将问题按层次划分为多个层次的子问题，各子问题难度随层次降低，每一层次的问题都由低一层次的子问题组成，而且相应的各层次问题的解题算法相同。于是解决某一层次问题的算法将由调用相同算法解决子问题组成。第23页/共24页感谢您的观看！第24页/共24页