《第2章 程序的算法精选PPT.ppt》由会员分享，可在线阅读，更多相关《第2章 程序的算法精选PPT.ppt（30页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第第第2 2章章章章 程序的算法程序的算法程序的算法程序的算法第1页，此课件共30页哦本章主要内容本章主要内容 2.1算法的概念及简单算法举例算法的概念及简单算法举例 2.2算法的特性算法的特性 2.3怎样表示一个算法怎样表示一个算法 2.4结构化程序设计方法结构化程序设计方法第2页，此课件共30页哦2.12.1算法算法算法算法(Algorithm)(Algorithm)算法算法解决问题的方法解决问题的方法解决问题的方法解决问题的方法算法是程序的灵魂算法是程序的灵魂算法是程序的灵魂算法是程序的灵魂 程序程序(Program)对算法的具体实现对算法的具体实现对算法的具体实现对算法的具体实现程序
2、的效率不可能超过算法的限制程序的效率不可能超过算法的限制程序的效率不可能超过算法的限制程序的效率不可能超过算法的限制 Nikiklaus Wirth程序程序程序程序 数据结构数据结构数据结构数据结构 算法算法算法算法数据结构算法程序设计方法语言工具数据结构算法程序设计方法语言工具完整的程序设计应该是:第3页，此课件共30页哦算法算法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：求第4页，此课件共30页哦这是最简单的算法这是最简单的算法如果如果n从从1到到1万怎么办？万怎么办？第5页，此课件共30页哦算法算法2：100+(1+99)+(2+98)+(49+51)+50 按照等差数列求和公式：按照等差数列求和公式：sum=(首项首项+尾项尾项)*项数项数)/2 只需要进行一次加法，一次乘法和一次除只需要进行一次加法，一次乘法和一次除法即可，大大节省了运行时间！法即可，大大节省了运行时间！第6页，此课件共30页哦算法的重要性算法的重要性算法的重要性算法的重要性 同样的问题，有的人写出一段程序也许要几同样的问题，有的人写出一段
4、程序也许要几天几夜能得到结果，而有的人写的程序也许仅仅天几夜能得到结果，而有的人写的程序也许仅仅需要几分钟而已！需要几分钟而已！人和人之间的差距咋就这么大呢？人和人之间的差距咋就这么大呢？第7页，此课件共30页哦例例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 S
5、5 S5 S5 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最后的值就是多项式的值。第8页，此课件共30页哦 2.2 算法的特性算法的特性 有穷性：有穷性：有穷性：有穷性：包含有限的操作步骤。包含有限的操作步骤。包含有限的操作步骤。包含有限的操作步骤。(必须存在循环结束条件）必须存在循环结束条件）必须存在循环结束条件）必须存在循环结束条件）确定性：确定性：确定性：确定性：算法中的每一个步骤都应当是确定的。算法中的每一个步骤
7、都应当是确定的。算法中的每一个步骤都应当是确定的。算法中的每一个步骤都应当是确定的。有零个或多个输入：有零个或多个输入：有零个或多个输入：有零个或多个输入：输入是指在执行算法时需要从外界取得必要的信输入是指在执行算法时需要从外界取得必要的信输入是指在执行算法时需要从外界取得必要的信输入是指在执行算法时需要从外界取得必要的信息。息。息。息。有一个或多个输出：有一个或多个输出：有一个或多个输出：有一个或多个输出：算法的目的是为了求解，算法的目的是为了求解，算法的目的是为了求解，算法的目的是为了求解，“解解解解”就是输出。就是输出。就是输出。就是输出。有效性：有效性：有效性：有效性：算法中的每一个步
8、骤都应当能有效地执行，并得到确定的算法中的每一个步骤都应当能有效地执行，并得到确定的算法中的每一个步骤都应当能有效地执行，并得到确定的算法中的每一个步骤都应当能有效地执行，并得到确定的结果结果结果结果 。一个算法应该具有以下特点：一个算法应该具有以下特点：第9页，此课件共30页哦 2.3 算法的表示算法的表示可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：可以用不同的方法表示算法，常用的有：自然语言自然语言自然语言自然语言传统流程图传统流程图传统流程图传统流程图结构化流程图结构化流程图伪代码伪代码伪代码伪代码用计算机语言表示算法用计算
9、机语言表示算法用计算机语言表示算法用计算机语言表示算法第10页，此课件共30页哦 2.3.2 用流程图表示算法用流程图表示算法美国国家标准化协会美国国家标准化协会美国国家标准化协会美国国家标准化协会ANSI(American National ANSI(American National ANSI(American National ANSI(American National Standard Institute)Standard Institute)规定了一些常用的流程图符规定了一些常用的流程图符号：号：号：号：起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流
10、向线连接点连接点第11页，此课件共30页哦 将例算法将例算法2.12.1的算法的算法1 1用流程图表示用流程图表示第12页，此课件共30页哦将例将例2.22.2的算法用流程图表示的算法用流程图表示 第13页，此课件共30页哦流程图的特点流程图的特点流程图的特点流程图的特点 流程图是表示算法的较好的工具。一个流程图流程图是表示算法的较好的工具。一个流程图包括以下几部分包括以下几部分：(1)表示相应操作的框；表示相应操作的框；(2)带箭头的流程线；带箭头的流程线；(3)框内外必要的文字说明。框内外必要的文字说明。第14页，此课件共30页哦三种基本算法结构三种基本算法结构三种基本算法结构三种基本算法
11、结构 顺序结构顺序结构 选择结构（分支结构）选择结构（分支结构）循环结构（重复结构）循环结构（重复结构）当型循环（当型循环（当型循环（当型循环（WhileWhile型循环）型循环）型循环）型循环）直到型循环（直到型循环（直到型循环（直到型循环（UntilUntil型循环）型循环）型循环）型循环）第15页，此课件共30页哦选择结构ABabpYN当p为“真”当p为“假”第16页，此课件共30页哦if(x y)z=xz=xz=y输出输出z第17页，此课件共30页哦循环结构Aabp1YWhile型循环N当p1为“真”当p1为“假”Aabp2NUntil型循环Y当p2为“真”当p2为“假”第18页，此课
12、件共30页哦AabpYN两种循环结构的比较While型循环Until型循环Aab!pNY两个循环结构的判断条件相反A一次也没有执行A执行了一次当首次判断p即为“假”(!p为“真”)当执行一次A后，判断p为“假”(!p为“真”)A执行了一次第19页，此课件共30页哦三种基本算法结构的共同特点AabBABa(1)只有一个入口。(2)只有一个出口(3)结构内的每一部分都有机会被执行到。(4)结构内不存在“死循环”(无终止的循环)。第20页，此课件共30页哦 2.3.5 用计算机语言表示算法用计算机语言表示算法#include#include void void main()main()int int
13、 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);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.1的算法的算法1 1用用 C C语言表示语言表示第21页，此课件共
14、30页哦 2.3.5 用计算机语言表示算法用计算机语言表示算法将例将例将例将例2.12.12.12.1的算法的算法的算法的算法2 2 2 2用用用用 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,m
15、ax_num*(1+max_num)/2);printf(result=%dn,max_num*(1+max_num)/2);第22页，此课件共30页哦2.4 结构化程序设计方法结构化程序设计方法 结构化算法结构化算法由基本结构顺序组成的算法结构由基本结构顺序组成的算法结构由基本结构顺序组成的算法结构由基本结构顺序组成的算法结构 结构化程序设计方法结构化程序设计方法自顶向下自顶向下自顶向下自顶向下逐步细化逐步细化逐步细化逐步细化模块化设计模块化设计模块化设计模块化设计结构化编码结构化编码结构化编码结构化编码第23页，此课件共30页哦课外知识简介课外知识简介-软件设计方法软件设计方法 所有的模块
16、都在最后集成，一旦出现错误不容易查找！所有的模块都在最后集成，一旦出现错误不容易查找！所有的模块都在最后集成，一旦出现错误不容易查找！所有的模块都在最后集成，一旦出现错误不容易查找！也许会出现半年开发、半年集成的局面。也许会出现半年开发、半年集成的局面。也许会出现半年开发、半年集成的局面。也许会出现半年开发、半年集成的局面。软件设计方法软件设计方法模块化设计方法模块化设计方法持续集成持续集成（敏捷开发）（敏捷开发）第24页，此课件共30页哦敏捷式开发（目前各大公司推崇）（目前各大公司推崇）（目前各大公司推崇）（目前各大公司推崇）这是一种这是一种边开发边集成边开发边集成的方式，每个月或每半个的方
17、式，每个月或每半个月集成一次，此开发方式能尽早发现问题并解决问题月集成一次，此开发方式能尽早发现问题并解决问题 一般每天生成一个小版本，每个月生成一个大版一般每天生成一个小版本，每个月生成一个大版本。敏捷式开发方式如果某天的测试发现了问题，存本。敏捷式开发方式如果某天的测试发现了问题，存在在Bug，最多只推到前一天的版本，而不是像模块化，最多只推到前一天的版本，而不是像模块化开发那样，需要对半年以前的代码进行测试。开发那样，需要对半年以前的代码进行测试。版本控制说明版本控制说明第25页，此课件共30页哦软件开发的版本控制问题软件开发的版本控制问题软件开发的版本控制问题软件开发的版本控制问题 A
18、、B、C、D、E、F六人共同开发一个系统软件，六人共同开发一个系统软件，A、B、C三三人的模块彼此耦合不大，可以相互独立进行，而人的模块彼此耦合不大，可以相互独立进行，而D、E、F三人共同开三人共同开发一个大的模块，彼此之间相关程度很大。发一个大的模块，彼此之间相关程度很大。三个人的代码如何整合呢？三个人的代码如何整合呢？版本控制软件：版本控制软件：SVN和和clearcase（收费）（收费）第26页，此课件共30页哦D编写好软件上传至服务器（版本0）E下载至本地本地版本为0F下载至本地本地版本为0E首先编写完代码，将代码上传至服务器SVN发现服务器版本和本地一致可以直接上传，并将服务器版本改
19、为1F将代码上传至服务器SVN发现本地版本与服务器版本不一致，会提示冲突并显示。F手动merge，服务器版本号变为2 版本控制流程版本控制流程第27页，此课件共30页哦软件测试软件测试 敏捷式开发带来的一个问题是：测试工作量大大增加敏捷式开发带来的一个问题是：测试工作量大大增加 开发人员开发人员写一部分代码进行写一部分代码进行单元测试（单元测试（UT），），这里的测试不这里的测试不采用专门的软件，一般写一段辅助程序进行测试。采用专门的软件，一般写一段辅助程序进行测试。测试人员测试人员对于上传到服务器上的代码，采用对于上传到服务器上的代码，采用自动化测试自动化测试（AT）的方法，每天下班之前进行
20、测试，第二天早晨就会有结果，的方法，每天下班之前进行测试，第二天早晨就会有结果，确定前一天的开发是否引入了新的问题。确定前一天的开发是否引入了新的问题。一个模块完成后进行一个模块完成后进行功能性测试（功能性测试（FT）模块中加入了新功能要进行模块中加入了新功能要进行回归测试（回归测试（RT）系统的多个模块整合在一起后进行系统的多个模块整合在一起后进行系统测试系统测试（ST）第28页，此课件共30页哦 现在的工程基本上要由很多人共同来完成，公司需现在的工程基本上要由很多人共同来完成，公司需要对所有程序开发人员的编程风格进行统一。因此要对要对所有程序开发人员的编程风格进行统一。因此要对每个人进行每
21、个人进行coding style测试，如果编程风格不符合要求，测试，如果编程风格不符合要求，就无权上传代码，直到符合要求为止。就会出现就无权上传代码，直到符合要求为止。就会出现这样一种情况，即虽然在测试的时候通过了，但以后编这样一种情况，即虽然在测试的时候通过了，但以后编写代码还按照原来的风格编写，公司对这种情况会如何写代码还按照原来的风格编写，公司对这种情况会如何处理呢？处理呢？对程序员编程风格的要求对程序员编程风格的要求code review！第29页，此课件共30页哦本章小结本章小结1.1.理解算法的概念：程序的灵魂所在理解算法的概念：程序的灵魂所在2.2.2.2.重点掌握算法的两种表示方法：流程图和计重点掌握算法的两种表示方法：流程图和计重点掌握算法的两种表示方法：流程图和计重点掌握算法的两种表示方法：流程图和计 算机语言。算机语言。第30页，此课件共30页哦