第1章软件学基本知识

软件学基础王东洋电气工程学院教学大纲课程的性质软件学基础主要研究程序设计中的数据结构及其算法、数据库技术、软件开发技术，是电建专业必修的一门学科基础课。课程的目的通过本课程的学习，使学生掌握和理解常用算法与数据结构、数据库技术、开发软件的一般方法。教学任务包括软件学基本知识、基本数据结构及算法、查找与排序算法、数据库技术、应用软件设计与开发技术。课程成绩最终成绩=0.8*（0.3*平时成绩+0.7*考试成绩）+0.2*实验成绩第一章算法1.1算法的基本概念算法是解题方案的准确而完整的描述。一、算法的基本特征能行性(effectiveness)算法中的每一个步骤必须能够实现；算法执行的结果能够达到预期的目的。确定性(definiteness)算法中的每一个步骤都必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。有穷性(finiteness)算法必须能在有限的时间内做完，即算法必须能执行有限个步骤之后终止。输入一个算法应该有零个或多个输入。输出一个算法应该有一个或多个输出。算法是一组严谨地定义运算顺序的规则，并且每一个规则都是有效的和明确的，此运算顺序将在有限的次数下终止。二、算法的基本要素算法中对数据的运算和操作：算术运算：加、减、乘、除等运算；逻辑运算：与、或、非等运算；关系运算：大于、小于、等于、不等于等运算；数据传输：赋值、输入、输出等操作。算法的控制结构：算法的控制结构：是指算法中各操作之间的执行顺序；构成算法的基本控制结构有：顺序、选择和循环三种。三、算法的描述算法：是指在一有限的时间内，解决某一个问题的一系列逻辑步骤。当问题被确定后，可以把问题分成若干个部分，针对每个部分先写出其算法描述。这里的每部分可以视为子程序，子程序间的调用可以由主程序或其他子程序调用。在编写一个算法时，可以采用自然语言、流程图、计算机语言或是专门为描述算法而设计的语言描述。例1-1.存在一个长度为n的字符串，串中元素互不相同。编写一算法，确定字符e在字符串中的位置。1.分析：现在对这个例子进行分析，把字符串看成一个序列，结点类型为字符型。选用顺序存储方式表示，采用数组A[n]存储这个字符串，用i表示e在数组的位置。结果就可能有以下情况，找到了e字符的位置，返回值i，i即为字符e的位置；还有一种可能就是不存在e这个字符，同样也要返回值i=0。2.用自然语言表示：(1)给i赋初始值为1；(2)若字符串中的第i字符为e，则输出i的值，即得最终结果，结束；(3)若i大于n时，仍未找到e，则字符串中没有e这个字符，结束；(4)i自增1；(5)重复步骤（2）（3）（4）。3.用流程图用流程图表示，如下图所示：4.C语言来描述Search(charA[]，intn){inti；for(i=1;i=n;i++)if(A[i]=='e‘)return(i);/*找到返回i*/elsereturn(0);/*未找到，返回0*/}1.2算法设计基本方法一、列举法基本思想：根据提出的问题，列举所有可能的情况，并用问题中给定的条件检验哪些是需要的，哪些是不需要的。应用场合：常用于解决“是否存在”或“有多少种可能”等类型的问题。特点：算法比较简单，但当列举的情况较多时，执行列举算法的工作量将会很大。实现列举法的循环控制有两种：计数法：首先确定循环次数，然后逐次测试，完成测试后循环结束。标志法：达到某一目标后，循环结束。例1-2公鸡每只三元，母鸡每只两元，小鸡每两只一元。用一百元买一百只鸡，问公鸡、母鸡和小鸡各有几只？分析：假设买母鸡i只，公鸡j只，小鸡k只。根据题意，粗略的列举算法如下。#includestdio.hmain(){inti,j,k;for(i=0;i=100;i++)for(j=0;j=100;j++)for(k=0;k=100;k++){if((i+j+k==100)&&(3*i+2*j+0.5*k==100.0))printf(“%5d%5d%5d\n”,i,j,k);}}算法优化后：#includestdio.hmain(){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)printf(“%5d%5d%5d\n”,i,j,k);}}算法1：总循环次数为1013。算法2：总循环次数为894。二、归纳法基本思想：通过列举少量的特殊情况，经过分析，最后找出一般的关系。归纳法要比列举法更能反映问题的本质，并且可以解决列举量为无限的问题。但是，从一个实际问题中总结归纳出一般的关系，并不是一件容易的事情，尤其是要归纳出一个数学模型更为困难。三、递推法基本思想：从已知的初始条件出发，逐次推出所要求的各中间结果和最后结果。应用场合：常用于数值计算。递推计算必须具备的两个条件：初值和递推公式。利用递推公式逐次迭代，直到问题求解。例1-3求整数n的阶乘n!的函数？(假设n≥1)解：1.分析：1!→2*1!→3*2!→……→n*(n-1)!2.源程序：四、递归法基本思想：将问题逐层分解，最后归结为一些最简单的问题。在问题逐层分解的过程，实际上并没有对问题进行求解，而只是当解决了最后那些最简单的问题后，才沿着原来分解的逆过程逐步进行综合，这就是递归的基本思想。特点：程序结构清晰，可读性强；应用场合：常用解决一些较复杂的问题；递归算法的程序实现：通过函数的递归调用来实现，即一个函数直接或间接地调用自身。例1-4基于以下数学模型求n!#includestdio.hfloatfun(intn){floatf;if(n0)printf(n0,dataerror!);elseif(n==0||n==1)f=1;elsef=fun(n-1)*n;return(f);}五、减半递推法所谓“减半”，是指将问题的规模减半，而问题的性质不变。所谓“递推”，是指重复“减半”的过程。例1-5设方程f(x)=0在区间[a，b]上有实根，且f(a)与f(b)异号。利用二分法求该方程在区间[a，b]上的一个实根？解：1.分析二分法求方程实根的减半递推过程如下：首先取给定区间的中点c=(a+b)/2。然后判断f(c)是否为0。若f(c)=0，则说明c即为所求的根，求解过程结束；如果f(c)≠0，则根据以下原则将原区间减半；若f(a)f(c)0，则取原区间的前半部分；若f(b)f(c)0，则取原区间的后半部分。最后判断减半后的区间长度是否已经很小。若Ia-blε，则过程结束，取(a+b)/2为根的近似值；若|a-b|≥ε，则重复上述的减半过程。while(abs(a-b)ɛ){c=(a+b)/2;if(f(c)==0)return(c);elseif(f(c)*f(a)0)b=c;elsea=c;}return((a+b)/2);六、回溯法基本思想：通过对问题的分析，找出一个解决问题的线索，然后沿着这个线索逐步试探，对于每一步的试探，若试探成功，就得到问题的解，若试探失败，就逐步回退，换别的路线再进行试探。应用场合：常用于处理复杂数据结构。1.3算法的复杂度分析算法的复杂度主要包括时间复杂度和空间复杂度。一、算法的时间复杂度算法的时间复杂度：是指执行算法所需要的计算工作量。为了能够比较客观地反映出一个算法的效率，在度量一个算法的工作量时，不仅应该与所使用的计算机、程序设计语言以及程序编制者无关，而且还应该与算法实现过程中的许多细节无关。在算法分析工作中通常粗略地将算法中语句执行的最大次数作为算法时间的度量，而不是计算出它的具体时间。算法的工作量用算法所执行的基本运算次数来度量，而算法所执行的基本运算次数是问题规模的函数，即算法的工作量＝f(n)。其中n是问题的规模。例如，两个n阶矩阵相乘所需要的基本运算(即两个实数的乘法)次数为n3，即计算工作量为n3，也就是时间复杂度为n3。在具体分析一个算法的工作量时，还会存在这样的问题：对于一个固定的规模，算法所执行的基本运算次数还可能与特定的输入有关，而实际上又不可能将所有可能情况下算法所执行的基本运算次数都列举出来。在同一问题规模下，如果算法执行所需的基本运算次数取决于某一特定输入时，可以用以下两种方法来分析算法的工作量。2.最坏情况复杂性(worst-casecomplexity)最坏情况分析：是指在规模为n时，算法所执行的基本运算的最大次数。它定义为W(n)=max{t(x)}x∈Dn显然，W(n)的计算要比A(n)的计算方便得多。由于W(n)实际上是给出了算法工作量的一个上界，因此，它比A(n)更具有实用价值。例1-7采用顺序搜索法，在长度为n的一维数组中查找值为x的元素。即从数组的第一个元素开始，逐个与被查值x进行比较。基本运算为x与数组元素的比较。分析算法复杂度的平均性态和最坏情况。分析算法的最坏情况在这个例子中，最坏情况发生在需要查找的x是数组中的最后一个元素，或x不在数组中的时候，此时显然有二、算法的空间复杂度算法的空间复杂度：是指执行这个算法所需要的内存空间。一个算法所占用的存储空间包括算法程序所占的空间、输入的初始数据所占的存储空间以及算法执行过程中所需要的额外空间。时间与空间是一对矛盾，要节约空间往往就要消耗较多时间，反之亦然。目前，由于计算机硬件的发展，一般都有足够的内存空间，因此在今后的算法分析中着重考虑时间的因素。