第2章 程序的算法精选文档.ppt

《第2章 程序的算法精选文档.ppt》由会员分享，可在线阅读，更多相关《第2章 程序的算法精选文档.ppt（30页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第第第2 2章章章章 程序的算法程序的算法程序的算法程序的算法本讲稿第一页，共三十页本章主要内容本章主要内容 2.1算法的概念及简单算法举例算法的概念及简单算法举例 2.2算法的特性算法的特性 2.3怎样表示一个算法怎样表示一个算法 2.4结构化程序设计方法结构化程序设计方法本讲稿第二页，共三十页2.12.1算法算法算法算法(Algorithm)(Algorithm)算法算法解决问题的方法解决问题的方法解决问题的方法解决问题的方法算法是程序的灵魂算法是程序的灵魂算法是程序的灵魂算法是程序的灵魂 程序程序(Program)对算法的具体实现对算法的具体实现对算法的具体实现对算法的具体实现程序的效

2、率不可能超过算法的限制程序的效率不可能超过算法的限制程序的效率不可能超过算法的限制程序的效率不可能超过算法的限制 Nikiklaus Wirth程序程序程序程序 数据结构数据结构数据结构数据结构 算法算法算法算法数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具完整的程序设计应该是:本讲稿第三页，共三十页算法算法1：1+2+3+4+.+100 S1:1+2，得到结果，得到结果3；S2:将步骤将步骤1得到的和再加得到的和再加3，得结果，得结果6；S3:将将6再加上再加上4得得10；.S99:将上一步的结果再加上将上一步的结果再加上100，得最终结果，得最终结果5050 上述算法共需

3、要求和上述算法共需要求和99次次例2.1：求本讲稿第四页，共三十页这是最简单的算法这是最简单的算法如果如果n从从1到到1万怎么办？万怎么办？本讲稿第五页，共三十页算法算法2：100+(1+99)+(2+98)+(49+51)+50 按照等差数列求和公式：按照等差数列求和公式：sum=(首项首项+尾项尾项)*项数项数)/2 只需要进行一次加法，一次乘法和一次除只需要进行一次加法，一次乘法和一次除法即可，大大节省了运行时间！法即可，大大节省了运行时间！本讲稿第六页，共三十页算法的重要性算法的重要性算法的重要性算法的重要性 同样的问题，有的人写出一段程序也许要几同样的问题，有的人写出一段程序也许要几

4、天几夜能得到结果，而有的人写的程序也许仅仅天几夜能得到结果，而有的人写的程序也许仅仅需要几分钟而已！需要几分钟而已！人和人之间的差距咋就这么大呢？人和人之间的差距咋就这么大呢？本讲稿第七页，共三十页例例2.22.2求求算法如下算法如下算法如下算法如下 ：S1S1S1S1：sign=1sign=1sign=1sign=1 S2 S2 S2 S2：sum=1sum=1sum=1sum=1 S3 S3 S3 S3：deno=2deno=2deno=2deno=2 S4S4S4S4：sign=(-1)signsign=(-1)signsign=(-1)signsign=(-1)sign S5 S5 S

5、5 S5：term=sign(1/deno)term=sign(1/deno)term=sign(1/deno)term=sign(1/deno)S6 S6 S6 S6：sum=sum+termsum=sum+termsum=sum+termsum=sum+term S7 S7 S7 S7：deno=deno+1deno=deno+1deno=deno+1deno=deno+1 S8 S8 S8 S8：若：若：若：若deno100deno100deno100deno100返回返回返回返回S4S4S4S4，否则算法结束。，否则算法结束。，否则算法结束。，否则算法结束。单词作变量名，以使算法更易于

6、理解：sum表示累加和，deno是英文分母（denominator）缩写，sign代表数值的符号，term代表某一项。反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是多项式的值。本讲稿第八页，共三十页 2.2 算法的特性算法的特性 有穷性：有穷性：有穷性：有穷性：包含有限的操作步骤。包含有限的操作步骤。包含有限的操作步骤。包含有限的操作步骤。(必须存在循环结束条件）必须存在循环结束条件）必须存在循环结束条件）必须存在循环结束条件）确定性：确定性：确定性：确定性：算法中的每一个步骤都应当是确定的。算法中的每一个步骤都应当是确定的

7、。算法中的每一个步骤都应当是确定的。算法中的每一个步骤都应当是确定的。有零个或多个输入：有零个或多个输入：有零个或多个输入：有零个或多个输入：输入是指在执行算法时需要从外界取得必输入是指在执行算法时需要从外界取得必输入是指在执行算法时需要从外界取得必输入是指在执行算法时需要从外界取得必要的信息。要的信息。要的信息。要的信息。有一个或多个输出：有一个或多个输出：有一个或多个输出：有一个或多个输出：算法的目的是为了求解，算法的目的是为了求解，算法的目的是为了求解，算法的目的是为了求解，“解解解解”就是输出。就是输出。就是输出。就是输出。有效性：有效性：有效性：有效性：算法中的每一个步骤都应当能有效

8、地执行，并得到确算法中的每一个步骤都应当能有效地执行，并得到确算法中的每一个步骤都应当能有效地执行，并得到确算法中的每一个步骤都应当能有效地执行，并得到确定的结果定的结果定的结果定的结果 。一个算法应该具有以下特点：一个算法应该具有以下特点：本讲稿第九页，共三十页 2.3 算法的表示算法的表示可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：自然语言自然语言传统流程图传统流程图结构化流程图结构化流程图伪代码伪代码伪代码伪代码用计算机语言表示算法用计算机语言表示算法本讲稿第十页，共三十页 2.3.2 用

9、流程图表示算法用流程图表示算法美国国家标准化协会美国国家标准化协会ANSI(American National ANSI(American National Standard Institute)Standard Institute)Standard Institute)Standard Institute)规定了一些常用的流程图符规定了一些常用的流程图符规定了一些常用的流程图符规定了一些常用的流程图符号：号：号：号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点本讲稿第十一页，共三十页 将例算法将例算法2.12.1的算法的算法1 1用流程图表示

10、用流程图表示本讲稿第十二页，共三十页将例将例2.22.2的算法用流程图表示的算法用流程图表示 本讲稿第十三页，共三十页流程图的特点流程图的特点流程图的特点流程图的特点 流程图是表示算法的较好的工具。一个流程图流程图是表示算法的较好的工具。一个流程图包括以下几部分包括以下几部分：(1)表示相应操作的框；表示相应操作的框；(2)带箭头的流程线；带箭头的流程线；(3)框内外必要的文字说明。框内外必要的文字说明。本讲稿第十四页，共三十页三种基本算法结构三种基本算法结构三种基本算法结构三种基本算法结构 顺序结构顺序结构 选择结构（分支结构）选择结构（分支结构）循环结构（重复结构）循环结构（重复结构）当型

11、循环（当型循环（当型循环（当型循环（WhileWhile型循环）型循环）型循环）型循环）直到型循环（直到型循环（直到型循环（直到型循环（UntilUntil型循环）型循环）型循环）型循环）本讲稿第十五页，共三十页选择结构ABabpYN当p为“真”当p为“假”本讲稿第十六页，共三十页if(x y)if(x y)z=xz=xz=yz=y输出输出输出输出z z本讲稿第十七页，共三十页循环结构Aabp1YWhile型循环N当p1为“真”当p1为“假”Aabp2NUntil型循环Y当p2为“真”当p2为“假”本讲稿第十八页，共三十页AabpYN两种循环结构的比较While型循环Until型循环Aab!p

12、NY两个循环结构的判断条件相反A一次也没有执行A执行了一次当首次判断p即为“假”(!p为“真”)当执行一次A后，判断p为“假”(!p为“真”)A执行了一次本讲稿第十九页，共三十页三种基本算法结构的共同特点AabBABa(1)只有一个入口。(2)只有一个出口(3)结构内的每一部分都有机会被执行到。(4)结构内不存在“死循环”(无终止的循环)。本讲稿第二十页，共三十页 2.3.5 用计算机语言表示算法用计算机语言表示算法#include#include void void main()main()int int sum=0;sum=0;int int i=0;i=0;int int max_num

13、=0;max_num=0;printf(Input Max Number:n);printf(Input Max Number:n);scanf(%d,&max_num);scanf(%d,&max_num);for for(i=1;i=max_num;i+)(i=1;i=max_num;i+)sum=sum+i;sum=sum+i;printf(result=%dn,sum);printf(result=%dn,sum);将例将例将例将例2.12.12.12.1的算法的算法的算法的算法1 1 1 1用用用用 C C C C语言表示语言表示语言表示语言表示本讲稿第二十一页，共三十页 2.3.5

14、 用计算机语言表示算法用计算机语言表示算法将例将例2.12.1的算法的算法2 2用用 C C C C语言表示语言表示语言表示语言表示#include#include void void main()main()int int sum=0;sum=0;int int i=0;i=0;int int max_num=0;max_num=0;printf(Input Max Number:n);printf(Input Max Number:n);scanf(%d,&max_num);scanf(%d,&max_num);printf(result=%dn,max_num*(1+max_num)/2

15、);printf(result=%dn,max_num*(1+max_num)/2);本讲稿第二十二页，共三十页2.4 结构化程序设计方法结构化程序设计方法 结构化算法结构化算法由基本结构顺序组成的算法结构由基本结构顺序组成的算法结构由基本结构顺序组成的算法结构由基本结构顺序组成的算法结构 结构化程序设计方法结构化程序设计方法自顶向下自顶向下自顶向下自顶向下逐步细化逐步细化逐步细化逐步细化模块化设计模块化设计模块化设计模块化设计结构化编码结构化编码结构化编码结构化编码本讲稿第二十三页，共三十页课外知识简介课外知识简介-软件设计方法软件设计方法 所有的模块都在最后集成，一旦出现错误不容易查找！所

16、有的模块都在最后集成，一旦出现错误不容易查找！所有的模块都在最后集成，一旦出现错误不容易查找！所有的模块都在最后集成，一旦出现错误不容易查找！也许会出现半年开发、半年集成的局面。也许会出现半年开发、半年集成的局面。也许会出现半年开发、半年集成的局面。也许会出现半年开发、半年集成的局面。软件设计方法软件设计方法模块化设计方法模块化设计方法持续集成持续集成（敏捷开发）（敏捷开发）本讲稿第二十四页，共三十页敏捷式开发（目前各大公司推崇）（目前各大公司推崇）（目前各大公司推崇）（目前各大公司推崇）这是一种这是一种边开发边集成边开发边集成的方式，每个月或每半个的方式，每个月或每半个月集成一次，此开发方式

17、能尽早发现问题并解决问题月集成一次，此开发方式能尽早发现问题并解决问题 一般每天生成一个小版本，每个月生成一个大版一般每天生成一个小版本，每个月生成一个大版本。敏捷式开发方式如果某天的测试发现了问题，存本。敏捷式开发方式如果某天的测试发现了问题，存在在Bug，最多只推到前一天的版本，而不是像模块化，最多只推到前一天的版本，而不是像模块化开发那样，需要对半年以前的代码进行测试。开发那样，需要对半年以前的代码进行测试。版本控制说明版本控制说明本讲稿第二十五页，共三十页软件开发的版本控制问题软件开发的版本控制问题软件开发的版本控制问题软件开发的版本控制问题 A、B、C、D、E、F六人共同开发一个系统

18、软件，六人共同开发一个系统软件，A、B、C三人的模块彼此耦合不大，可以相互独立进行，而三人的模块彼此耦合不大，可以相互独立进行，而D、E、F三人三人共同开发一个大的模块，彼此之间相关程度很大。共同开发一个大的模块，彼此之间相关程度很大。三个人的代码如何整合呢？三个人的代码如何整合呢？版本控制软件：版本控制软件：SVN和和clearcase（收费）（收费）本讲稿第二十六页，共三十页D编写好软件上传至服务器（版本0）E下载至本地本地版本为0F下载至本地本地版本为0E首先编写完代码，将代码上传至服务器SVN发现服务器版本和本地一致可以直接上传，并将服务器版本改为1F将代码上传至服务器SVN发现本地版

19、本与服务器版本不一致，会提示冲突并显示。F手动merge，服务器版本号变为2 版本控制流程版本控制流程本讲稿第二十七页，共三十页软件测试软件测试 敏捷式开发带来的一个问题是：测试工作量大大增加敏捷式开发带来的一个问题是：测试工作量大大增加 开发人员开发人员写一部分代码进行写一部分代码进行单元测试（单元测试（UT），），这里的测试不这里的测试不采用专门的软件，一般写一段辅助程序进行测试。采用专门的软件，一般写一段辅助程序进行测试。测试人员测试人员对于上传到服务器上的代码，采用对于上传到服务器上的代码，采用自动化测试（自动化测试（AT）的方法，每天下班之前进行测试，第二天早晨就会有结果，确定的方法

20、，每天下班之前进行测试，第二天早晨就会有结果，确定前一天的开发是否引入了新的问题。前一天的开发是否引入了新的问题。一个模块完成后进行一个模块完成后进行功能性测试（功能性测试（FT）模块中加入了新功能要进行模块中加入了新功能要进行回归测试（回归测试（RT）系统的多个模块整合在一起后进行系统的多个模块整合在一起后进行系统测试系统测试（ST）本讲稿第二十八页，共三十页 现在的工程基本上要由很多人共同来完成，公司需现在的工程基本上要由很多人共同来完成，公司需要对所有程序开发人员的编程风格进行统一。因此要对要对所有程序开发人员的编程风格进行统一。因此要对每个人进行每个人进行coding style测试，

21、如果编程风格不符合要求，测试，如果编程风格不符合要求，就无权上传代码，直到符合要求为止。就会出现就无权上传代码，直到符合要求为止。就会出现这样一种情况，即虽然在测试的时候通过了，但以后编这样一种情况，即虽然在测试的时候通过了，但以后编写代码还按照原来的风格编写，公司对这种情况会如何写代码还按照原来的风格编写，公司对这种情况会如何处理呢？处理呢？对程序员编程风格的要求对程序员编程风格的要求code review！本讲稿第二十九页，共三十页本章小结本章小结1.1.理解算法的概念：程序的灵魂所在理解算法的概念：程序的灵魂所在2.2.2.2.重点掌握算法的两种表示方法：流程图和计重点掌握算法的两种表示方法：流程图和计重点掌握算法的两种表示方法：流程图和计重点掌握算法的两种表示方法：流程图和计 算机语言。算机语言。本讲稿第三十页，共三十页