资源描述
C程序设计语言,第2章算法,本章主要内容,2.1算法的概念及简单算法举例2.2算法的特性2.3怎样表示一个算法2.4结构化程序设计方法,2.1算法(Algorithm),算法解决问题的方法算法是程序的灵魂程序(Program)对算法的具体实现程序的效率不可能超过算法的限制NikiklausWirth程序数据结构算法,数据结构算法程序设计方法语言工具,完整的程序设计应该是:,算法1：1+2+3+4+.+100S1:1+2，得到结果3；S2:将步骤1得到的和再加3，得结果6；S3:将6再加上4得10；.S99:将上一步的结果再加上100，得最终结果5050上述算法共需要求和99次,例2.1：求,这是最简单的算法,如果n从1到1万怎么办？,算法2：100+(1+99)+(2+98)+(49+51)+50按照等差数列求和公式：sum=(首项+尾项)*项数)/2只需要进行一次加法，一次乘法和一次除法即可，大大节省了运行时间！,算法的重要性,同样的问题，有的人写出一段程序也许要几天几夜能得到结果，而有的人写的程序也许仅仅需要几分钟而已！,人和人之间的差距咋就这么大呢？,例2.2求,算法如下：,S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)signS5：term=sign(1/deno)S6：sum=sum+termS7：deno=deno+1S8：若deno100返回S4，否则算法结束。,单词作变量名，以使算法更易于理解：sum表示累加和，deno是英文分母（denominator）缩写，sign代表数值的符号，term代表某一项。,反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是多项式的值。,2.2算法的特性,有穷性：包含有限的操作步骤。(必须存在循环结束条件）确定性：算法中的每一个步骤都应当是确定的。有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信息。有一个或多个输出：算法的目的是为了求解，“解”就是输出。有效性：算法中的每一个步骤都应当能有效地执行，并得到确定的结果。,一个算法应该具有以下特点：,2.3算法的表示,可以用不同的方法表示算法，常用的有：自然语言传统流程图结构化流程图伪代码用计算机语言表示算法,2.3.2用流程图表示算法,美国国家标准化协会ANSI(AmericanNationalStandardInstitute)规定了一些常用的流程图符号：,将例算法2.1的算法1用流程图表示,将例2.2的算法用流程图表示,流程图的特点,流程图是表示算法的较好的工具。一个流程图包括以下几部分：(1)表示相应操作的框；(2)带箭头的流程线；(3)框内外必要的文字说明。,三种基本算法结构,顺序结构选择结构（分支结构）循环结构（重复结构）当型循环（While型循环）直到型循环（Until型循环）,选择结构,当p为“真”,当p为“假”,if(xy),z=x,z=y,输出z,循环结构,A,a,b,p1,Y,While型循环,N,当p1为“真”,当p1为“假”,A,a,b,p2,N,Until型循环,Y,当p2为“真”,当p2为“假”,两种循环结构的比较,While型循环,Until型循环,两个循环结构的判断条件相反,A一次也没有执行,A执行了一次,当首次判断p即为“假”(!p为“真”),当执行一次A后，判断p为“假”(!p为“真”),A执行了一次,三种基本算法结构的共同特点,(1)只有一个入口。(2)只有一个出口(3)结构内的每一部分都有机会被执行到。(4)结构内不存在“死循环”(无终止的循环)。,2.3.5用计算机语言表示算法,#includevoidmain()intsum=0;inti=0;intmax_num=0;printf(InputMaxNumber:n);scanf(%d,将例2.1的算法1用C语言表示,2.3.5用计算机语言表示算法,将例2.1的算法2用C语言表示,#includevoidmain()intsum=0;inti=0;intmax_num=0;printf(InputMaxNumber:n);scanf(%d,2.4结构化程序设计方法,结构化算法由基本结构顺序组成的算法结构结构化程序设计方法自顶向下逐步细化模块化设计结构化编码,课外知识简介-软件设计方法,所有的模块都在最后集成，一旦出现错误不容易查找！也许会出现半年开发、半年集成的局面。,软件设计方法,模块化设计方法,持续集成（敏捷开发）,敏捷式开发（目前各大公司推崇）,这是一种边开发边集成的方式，每个月或每半个月集成一次，此开发方式能尽早发现问题并解决问题一般每天生成一个小版本，每个月生成一个大版本。敏捷式开发方式如果某天的测试发现了问题，存在Bug，最多只推到前一天的版本，而不是像模块化开发那样，需要对半年以前的代码进行测试。,版本控制说明,软件开发的版本控制问题,A、B、C、D、E、F六人共同开发一个系统软件，A、B、C三人的模块彼此耦合不大，可以相互独立进行，而D、E、F三人共同开发一个大的模块，彼此之间相关程度很大。三个人的代码如何整合呢？,版本控制软件：SVN和clearcase（收费）,D编写好软件,上传至服务器（版本0）,E下载至本地本地版本为0,F下载至本地本地版本为0,E首先编写完代码，将代码上传至服务器SVN发现服务器版本和本地一致可以直接上传，并将服务器版本改为1,F将代码上传至服务器SVN发现本地版本与服务器版本不一致，会提示冲突并显示。F手动merge，服务器版本号变为2,版本控制流程,软件测试,敏捷式开发带来的一个问题是：测试工作量大大增加开发人员写一部分代码进行单元测试（UT），这里的测试不采用专门的软件，一般写一段辅助程序进行测试。测试人员对于上传到服务器上的代码，采用自动化测试（AT）的方法，每天下班之前进行测试，第二天早晨就会有结果，确定前一天的开发是否引入了新的问题。一个模块完成后进行功能性测试（FT）模块中加入了新功能要进行回归测试（RT）系统的多个模块整合在一起后进行系统测试（ST）,现在的工程基本上要由很多人共同来完成，公司需要对所有程序开发人员的编程风格进行统一。因此要对每个人进行codingstyle测试，如果编程风格不符合要求，就无权上传代码，直到符合要求为止。就会出现这样一种情况，即虽然在测试的时候通过了，但以后编写代码还按照原来的风格编写，公司对这种情况会如何处理呢？,对程序员编程风格的要求,codereview！,本章小结,1.理解算法的概念：程序的灵魂所在,2.重点掌握算法的两种表示方法：流程图和计算机语言。,
展开阅读全文