第1章南财数据智能化课件.ppt

1、计算机软件技术基础（第计算机软件技术基础（第4 4版）版）王晓庆QQ: 26445100Office:8671-8170Mobile: 189-5199-5050Email: 第第1章章 预备知识预备知识1.1 集合1.2 算法1.1.1 集合及其基本性质1.1.2 自然数集与数学归纳法1.1.3 笛卡尔积1.1.4 二元关系31.1.1 集合及其基本性质 1. 集合的基本概念 所谓集合，是指若干个或无穷多个具有相同属性的元（元素）的集体。 通常，一个集合名称用大写字母表示，而集合中的某个元素用小写字母表示。45678一个集合，通常用以下两种方法表示。 (1) 列举法 用列举法表示一个集合是将

2、此集合中的元素全部列出来，或者列出若干项但能根据规律可知其所有的元素。例如9大于1而小于100的所有整数的集合可以表示为 A 2，3，4，99 ，有限集所有整数构成的集合可以表示为 Z 0，1，2，3，无限集空集表示为 ，空集10 (2) 性质叙述法 用性质叙述法表示一个集合是将集合中的元素所具有的属性描述出来。例如：11大于1而小于100的所有整数的集合可以表示为 A a|1a100的所有整数 所有整数构成的集合可以表示为 Zz |z为一切整数 大于0而小于1的所有实数构成的集合可以表示为 B b|0b1的所有实数 所有实数构成的集合可以表示为 Rr |r为一切实数 1213 2. 集合的基

3、本运算(1) 两个集合的并（union）设有两个集合M和N，它们的并集记作MN，其定义如下： 即两个集合M与N的并集是指M与N中的所有元素（去掉重复的元素）组成的集合。14(2) 两个集合的交（intersection）设有两个集合M和N，它们的交集记作MN，其定义如下： 即两个集合M与N的交集是指M与N中所有共同元素组成的集合。15两个集合与的并、交均满足交换律，即 MNNM MNNM 16(3) 两个集合的差（difference） 设有两个集合M和N，M和N的差集记作MN，其定义如下： MN |M但不属于N 两个集合的差不满足交换律，即 MNNM17 例 设集合 Aa，b，c，d，e B

4、d，e，f，g，h 则 ABa，b，c，d，e，f，g，h AB d，e ABa，b，c BAf，g，h 18基本性质：(1) 结合律 (AB)CA(BC) (AB)CA(BC)(2) 分配律 A(BC)(AB)(AC) A(BC)(AB)(AC)(3) (AB)(BA)(AB)(AB)(4) B(AB) (AB)(AB)A193. 映射2021222324251.1.2 自然数集与数学归纳法26由所有自然数所组成的集合由所有自然数所组成的集合 1 1，2 2，3 3， 称为自然数集。自然数集是一个无限集。称为自然数集。自然数集是一个无限集。由自然数组成的集合均是自然数集的子集。由自然数组成的

5、集合均是自然数集的子集。自然数集的子集可以是有限集，也可以是无限集。自然数集的子集可以是有限集，也可以是无限集。27与自然数集对等（即具有相等浓度）的集合称为可列集（或可数集）。任一可列集中的元素排列时可标以正整数下标，即任意可列集均可写成28定理：在自然数集的任一非空子集M中，必定有一个最小数。即在集合M中有不大于其它任意数的数。2930定理：设M是由自然数形成的集合，如果它含有1，2，k，并且当它含有数n1，n2，nk（nk）时，也含有数n，那么它含有所有的自然数，即M是自然数集。3132为了证明一个命题对于所有的自然数是真，采用数学归纳法证明的步骤如下：(1) 证明命题对于自然数1，2，

6、k是真的；(2) 假设命题对于自然数nk，nk1，n1（nk）是真的（这一步称为归纳假设）；(3) 证明命题对于自然数n也是真的。33例 证明下列命题： 对于任意的自然数n，必存在一对非负整数(i，j )有 7n3i5j34证明：(1) 当n1时，有7135，即i1，j1。命题成立。 当n2时，有723350，即即i3，j0。命题成立。 当n3时，有733052，即即i0，j2。命题成立。(2) 假设命题对于自然数n1，n2，n3（n3）成立（归纳假设）。(3) 考虑自然数n，有 7n7(n3)3根据归纳假设，对于自然数n3命题成立，设存在一对非负整数I，J有 7(n3)3I5J则有 7n7(

7、n3)33(I1)5J3i5j其中iI1，jJ均为非负整数。即对于自然数n命题也成立。 由此得出结论，对于所有的自然数n命题成立。351.1.3 笛卡尔积3637381.1.4 二元关系39404142434445461.2.1 算法的基本特征1.2.2 算法设计基本方法1.2.3 算法的复杂度分析1.2.1 算法的基本概念算法的基本概念 算法是指解题方案的准确而完整的描述。1.能行性(effectiveness) A1012，B1，C1012 ABC10121(1012)0 ACB1012(1012)112.确定性(definiteness)3.有穷性(finiteness)4.拥有足够的情

8、报算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的，且是明确的，此顺序将在有限的次数下终止。1.2.2 算法设计基本方法算法设计基本方法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 N3I

9、2J0.5K IF (M100)and(N100) THEN OUTPUT I，J，K RETURN总循环次数为1013 FOR I0 TO 33 DO FOR J0 TO 501.5I DO K100IJ IF (3I2J0.5K100) THEN OUTPUT I，J，K RETURN总循环次数为894) I5 . 151(330I #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)；

10、运行结果如下： 2 30 68 5 25 70 8 20 72 11 15 74 14 10 76 17 5 78 20 0 802. 归纳法归纳法通过列举少量的特殊情况，经过分析，最后找出一般的关系。3. 递推递推从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。例1,20,21,30n,I51n51I1In1n304. 递归递归将一个复杂的问题归结为若干个较简单的问题，然后将这些较简单的每一个问题再归结为更简单的问题，这个过程可以一直做下去，直到最简单的问题为止。例编写一个过程，对于输入的参数n，依次打印输出自然数1到n。 PROCEDURE WRT(n) FOR k1 TO n

11、 DO OUTPUT k RETURN #include stdio.h wrt(int n) int k； for (k1；kn；k) printf(%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. 减半递推技术减半递推技术所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。62312

12、242215312754111xxxxcxxcxxcxxxxc例二分法求方程实根的减半递推过程：首先取给定区间的中点c(ab)/2。然后判断f(c)是否为0。 若f(c)0,则说明c即为所求的根，求解过程结束； 如果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(

13、c) IF (f10) THEN ROOTc ；RETURN IF (f0*f10) THEN ac ELSE bc c(ab)/2；ROOTc RETURN#include stdio.h”#include 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. 回溯法回溯法通过对

14、问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。例求解皇后问题。由n2个方块排成n行n列的正方形称为“n元棋盘”。如果两个皇后位于棋盘上的同一行或同一列或同一对角线上，则称它们为互相攻击。现要求找使n元棋盘上的n个皇后互不攻击的所有布局。假设棋盘上的每一行放置一个皇后，分别用自然数进行编号为1，2，n。首先定义一个长度为n的一维数组q，其中每一个元素qi（i1，2，n）随时记录第i行上的皇后所在的列号。初始时，先将各皇后放在各行的第1列。即数组q的初值为 qi1，i1，2，n第i行与第j行

15、上的皇后在某一对角线上的条件为 |qiqj|ij|而它们在同一列上的条件为 qiqj回溯法的步骤如下：从第一行（即i1）开始进行以下过程：设前i1行上的皇后已经布局好，即它们均互不攻击。现在考虑安排第i行上的皇后的位置，使之与前i1行上的皇后也都互不攻击。为了实现这一目的，可以从第i行皇后的当前位置qi开始按如下规则向右进行搜索：若qin1，将第i个皇后放在第1列（即置qi1），且回退一行，考虑重新安排第i1行上的皇后与前i2行上的皇后均互不攻击的下一个位置。此时如果已退到第0行（实际没有这一行），则过程结束。若qin，则需检查第i行上的皇后与前i1行的皇后是否互不攻击。若有攻击，则将第i行上

16、的皇后右移一个位置（即置qiqi1），重新进行这个过程；若无攻击，则考虑安排下一行上的皇后位置，即置ii1。若当前安排好的皇后是在最后一行（即第n行），则说明已经找到了n个皇后互不攻击的一个布局，将这个布局输出（即输出qi，i1，2，n）。然后将第n行上的皇后右移一个位置（即置qnqn1），重新进行这个过程，以便寻找下一个布局。回溯法求解皇后问题。PROCEDURE QUEEN(n)定义长度为n的数组存储空间q。FOR i1 TO n DO qi1i1loop: IF (qin) THEN k1 WHILE (ki)and(qkqi)*(|qkqi|ki|)0) DO kk1 IF (ki)

17、THEN qiqi1 ELSE ii1 IF (in) THEN OUTPUT qi(i1，2，n) qnqn1 in ELSE qi1 ii1 IF (i1) THEN RETURN qiqi1 GOTO loopRETURN#include stdio.h#include math.h#include stdlib.hvoid 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)

18、 if (qin) k0； while (ki)&(qkqi)* (fabs(qkqi)fabs(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. 算法的时间复杂度算法的时间复杂度 指执行算法所需要的计算工作量 算法的工作量f(n)1. 平均性态平均性态(Average Behavior)nDx)x( t )x(p)n(A2. 最坏情况复杂性最坏情况复杂性 (WorstCase Complexity)x( t max)n(WnDx例采用顺序搜索法，在长度为n的一维数组中查找为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。平均性态分析最坏情况分析 W(n)maxti | 1in1n2. 算法的空间复杂度算法的空间复杂度 执行算法所需要的内存空间。 in place