软件技术基础复习ppt课件.ppt

《软件技术基础复习ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章算法1.1算法的基本概念1.1.1算法的基本特征1.1.2算法的基本要素1.2算法设计基本方法1.3算法的复杂度分析1.3.1算法的时间复杂度1.3.2算法的空间复杂度教学目标了解算法的基本概念、算法描述语言，掌握几种常见算法的基本实现，并能分析算法的时间和空间复杂度。学习要点⑴掌握算法的基本概念和基本特征⑵掌握常用的几种算法的思想，例如：列举法，递推法，递归法和减半递推。⑶算法复杂度的概念和意义（时间复杂度与空间复杂度）。引出算法程序设计主要包括两个方面的内容：行为特性的设计----将解决实际问

2、题的每个细节准确地加以定义，并且还应当将全部解题过程完整地描述出来。这就是算法的设计。结构特性的设计----确定合适的数据结构。1.1算法基本概念算法（Algorithm）是对特定问题求解步骤的一种描述；是一组指令的有限集合。算法的基本特征能行性：算法中描述的操作都是可通过已经实现的基本运算、执行有限次实现的；确定性：算法中的每一条指令必须有明确的含义，不能有二义性；有穷性：一个算法必须总是在执行有穷步后结束，且每一步都可在合理的执行时间内完成；拥有足够情报：一个算法应有0个或多个输入；结论：所谓算法，是

3、一组严谨地定义运算顺序的规则，并且每一个规则都是有效的、明确的，此顺序将在有限的次数下终止。1.1.2算法的基本要素算法中对数据的运算和操作（1）算术运算：主要包括加、减、乘、除等运算。（2）逻辑运算：主要包括“与”、“或”、“非”等运算。（3）关系运算：主要包括“大于”、“小于”、“等于”、“不等于”等运算。（4）数据传输：主要包括赋值、输入、输出等操作。算法的控制结构算法中各操作之间的执行顺序称为算法的控制结构。算法的控制结构给出了算法的基本框架，算法一般都可以用顺序、选择、循环三种基本控制结构组合而

4、成1.2算法设计基本方法列举法归纳法递推递归减半递推技术回溯法1.列举法基本思想根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。因此，列举法常用于解决“是否存在”或“有多少种可能”等类型的问题，例如求解不定方程的问题。例题：设每只母鸡值3元，每只公鸡值2元，每只小鸡值0.5元。现要用100元钱买100只鸡，设计买鸡方案，这就是经典的求解百鸡问题。PROCEDUREBAIJIFORI=0TO100DOFORJ=0TO100DOFORK=0TO100DO{M＝I+J+

5、KN＝3I十2J+0.5KIF（（M＝100）and（N＝100））THENOUTPUTI，J，K}RETURN总循环次数为1013＝1030301首先，考虑到母鸡为3元一只，因此，母鸡最多只能买33以，即算法中的外循环没有必要从0到100．而只需要从0到33就可以了。其次，考虑到公鸡为2元一只，因此，公鸡最多只能头50只。又考虑到对公鸡的列举是在算法的第二层循环中，此时已经买了I只母鸡，且买一只母鸡的价钱相当于买1.5只公鸡。因此，由第一层循环已经确定买I只母鸡的前提下，公鸡最多只能买50-1.5I只，

6、即第二层对J的循环只需从0到50-1.5I就可以了。最后，考虑到买的总鸡数为100，而由第一层循环已确定买I只母鸡，由第二层循环已确定买J只公鸡，因此，买小鸡的数量只能是K=100-I-J，即第三层循环已经没有必要了。改进后的算法PROCEDUREBAIJIFORI＝0TO33DOFORJ=0TO50-1.5IDO{K=100-I-JIF（3I+2J+0.5K=100）THENOUTPUTI，J，K}RETURN总循环次数为#include#includeusingn

7、amespacestd;intmain（）{inti,j,k;for(i=0;i<=33;i++)for(j=0;j<=50-1.5*i;j++){k=100-i-j;if(3*i+2*j+0.5*k==100.0)cout<

8、能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。3.递推法基本思想从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简而得到确定。例题递推法例题分析发现相邻两个积分之间存在以下关系:只要知道In-1就可以算出In，也就是说，只要知道了I0，就可以通过这个递推公式计算出所有的积分值In（n=1，2，…，20）。这