武汉理工大学C语言-第2章-算法2015

主讲：袁小玲Email:[e-mail]进行程序设计，需要具备两方面知识：⑴掌握一门计算机语言⑵掌握解题的方法和步骤不论是计算机还是人，要完成一项工作都是按照一定的工作步骤进行的。例如，去徐东销品茂买东西，可以按照下面步骤进行：①到南校门；②乘709路公交车；③到“徐东一路”站点下车；进大厦买东西。又如，到食堂吃饭，一般按照以下步骤进行：①带上校园卡，走进食堂排队；②刷卡买饭；③刷卡买菜；④到餐桌吃饭。以上两个例子说明，无论完成什么任务，都有一定的方法和具体的步骤。算法(Algorithm)是为解决某个问题而采取的方法和步骤。这里我们所关心的只限于计算机算法，即计算机可以执行的算法。对于同一个问题可以采用不同的方法和步骤(即可以有不同的算法)，但应选择最佳的方案。1001kksum【例1】计算方法一：先进行1＋2、再加3、再加4、…、加到100为止。（做99次加法）方法二：100＋(1＋99)＋(2＋98)＋…＋(49＋51)＋50=100＋49×100＋50=5050。（1次乘法，2次加法）……此例说明：解决问题的算法有优劣之分。算法的优劣是程序设计中一个极为重要的问题，不仅要保证算法正确，而且要考虑算法的质量（方法简单、运算步骤少）。第二章算法与算法设计简介2.1算法的概念2.2算法的设计与表示2.3简单的算法实例2.4结构化程序设计方法简介算法的概念任何一个程序应包含如下两方面的内容：(1)对数据的描述。在程序中要指定数据的类型和数据的组织形式，即数据结构(datastructure).(2)对操作的描述。即操作步骤，也就是算法(algorithm)。著名计算机科学家沃思(NikiklausWirth)提出公式数据结构＋算法＝程序算法：解决一个问题而采取的方法和步骤，就称为算法。程序：从计算机的角度来讲，程序是用某种计算机能理解并执行的计算机语言描述解决问题的方法和步骤。1、什么叫算法？实际上，一个程序除了以上两个主要要素之外，还应当采用结构化程序设计方法进行程序设计，并且采用某一种计算机语言来表示。因此，可以这样概括：程序＝算法＋数据结构＋程序设计方法＋语言工具和环境在这4个方面中，语言是工具，数据结构是加工对象，而算法是灵魂，是解决“做什么”和“怎么做”的问题，而程序中的操作语句，实际上就是算法的体现。因此，应该养成编程之前先进行算法设计的好习惯。算法分类：数值运算算法和非数值运算算法。2、算法的特性（1）有穷性：一个算法应包含有限的操作步骤而不是无限的。例如：不能有死循环。（2）确定性：算法中的每一个步骤都应当是确定的，而不是含糊的，模棱两可的。例如，“100与一个整数相乘”是不确定的，它没有说明“这个整数”具体是多少。（3）有零个或多个输入：所谓输入是指在执行算法时需要从外界或取的必要信息。可以没有输入。例如求5！。（4）有一个或多个输出：算法的目的是为了求解，“解”就是输出。没有输出的算法是没有意义的。所以，至少有一个输出结果。（5）有效性算法中的每一个步骤都应当能有效地执行，并得到确定的结果。例如：假设B＝0，则A÷B就是无效的操作。3、算法的设计要求（1）正确性：算法应满足具体问题的需求。“正确”的含义可以分以下四个不同层次：程序不含语法错误，这是基本要求；程序对于几组输入数据能够得出满足规格说明要求的结果；程序对于精心挑选的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；程序对于一切合法的输入数据都能得出满足规格说明要求的结果。（2）可读性：算法设计的主要目的是为了阅读和交流。（3）健壮性：当输入非法数据时，算法能适当做出反应或进行处理，而不会出现莫名其妙的结果。（4）效率与存储量需求。效率指算法的执行时间；存储量指算法执行过程中需要的最大存储空间。4、算法复杂度算法复杂度，即算法在编写成可执行程序后，运行时所需要的资源，包括时间资源和内存资源。即时间复杂度和空间复杂度。同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。（1）算法的时间复杂度：是指执行算法所需要的计算工作量。一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n))称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。（2）算法的空间复杂度：是指算法在计算机内执行时所需存储空间的度量。记作:S(n)=O(f(n))，其中n为问题的规模。算法执行期间所需要的存储空间包括3个部分：算法程序所占的空间；输入的初始数据所占的存储空间；算法执行过程中所需要的额外空间。在某算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),例如{++X;S=0;}而for(j=1;j=n;j++){++X;S+=X;}的时间复杂度为O(n),for(j=1;j=n;j++)for(k=1;k=n;k++){++X;S+=X;}的时间复杂度为O(n2)。分别称为常量阶、线性阶和平方阶。算法还可能呈现的时间复杂度有对数阶、指数阶等。自然语言法：用人类语言或其他文字来描述解决问题的方法和步骤。优点：通俗易懂。缺点：文字冗长、繁琐，含义不严格，容易产生歧义。流程图：用一些图框来表示算法的步骤。包括：传统流程图、结构化流程图、N-S流程图三种。伪代码(pseudocode)法：用介于自然语言和计算机语言之间的文字和符号来描述算法。算法的设计与表示例1：计算5!（5!=1×2×3×4×5）约定：用s1、s2、…、sn表示算法的第1、2、…、第n步。实现思想：设A、B两个变量，其中A代表被乘数，B代表乘数。每一步的乘积结果存放在A中。另外，用循环表示每一步的乘积运算。具体算法如下：s1：使A=1（初值）s2：使B=2（初值）s3：A×BA（A与B的积存放于A中）s4：B＋1B（B的值增1）s5：如果B≤5，返回重新执行s3、s4、s5；否则，算法结束。（此时，A的值为5！。）1.自然语言表示的算法例2：有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用g代表学生成绩，gi代表第i个学生成绩，算法可表示如下：S1：1iS2：读入学号ni和成绩giS3:如果gi80，则打印ni和gi，否则不打印S4：i+1iS5:如果i50,返回S2，继续执行；否则，算法结束。由于自然语言容易出现“歧义性”，且描述问题的文字冗长，因此一般很少使用自然语言来描述算法。而是采用流程图来描述算法。ANSI规定了一些常用的流程图符号(见教材图2-1)。（1）传统流程图判断框起止框输入输出框处理框流程线或连接点注释框2.流程图表示的算法1001kksum思考1:计算思考2:计算N!例1：计算5!1A2BA×BAB+1BB﹥5?算法结束是否计算5!的算法示意图算法开始输出A算法开始输出A算法开始输出A算法开始例3：计算N!（N为任意正整数）。s1：输入Ns2：使A=1s3：使B=2s4：A×BAs5：B＋1Bs6：如果B≤N，返回重新执行s4、s5、s6；否则，A值为N!，输出A值，算法结束。输入N开始1A2BA×BAB＋1BBN?输出A是结束否一个流程图主要包括：⑴表示相应操作的图框；⑵带箭头的流程线；⑶图框内外相应的文字说明。传统流程图的优缺点优点：直观形象、图框间的逻辑关系清楚。缺点：对流程线的使用没有限制。因此，使用者可以不受限制地使流程任意地转来转去，使流程图变得毫无规律，使人难以理解算法的逻辑。结构化流程图基本思路：由基本结构构成算法流程图，只在基本结构内才存在分支和向前\向后的跳转，从而限制流程线的滥用。1966年，Bohra和Jacopini提出了三种基本结构：顺序结构、选择结构、循环结构。⑴顺序结构按流程线先后顺序执行算法中的各图框。（2）结构化流程图顺序结构示意图BA⑵选择结构根据判断框中的条件P是否成立选择执行A或B。注：A或B两个框中可以有一个是空，即不执行任何操作。选择结构示意图APB成立不成立AP⑶循环结构包括两种类型：当型循环、直到型循环。当型(While型)循环当型循环示意图成立P1循环体不成立当条件P1成立时，执行循环体；再判断条件P1，若成立，再执行循环体；…如此反复…；直到当条件P1不成立时，则退出循环结构。特点：①先判断后执行；②当条件P1成立时执行循环体，条件P1是执行循环的条件。直到型(Until型)循环直到型循环示意图成立P2循环体不成立先执行循环体；然后判断条件P2，若不成立，再执行循环体；然后再判断条件P2，若仍然不成立，则再执行循环体；…如此反复…；直到条件P2成立，则退出循环结构。特点：①先执行，后判断；②当条件P2不成立时执行循环体，条件P2成立时退出循环。条件P2是退出循环的条件。【例3】计算N!。直到型循环输入N开始1A2BA×BAB＋1BB≤N?输出A(N!)是结束否当型循环输入N开始1A2BA×BAB＋1BBN?输出A(N!)是结束否当型循环和直到型循环小结：1.当型循环是先判断后执行;直到型循环是先执行后判断。2.当型循环中条件P1是执行循环的条件，故条件成立时执行循环体；3.直到型循环中条件P2是退出循环的条件，故条件不成立时执行循环体。4.当型循环和直到型循环的条件P1和P2互为逆条件。5.当型循环中条件不成立时循环体不执行，而直到型循环的循环体至少执行一次。故，如果没有要求“至少执行一次循环体”时，最好选用当型循环。直到型循环示意图成立P2循环体不成立当型循环示意图成立P1循环体不成立基本结构小结三种基本结构的共同特点（1）有一个入口（2）有一个出口。（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混淆。）（3）结构中每一部分都应当有被执行到的机会。（4）没有死循环。选择结构示意图APB成立不成立图中没有一条从入口到出口的路径通过A框。不正确的流程表示：流程内的死循环小结：由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。（3）N-S流程图在结构化流程图基础上，1973年美国学者I.Nassi和B.Shneiderman提出了一种新的流程图形式，称为N-S流程图，又称盒图(boxdiagram)。在N-S流程图中，完全去掉了流程线，三种基本结构均用矩形框来表示。⑴顺序结构BABA⑵选择结构APB成立不成立P成立AB成立不⑶循环结构当型(While型)循环直到型(Until型)循环成立P1循环体不成立成立P2循环体不成立当P1循环体直到P2循环体【例3】计算N!（N为任意正整数）。输入N开始1A2BA×BAB＋1BB≤N?输出A(N!)是结束否A×BAB＋1B当B≤N2B1A输入N输出A（N!）N-S流程图的特点：没有起止框，没有流程线；其余流程图符号均以矩形框形式表示；在一个基本结构中还可以包含另一个基本结构3、用伪代码表示的算法伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。它不用图形符号，因此书写方便，格式紧凑，也比较好懂，便于向计算机语言算法（即程序）过渡。例2有50个学生，要求将他们之中成绩在80分以上者打印出来。用n表示学生学号，n1表示第一个学生学号，ni表示第i个学生学号。用g表示学生成绩，gi表示第i个学生成绩。BEGIN(算法开始)1=iWhilei=50{inputniandgii+1=i}-----------------------------------1=iWhilei=50{i