《计算机软件基础》第1章算法

1、第1章 算法1计算机软件技术基础计算机软件技术基础第1章 算法2课课 程程 介介 绍绍课时安排：课时安排： 理论：理论：28 实验：实验：28 课程设计：课程设计：8上课要求：需要同学在青海大学上课要求：需要同学在青海大学“教育在线教育在线”选课选课 网址：网址：老师的联系方式：老师的联系方式： 办公地点：计算机系三楼计算机教研室办公地点：计算机系三楼计算机教研室 Email:参考教材：徐士良编著，计算机软件技术基础，参考教材：徐士良编著，计算机软件技术基础，第二版第二版. .清华大学出版社，清华大学出版社，20072007第1章 算法3第第1章章 算算 法法1.1 算法的基本概念算法的基本概

2、念1.2 算法描述语言算法描述语言1.3 算法设计基本方法算法设计基本方法1.4 算法的复杂度分析算法的复杂度分析第1章 算法41.1 算法的基本概念算法的基本概念1.1.1 算法的基本特征算法的基本特征 算法是指解题方案的准确而完整的描述。算法是指解题方案的准确而完整的描述。1.1.能行性能行性(effectiveness)(effectiveness)算法的能行性包括以下两个方面：算法的能行性包括以下两个方面：（1 1）算法中的每一个步骤必须能够实现。）算法中的每一个步骤必须能够实现。（2 2）算法执行的结果要能够达到预期的目的。）算法执行的结果要能够达到预期的目的。 A A1010121

3、2，B B1 1，C C10101212 A AB BC C101012121 1( (10101212) )0 0 A AC CB B10101212( (10101212) )1 11 1第1章 算法52.2.确定性确定性(definiteness)(definiteness) 算法的确定性，是指算法中的每一个步骤都必算法的确定性，是指算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。也不允许有多义性。3.3.有穷性有穷性(finiteness)(finiteness) 算法的有穷性，是指算法必须能在有限的时间算法的

4、有穷性，是指算法必须能在有限的时间内做完，即算法必须能在执行有限个步骤之后内做完，即算法必须能在执行有限个步骤之后终止。终止。4.4.拥有足够的情报拥有足够的情报 一个算法是否有效，还取决于为算法所提供的情一个算法是否有效，还取决于为算法所提供的情报是否足够。通常，算法中的各种运算总是要报是否足够。通常，算法中的各种运算总是要施加到各个运算对象上，而这些运算对象又可施加到各个运算对象上，而这些运算对象又可能能具有某种初始状态，这是算法执行的起点能能具有某种初始状态，这是算法执行的起点或是依据。或是依据。第1章 算法6 因此，一个算法执行的结果总是与输入的初始因此，一个算法执行的结果总是与输入的

5、初始数据有关，不同的输入将会有不同的输出。一数据有关，不同的输入将会有不同的输出。一般来说，当算法拥有足够的情报时，此算法才般来说，当算法拥有足够的情报时，此算法才是有效的，而当提供的情报不够时，算法并不是有效的，而当提供的情报不够时，算法并不有效。有效。 综上所述，算法是一组严谨地定义运算顺序的综上所述，算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。的，此顺序将在有限的次数下终止。第1章 算法71.1.2 算法的基本要素算法的基本要素一个算法通常由两种基本要素组成一个算法通常由两种基本要素组成：(

6、1) (1) 算法中对数据的运算和操作算法中对数据的运算和操作 算术运算算术运算 逻辑运算逻辑运算 关系运算关系运算 数据传输数据传输(2) (2) 算法的控制结构算法的控制结构 一个算法的功能不仅取决于所选用的操作，而且还与各操作一个算法的功能不仅取决于所选用的操作，而且还与各操作之间的执行顺序有关。算法中各操作之间的执行顺序称为控之间的执行顺序有关。算法中各操作之间的执行顺序称为控制结构。一个算法一般都可以用顺序、选择、循环三种基本制结构。一个算法一般都可以用顺序、选择、循环三种基本控制结构组合而成。控制结构组合而成。第1章 算法81.2 算法描述语言算法描述语言1.符号与表达式符号与表达

7、式符号是以字母开头的字母和数字的有限串，主要用符号是以字母开头的字母和数字的有限串，主要用来表示变量名、数组名等，必要时也用来表示语句来表示变量名、数组名等，必要时也用来表示语句标号。例如：标号。例如： looploop：i ii i1 1 有时，为了使算法更清楚，算法中的某些指令或子过有时，为了使算法更清楚，算法中的某些指令或子过程直接用叙述的方式给出。例如：程直接用叙述的方式给出。例如： “设设x x是是A A中的最大项中的最大项”（其中（其中A A是一个数组）是一个数组） “ “将将x x插入到插入到L L之中之中”（其中（其中L L是某个表）是某个表） 在算法中，算术运算符沿用数学中的

8、表示法：在算法中，算术运算符沿用数学中的表示法：（1 1）关系运算符用、）关系运算符用、（2 2）逻辑运算符用）逻辑运算符用and(and(与与) )、or(or(或或) )、not(not(非非) )第1章 算法92.赋值语句赋值语句赋值语句的形式为赋值语句的形式为 a ae e其中其中a a为变量名或数组元素，为变量名或数组元素，e e为算术表达式或逻辑为算术表达式或逻辑表达式。表达式。 如果如果a a和和b b都是变量名或数组元素，则可用记号都是变量名或数组元素，则可用记号： 表示将表示将a a和和b b的内容互换。的内容互换。 如果想将表达式如果想将表达式e e的计算结果同时赋给的计算

9、结果同时赋给a a与与b b，则可用记，则可用记号：号： a ab be eab第1章 算法103.控制转移语句控制转移语句 无条件转移语句的形式：无条件转移语句的形式： GOTO GOTO 标号标号 条件转移语句的形式：条件转移语句的形式： IF C THEN SIF C THEN S 或或 IF C THEN SIF C THEN S1 1 ELSE S ELSE S2 2第1章 算法114.循环语句循环语句 WHILEWHILE语句语句 WHILE C DO SWHILE C DO S 功能等价于如下的功能等价于如下的IFIF语句：语句： looploop：IF C THENIF C T

10、HEN S S GOTO loop GOTO loop 第1章 算法12FORFOR语句语句FOR iFOR iinit TO limit BY step DO Sinit TO limit BY step DO SFOR iFOR iinit TO limit DO Sinit TO limit DO S 当当stepstep0 0时，功能等价于如下的时，功能等价于如下的IFIF语句：语句： i iinitinit loop loop：IF ilimit THENIF ilimit THEN S S i ii istepstep GOTO loop GOTO loop 第1章 算法13当当s

11、tepstep0 0时，功能等价于如下的时，功能等价于如下的IFIF语句：语句： i iinitinit loop loop：IF ilimit THENIF ilimit THEN S S i ii istepstep GOTO loop GOTO loop 第1章 算法145.其它语句其它语句EXITEXIT：用于退出某个循环，使控制转到包含：用于退出某个循环，使控制转到包含EXITEXIT语句的最内层的语句的最内层的WHILEWHILE或或FORFOR循环后面的循环后面的一个语句去执行。一个语句去执行。READREAD（或（或INPUTINPUT）和）和WRITEWRITE（或（或PRI

12、NTPRINT，或，或OUTPUTOUTPUT）语句分别用于输入和输出。语句分别用于输入和输出。RETURNRETURN语句用于结束算法的执行。如果算法是语句用于结束算法的执行。如果算法是在最后一行之后结束，则可以省略在最后一行之后结束，则可以省略RETURNRETURN语语句。句。第1章 算法151.3 算法设计基本方法算法设计基本方法1. 列举法列举法 根据提出的问题，列举所有可能的情况，根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要并用问题中给定的条件检验哪些是需要的，哪些是不需要的。的，哪些是不需要的。因此，列举法常用于解决因此，列举法常用于解决“是否存在是否存

13、在”或或“有多少种可能有多少种可能”等类型的问题，比如，等类型的问题，比如，求解不定方程的问题。求解不定方程的问题。第1章 算法16例如：百元买百鸡问题。例如：百元买百鸡问题。设每只母鸡值设每只母鸡值3 3元，每只公鸡值元，每只公鸡值2 2元，两只小鸡值元，两只小鸡值1 1元。现要用元。现要用100100元钱买元钱买100100只鸡，设计买鸡方案。只鸡，设计买鸡方案。 假设买母鸡假设买母鸡I I只，公鸡只，公鸡J J只，小鸡只，小鸡K K只。只。第1章 算法17 FOR I FOR I0 TO 100 DO0 TO 100 DO FOR J FOR J0 TO 100 DO0 TO 100 D

14、O FOR K FOR K0 TO 100 DO0 TO 100 DO M MI IJ JK K N N3I3I2J2J0.5K0.5K IF (M IF (M100)and(N100)and(N100) THEN100) THEN OUTPUT I OUTPUT I，J J，K K RETURN RETURN总循环次数为总循环次数为1011013 3第1章 算法18 FOR I FOR I0 TO 33 DO0 TO 33 DO FOR J FOR J0 TO 500 TO 501.5I DO1.5I DO K K100100I IJ J IF (3I IF (3I2J2J0.5K0.5K1

15、00) THEN100) THEN OUTPUT I OUTPUT I，J J，K K RETURN RETURN总循环次数为总循环次数为894) I 5 . 151(330I算法改进算法改进第1章 算法19 #include stdio.h #include stdio.h main() main() int i int i，j j，k k； for (ifor (i0 0； i i3333； i i) ) for (j for (j0 0； j j50501.51.5* *i i； j j) ) k k100100i ij j； if (3if (3* *i i2 2* *j j0.50.

16、5* *k k100.0)100.0) printf(%5d%5d%5dn printf(%5d%5d%5dn，i i，j j，k)k)； 第1章 算法20 运行结果如下：运行结果如下： 2 30 682 30 68 5 25 70 5 25 70 8 20 72 8 20 72 11 15 74 11 15 74 14 10 76 14 10 76 17 5 78 17 5 78 20 0 80 20 0 80第1章 算法212. 归纳法归纳法 归纳法的基本思想是，通过列举少量的特殊情况。经归纳法的基本思想是，通过列举少量的特殊情况。经过分析。最后找出一般的关系。显然，归纳法要比列过分析。最

17、后找出一般的关系。显然，归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。从本质上讲。归纳就是通过观个数学模型更为困难。从本质上讲。归纳就是通过观察一些简单而特殊的情况，最后总结出一般性的结论。察一些简单而特殊的情况，最后总结出一般性的结论。归纳是一种抽象，即从特殊现象中找出一般关系。但归纳是一种抽象，即从特殊现象中找出一般关系。但由于在归

18、纳的过程中不可能对所有的情况进行列举，由于在归纳的过程中不可能对所有的情况进行列举，因此，最后由归纳得到的结论还只是一种猜测，还需因此，最后由归纳得到的结论还只是一种猜测，还需要对这种猜测加以必要的证明。实际上，通过精心观要对这种猜测加以必要的证明。实际上，通过精心观察而得到的猜测得不到证实或最后证明猜测是错的。察而得到的猜测得不到证实或最后证明猜测是错的。也是常有的事。也是常有的事。 第1章 算法223. 递推递推 所谓递推，是指从已知的初始条件出发，逐次所谓递推，是指从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果、其中初推出所要求的各中间结果和最后结果、其中初始条件或是问题本身

19、已经给定，或是通过对问始条件或是问题本身已经给定，或是通过对问题的分析与化简而确定。递推本质上也属于归题的分析与化简而确定。递推本质上也属于归纳法，工程上许多递推关系式实际上是通过对纳法，工程上许多递推关系式实际上是通过对实际问题的分析与归纳而得到的。递推关系式实际问题的分析与归纳而得到的。递推关系式往往是归纳的结果。往往是归纳的结果。 递推算法在数值计算递推算法在数值计算中是极为常见的。但是，对于数值型的递推算中是极为常见的。但是，对于数值型的递推算法必须要注意数值计算的稳定性问题。法必须要注意数值计算的稳定性问题。 第1章 算法23例例第1章 算法24第1章 算法251,20,21,30n

20、,I51n51I1In1n30第1章 算法26第1章 算法274. 递归递归 将一个复杂的问题归结为若干个较简单的将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。做下去，直到最简单的问题为止。第1章 算法28例编写一个过程，对于输入的参数例编写一个过程，对于输入的参数n n，依次打印输出自然，依次打印输出自然数数1 1到到n n。 PROCEDURE WRT(n) FOR k1 TO n DO OUTPUT k RETURN#incl

21、ude stdio.h wrt(int n) int k； for (k1；kn；k) printf(%dn，k)； return； 非递归算法非递归算法第1章 算法29PROCEDURE WRT1(n) IF (n0) THEN WRT1(n1) OUTPUT n RETURN#include stdio.h wrt1(int n) if (n!0) wrt1(n1)； printf(%dn，n)； return； 递归算法递归算法第1章 算法30递归算法调用过程详解递归算法调用过程详解main() wrt1(1)wrt1( int n )if ( n != 0 ) wrt1( n - 1)

22、； printf(%dn，n)； wrt1( int n )if ( n != 0 ) wrt1(n-1)； printf(%dn，n)； 11100第1章 算法315. 减半递推技术减半递推技术所谓所谓“减半减半”，是指将问题的规模减半，是指将问题的规模减半，而问题的性质不变。而问题的性质不变。所谓所谓“递推递推”，是指重复，是指重复“减半减半”的过程。的过程。第1章 算法32例二分法求方程实根的减半递推过程：例二分法求方程实根的减半递推过程：首先取给定区间的中点首先取给定区间的中点c c(a(ab)/2b)/2。然后判断然后判断f(c)f(c)是否为是否为0 0。 若若f(c)f(c)0,

23、0,则说明则说明c c即为所求的根，求解过程结即为所求的根，求解过程结束；束； 如果如果f(c)0,f(c)0,则根据以下原则将原区间减半：则根据以下原则将原区间减半： 若若f(a)f(c)f(a)f(c)0 0，则取原区间的前半部分；，则取原区间的前半部分； 若若f(b)f(c)f(b)f(c)0 0，则取原区间的后半部分。，则取原区间的后半部分。最后判断减半后的区间长度是否已经很小：最后判断减半后的区间长度是否已经很小： 若若|a|ab|b|，则过程结束，取，则过程结束，取(a(ab)/2b)/2为根为根的近似值；的近似值； 若若|a|ab|b|，则重复上述的减半过程。，则重复上述的减半过

24、程。第1章 算法33 FUNCTION ROOT(a FUNCTION ROOT(a，b b，epseps，f)f) f0 f0f(a)f(a) WHILE (|a WHILE (|ab|) DOb|) DO c c(a(ab)/2b)/2； f1f1f(c) f(c) IF (f1 IF (f10) THEN0) THEN ROOT ROOTc c ；RETURN RETURN IF (f0 IF (f0* *f1f10) THEN a0) THEN ac c ELSE b ELSE bc c c c(a(ab)/2b)/2；ROOTROOTc c RETURN RETURN第1章 算法34

25、#include stdio.h”#include stdio.h”#include math.h”#include math.h”double root(adouble root(a，b b，epseps，f)f)double adouble a，b b，epseps，( (* *f)()f)()； double f0 double f0，f1f1，c c； f0f0( (* *f)(a)f)(a)； while (fabs(awhile (fabs(ab)b)eps)eps) c c(a(ab)/2b)/2； f1f1( (* *f)(c)f)(c)； if (f1if (f10) ret

26、urn(c)0) return(c)； if (f0if (f0* *f1f10) a0) ac c； else belse bc c； c c(a(ab)/2b)/2； return(c)return(c)； 第1章 算法356. 回溯法回溯法* 通过对问题的分析，找出一个解决问题通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。换别的路线再进行试探。第1章 算法361.4 算法的

27、复杂度分析算法的复杂度分析1.4.1 1.4.1 算法的时间复杂度算法的时间复杂度1.4.2 1.4.2 算法的空间复杂度算法的空间复杂度第1章 算法37 指执行算法所需要的计算工作量指执行算法所需要的计算工作量. .用算法在用算法在执行过程中所需基本运算的执行次数来度量执行过程中所需基本运算的执行次数来度量算法的工作量。算法的工作量。 算法的工作量用算法所执行的基本运算次算法的工作量用算法所执行的基本运算次数来度量而算法所执行的基本运算次数是问数来度量而算法所执行的基本运算次数是问题规模的函数。题规模的函数。 算法的工作量算法的工作量f(n)f(n) 其中其中n n是问题的规模。是问题的规模

28、。1.4.1 算法的时间复杂度算法的时间复杂度第1章 算法381. 平均性态平均性态(Average Behavior)nDx) x( t ) x( p) n (A平均性态指用各种特定的数如下的基本运算平均性态指用各种特定的数如下的基本运算次数的带权平均值来度量算法的工作量。次数的带权平均值来度量算法的工作量。 Dn: 表示算法规模为表示算法规模为n是，算法执行时所有可能是，算法执行时所有可能 输入的集合。输入的集合。 t(x): 在输入为在输入为x时所执行的基本运算次数。时所执行的基本运算次数。 p(x): 是是x 出现的概率。出现的概率。第1章 算法392. 最坏情况复杂性最坏情况复杂性

29、(Worst(WorstCase Complexity)Case Complexity)指在规模为指在规模为n n时，算法所执行的基本运算的最大次数。时，算法所执行的基本运算的最大次数。)x( tmax)n(WnDx第1章 算法40例例采用顺序搜索法，在长度为采用顺序搜索法，在长度为n n的一维数组中查找为的一维数组中查找为x x的元素。即从数组的第一个元素开始，逐个与被查的元素。即从数组的第一个元素开始，逐个与被查值值x x进行比较。进行比较。基本运算为基本运算为x x与数组元素的比较。与数组元素的比较。第1章 算法41平均性态分析平均性态分析第1章 算法42最坏情况分析最坏情况分析 W(n)W(n)maxtmaxti i | 1in | 1in11n n第1章 算法431.4.2 算法的空间复杂度算法