《电子教案第1章》由会员分享，可在线阅读，更多相关《电子教案第1章（54页珍藏版）》请在金锄头文库上搜索。
1、计算机软件技术基础,新世纪计算机基础教育丛书 主编 谭浩强,第1章 算 法,1.1 算法的基本概念 1.2 算法描述语言 1.3 算法设计基本方法 1.4 算法的复杂度分析,1.1 算法的基本概念,1.1.1 算法的基本特征 1.1.2 算法的基本要素,1.1 算法的基本概念,1.1.1 算法的基本特征 算法是指解题方案的准确而完整的描述。 1.能行性(effectiveness) A1012，B1，C1012 ABC10121(1012)0 ACB1012(1012)11 2.确定性(definiteness) 3.有穷性(finiteness) 4.拥有足够的情报,算法是一组严谨地定义运算
2、顺序的规则， 并且每一个规则都是有效的，且是明确的， 此顺序将在有限的次数下终止。,1.1.2 算法的基本要素 (1) 算法中对数据的运算和操作 算术运算 逻辑运算 关系运算 数据传输 (2) 算法的控制结构,1.2 算法描述语言,1.符号与表达式 loop：ii1 “设x是A中的最大项”（其中A是一个数组） “将x插入到L之中”（其中L是某个表） 关系运算符用、 逻辑运算符用and(与)、or(或)、not(非),2.赋值语句 ae ab abe,3.控制转移语句 无条件转移语句 GOTO 标号 条件转移语句 IF C THEN S 或 IF C THEN S1 ELSE S2,4.循环语句
3、 WHILE语句 WHILE C DO S 功能等价于如下的IF语句： loop：IF C THEN S GOTO loop ,FOR语句 FOR iinit TO limit BY step DO S FOR iinit TO limit DO S 当step0时，功能等价于如下的IF语句： iinit loop：IF ilimit THEN S iistep GOTO loop ,当step0时，功能等价于如下的IF语句： iinit loop：IF ilimit THEN S iistep GOTO loop ,5.其他语句 EXIT READ（或INPUT） WRITE（或PRINT，
4、或OUTPUT）,1.3 算法设计基本方法,1. 列举法 根据提出的问题，列举所有可能的情况，并用问题 中给定的条件检验哪些是需要的，哪些是不需要的。 因此，列举法常用于解决“是否存在”或“有多少种可 能”等类型的问题，例如求解不定方程的问题。,例 设每只母鸡值3元，每只公鸡值2元，两只小鸡值1 元。现要用100元钱买100只鸡，设计买鸡方案。 假设买母鸡I只，公鸡J只，小鸡K只。,FOR I0 TO 100 DO FOR J0 TO 100 DO FOR K0 TO 100 DO MIJK N3I2J0.5K IF (M100)and(N100) THEN OUTPUT I，J，K RETU
5、RN 总循环次数为1013,FOR I0 TO 33 DO FOR J0 TO 501.5I DO K100IJ IF (3I2J0.5K100) THEN OUTPUT I，J，K RETURN 总循环次数为,#include “stdio.h“ main() int i，j，k； for (i0； i33； i) for (j0； j501.5*i； j) k100ij； if (3*i2*j0.5*k100.0) printf(“%5d%5d%5dn“，i，j，k)； ,运行结果如下： 2 30 68 5 25 70 8 20 72 11 15 74 14 10 76 17 5 78 2
6、0 0 80,2. 归纳法 通过列举少量的特殊情况，经过分析，最后找出一般的关系。 3. 递推 从已知的初始条件出发，逐次推出所要求的各中间结果和最 后结果。,例,4. 递归 将一个复杂的问题归结为若干个较简单的问题，然 后将这些较简单的每一个问题再归结为更简单的问 题，这个过程可以一直做下去，直到最简单的问题 为止。,例 编写一个过程，对于输入的参数n，依次打印输出自然数1到n。 PROCEDURE WRT(n) FOR k1 TO n DO OUTPUT k RETURN #include “stdio.h“ wrt(int n) int k； for (k1；kn；k) printf(“
7、%dn“，k)； return； ,输出自然数1到n的递归算法。 PROCEDURE 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； ,5. 减半递推技术 所谓“减半”，是指将问题的规模减半，而问题的性质不变。 所谓“递推”，是指重复“减半”的过程。,例 二分法求方程实根的减半递推过程： 首先取给定区间的中点c(ab)/2。 然后判断f(c)是否为0。 若f(c)0,则说明c即为所求的根，求解过程结束；
8、 如果f(c)0,则根据以下原则将原区间减半： 若f(a)f(c)0，则取原区间的前半部分； 若f(b)f(c)0，则取原区间的后半部分。 最后判断减半后的区间长度是否已经很小： 若|ab|，则过程结束，取(ab)/2为根的近似值； 若|ab|，则重复上述的减半过程。,FUNCTION ROOT(a，b，eps，f) f0f(a) WHILE (|ab|) DO c(ab)/2； f1f(c) IF (f10) THEN ROOTc ；RETURN IF (f0*f10) THEN ac ELSE bc c(ab)/2；ROOTc RETURN,#include “stdio.h” #incl
9、ude “math.h” double root(a，b，eps，f) double a，b，eps，(*f)()； double f0，f1，c； f0(*f)(a)； while (fabs(ab)eps) c(ab)/2； f1(*f)(c)； if (f10) return(c)； if (f0*f10) ac； else bc； c(ab)/2； return(c)； ,6. 回溯法 通过对问题的分析，找出一个解决问题的线索，然 后沿着这个线索逐步试探，对于每一步的试探，若 试探成功，就得到问题的解，若试探失败，就逐步 回退，换别的路线再进行试探。,例 求解皇后问题。 由n2个方块排
10、成n行n列的正方形称为“n元棋盘”。如 果两个皇后位于棋盘上的同一行或同一列或同一对 角线上，则称它们为互相攻击。 现要求找使n元棋盘上的n个皇后互不攻击的所有布 局。,假设棋盘上的每一行放置一个皇后，分别用自然数进行编号 为1，2，n。 首先定义一个长度为n的一维数组q，其中每一个元素qi （i1，2，n）随时记录第i行上的皇后所在的列号。 初始时，先将各皇后放在各行的第1列。即数组q的初值为 qi1，i1，2，n 第i行与第j行上的皇后在某一对角线上的条件为 |qiqj|ij| 而它们在同一列上的条件为 qiqj,回溯法的步骤如下： 从第一行（即i1）开始进行以下过程： 设前i1行上的皇后
11、已经布局好，即它们均互不攻 击。 现在考虑安排第i行上的皇后的位置，使之与前 i1行上的皇后也都互不攻击。 为了实现这一目的，可以从第i行皇后的当前位置 qi开始按如下规则向右进行搜索：,若qin1，将第i个皇后放在第1列（即置qi1），且回退一行，考虑重新安排第i1行上的皇后与前i2行上的皇后均互不攻击的下一个位置。此时如果已退到第0行（实际没有这一行），则过程结束。 若qin，则需检查第i行上的皇后与前i1行的皇后是否互不攻击。若有攻击，则将第i行上的皇后右移一个位置（即置qiqi1），重新进行这个过程；若无攻击，则考虑安排下一行上的皇后位置，即置ii1。 若当前安排好的皇后是在最后一行（
12、即第n行），则说明已经找到了n个皇后互不攻击的一个布局，将这个布局输出（即输出qi，i1，2，n）。然后将第n行上的皇后右移一个位置（即置qnqn1），重新进行这个过程，以便寻找下一个布局。,回溯法求解皇后问题。 PROCEDURE QUEEN(n) 定义长度为n的数组存储空间q。 FOR i1 TO n DO qi1 i1 loop: IF (qin) THEN k1 WHILE (ki)and(qkqi)*(|qkqi|ki|)0) DO kk1 IF (ki) THEN qiqi1,ELSE ii1 IF (in) THEN OUTPUT qi(i1，2，n) qnqn1 in ,ELS
13、E qi1 ii1 IF (i1) THEN RETURN qiqi1 GOTO loop RETURN,#include “stdio.h“ #include “math.h“ #include “stdlib.h“ void queen(int n) int i，j，k，jt，*q； qmalloc(n*sizeof(int)； for (i0； in； i) qi0； i0； jt1； printf(“n“)； printf(“%d queen problemn“，n)；,while(jt1) if (qin) k0； while (ki)&(qkqi)* (fabs(qkqi)fabs
14、(ki)!0) kk1； if (ki) qiqi1； else ii1； if (in1) for(j0；jn；j) printf(“%5d“，qj1)；,printf(“n“)； qn1qn11； in1； else qi0； ii1； if (i0) printf(“n“)； free(q)； return； qiqi1； ,1.4 算法的复杂度分析,1.4.1 算法的时间复杂度 1.4.2 算法的空间复杂度,1.4.1 算法的时间复杂度 指执行算法所需要的计算工作量 算法的工作量f(n),1. 平均性态(Average Behavior),2. 最坏情况复杂性 (WorstCase Complexity),例 采用顺序搜索法，在长度为n的一维数组中查找为x 的元素。即从数组的第一个元素开始，逐个与被查 值x进行比较。 基本运算为x与数组元素的比较。,平均性态分析,最坏情况分析 W(n)maxti | 1in1
