《第2章 程序的灵魂算法优秀PPT.ppt》由会员分享，可在线阅读，更多相关《第2章 程序的灵魂算法优秀PPT.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第2章 程序的灵魂算法现在学习的是第1页，共21页随着计算机理论的发展，程序不但要和数据结构、算法有关，随着计算机理论的发展，程序不但要和数据结构、算法有关，还与程序设计的方法、语言的工具和环境有关，因此又可以表示还与程序设计的方法、语言的工具和环境有关，因此又可以表示成：成：程序程序=数据结构数据结构+算法算法+程序设计的方法程序设计的方法+语言的工具和环境，语言的工具和环境，下面介绍算法的基本概念。下面介绍算法的基本概念。现在学习的是第2页，共21页2.1 2.1 算法的概念算法的概念例例1 1：去火车站的方法：去火车站的方法例例2 2：求：求1 1100100的和的和例例3 3：祖冲之的
2、割圆术求：祖冲之的割圆术求 例例4 4：求：求1 1100100内的素数（筛法）内的素数（筛法）算法的实质是解决给定问题的有限操作步骤的描述，它指明了其问题算法的实质是解决给定问题的有限操作步骤的描述，它指明了其问题的解答过程。因些可给算法如下定义：的解答过程。因些可给算法如下定义：算法是一个过程，由一套清楚的规则组成的，这些规则指定了算法是一个过程，由一套清楚的规则组成的，这些规则指定了操作顺序，以便在有限步骤内得到特定问题的解。操作顺序，以便在有限步骤内得到特定问题的解。现在学习的是第3页，共21页2.2 2.2 简单算法的举例简单算法的举例例例1 1：求：求1 1100100的和的和步骤
3、步骤1 1：1=i,0=s1=i,0=s步骤步骤2 2：i+s=si+s=s步骤步骤3 3：i+1=ii+1=i步骤步骤4 4：如果：如果i100 i100 返回步骤返回步骤2 2，否则结束，否则结束现在学习的是第4页，共21页例例2 2：判断任何正整数是否是素数：判断任何正整数是否是素数步骤步骤1 1：输入正整数：输入正整数n(n2)n(n2)步骤步骤2 2：如果：如果n1,n1,输出不是素数，转步骤输出不是素数，转步骤8 8步骤步骤3 3：2=i 2=i 步骤步骤4 4：如果：如果in,ii i+1=i，转步骤，转步骤4 4步骤步骤7 7：输出：输出n n步骤步骤8 8：结束：结束现在学习
4、的是第5页，共21页例例3 3：欧几里德算法（求二个整数的最大公约数）：欧几里德算法（求二个整数的最大公约数）步骤步骤1 1：输入二个正整数：输入二个正整数m,nm,n步骤步骤2 2：如果：如果mn,mn,则则m,nm,n的值交换的值交换步骤步骤3 3：m mod n=rm mod n=r步骤步骤4 4：如果：如果r=0 r=0 则则 转步骤转步骤6 6，否则执行步骤，否则执行步骤5 5步骤步骤5 5：n=m r=n n=m r=n 转步骤转步骤3 3步骤步骤6 6：输出：输出n,n,结束结束现在学习的是第6页，共21页2.3 2.3 算法的特性算法的特性一个算法应具有以下特点：一个算法应具有
5、以下特点：1.1.有穷性有穷性有穷性有穷性 由于算法必须在有限步骤内得到问题的解，因些算法的操场作步骤由于算法必须在有限步骤内得到问题的解，因些算法的操场作步骤必要须是有限的，如用圆规和直尺不能将一个任意角三等分，其实是在必要须是有限的，如用圆规和直尺不能将一个任意角三等分，其实是在有限步骤内不能三等分。有限步骤内不能三等分。2.2.确定性确定性确定性确定性 算法的每一步骤都应该是确定的，不能是模糊不清的，譬如算法的每一步骤都应该是确定的，不能是模糊不清的，譬如你不能将烧菜的算法写成放盐，烧一会儿等。这样就不能确定少你不能将烧菜的算法写成放盐，烧一会儿等。这样就不能确定少许和一会儿到底是多少。
6、欧几里德算法许和一会儿到底是多少。欧几里德算法现在学习的是第7页，共21页3.3.数据的输入数据的输入数据的输入数据的输入 由于算法通常是对数据的操作，因此需输入对那些数据进由于算法通常是对数据的操作，因此需输入对那些数据进行操作，如求素数中的行操作，如求素数中的n,n,欧几里德算法中的欧几里德算法中的mm、n n二个正整数，二个正整数，也可能算法中没有显式的输入如求也可能算法中没有显式的输入如求1 1100100的和、祖冲之的割圆的和、祖冲之的割圆术求术求。4.4.数据的输出数据的输出数据的输出数据的输出 由于算法是给出特定问题的求解，因此当获得解时应该输出，由于算法是给出特定问题的求解，因
7、此当获得解时应该输出，如欧几里德算法中当如欧几里德算法中当r r为为0 0时时n n的值，即为最大公约数的值，即为最大公约数5.5.有效性有效性有效性有效性 有效性又称可行性，如一个去火车站的算法要去杀一个人，有效性又称可行性，如一个去火车站的算法要去杀一个人，做脑外科手术，只有切菜刀，在除法中要除以做脑外科手术，只有切菜刀，在除法中要除以0 0都不具有有效性。都不具有有效性。现在学习的是第8页，共21页2.4 2.4 算法的表示算法的表示 2.4.12.4.1 用自然语言表示算法用自然语言表示算法用自然语言表示算法用自然语言表示算法 虽然可以用人们使用的自然语言来描述算法，但自然语言虽然可以
8、用人们使用的自然语言来描述算法，但自然语言的种类繁多，而且其语句上下文有关系的，如：的种类繁多，而且其语句上下文有关系的，如：“你你C C语言考语言考得怎么样？得怎么样？”中的你不能确定究竟指哪一个同学。在程序设计中很中的你不能确定究竟指哪一个同学。在程序设计中很少使用这种方法来描述算法。少使用这种方法来描述算法。2.4.2 2.4.2 用流程图表示算法用流程图表示算法用流程图表示算法用流程图表示算法 流程图是用一些图框表各种操作。用；这种图形表示算法比效直观，流程图是用一些图框表各种操作。用；这种图形表示算法比效直观，相对容易理解。相对容易理解。现在学习的是第9页，共21页现在学习的是第10
9、页，共21页例例1 1：画出欧几里德算法的流程图：画出欧几里德算法的流程图现在学习的是第11页，共21页例例2 2：画出求：画出求3 3到到100100内的素数的流程图内的素数的流程图现在学习的是第12页，共21页2.4.32.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构和改进的流程图 1.1.传统流程图弊端传统流程图弊端传统流程图弊端传统流程图弊端 传统的流程图由于用箭头来指出各种处理的执行次序，对控制的传统的流程图由于用箭头来指出各种处理的执行次序，对控制的走向没有严格的限制走向没有严格的限制,这样有可能会造成用户过多的使用转向造成一这
10、样有可能会造成用户过多的使用转向造成一团乱麻团乱麻,这种算法难以理解也难以阅读和修改，为了避免这种情况应这种算法难以理解也难以阅读和修改，为了避免这种情况应尽量少用这种无限制的转移。尽量少用这种无限制的转移。2.2.三种基本结构三种基本结构三种基本结构三种基本结构 为了减少过多的转向，限制转移可用三种基本结构为了减少过多的转向，限制转移可用三种基本结构(1)(1)顺序结构顺序结构(2)(2)判断结构判断结构(3)(3)重复结构（循环结构）重复结构（循环结构）现在学习的是第13页，共21页现在学习的是第14页，共21页2.4.42.4.4 用用用用N-SN-S流程图表示算法流程图表示算法流程图表
11、示算法流程图表示算法 19731973年美国的年美国的NassiNassi和和ShneidermanShneiderman提出了提出了chapinchapin图，即图，即N-SN-S图，它是一种没有流程线的流程图，它的基本结构如下：图，它是一种没有流程线的流程图，它的基本结构如下：现在学习的是第15页，共21页例例1 1：用：用N-SN-S图，画出欧几里德算法图，画出欧几里德算法 现在学习的是第16页，共21页2.4.52.4.5 用伪代码表示算法用伪代码表示算法用伪代码表示算法用伪代码表示算法 当算法比较复杂时，用图形表示就会很大，有时可用一种介于自然语当算法比较复杂时，用图形表示就会很大，
12、有时可用一种介于自然语言和计算机语言之间的所谓伪代码来表示言和计算机语言之间的所谓伪代码来表示例例1 1：用伪代码表示，求：用伪代码表示，求5 5！的算法！的算法开始开始 置置t t的初值为的初值为1;1;置置i i的初值为的初值为2;2;当当i i的值的值=5t;t*i=t;i+1=i;i+1=i;输出输出t t的值的值现在学习的是第17页，共21页2.4.62.4.6 用计算机语言表示算法用计算机语言表示算法用计算机语言表示算法用计算机语言表示算法 计算机的算通常是要在计算机中完成的，因此可以用计算机的某计算机的算通常是要在计算机中完成的，因此可以用计算机的某种语言来表示算法，如用种语言来
13、表示算法，如用C C语言、语言、PASCALPASCAL语言或者其它语言来表示语言或者其它语言来表示算法。算法。现在学习的是第18页，共21页2.5 2.5 构化程序设计方法构化程序设计方法 结构程序设计的思想和方法是荷兰计算机学家结构程序设计的思想和方法是荷兰计算机学家(E.W.Dijkstra)(E.W.Dijkstra)提出来提出来的。随计算机的发展，计算机的软件也在不断的发展，因此如何提高计的。随计算机的发展，计算机的软件也在不断的发展，因此如何提高计算机程序的质量减少出错可能是每个程序设计者都要考虑的问题。算机程序的质量减少出错可能是每个程序设计者都要考虑的问题。结构化程序设计就是为
14、了使程序具有合理的结构，便于阅读、修改和结构化程序设计就是为了使程序具有合理的结构，便于阅读、修改和维护，从而提高了程序的可靠性，保证了软件的质量。那么什么样的程维护，从而提高了程序的可靠性，保证了软件的质量。那么什么样的程序是结构化的程序的呢？当需要处理一个较复杂的问题时，可以采用一序是结构化的程序的呢？当需要处理一个较复杂的问题时，可以采用一系列系统的、规范的方法保证其程序的正确性。具体来说，可采用下列系列系统的、规范的方法保证其程序的正确性。具体来说，可采用下列方法得到结构化程序：方法得到结构化程序：现在学习的是第19页，共21页(1)(1)自顶向下、逐步细化自顶向下、逐步细化(2)(2
15、)模块化设计模块化设计(3)(3)结构化编码结构化编码自顶向下是将一个复杂的问题由抽象到具的的过程，避如要解自顶向下是将一个复杂的问题由抽象到具的的过程，避如要解决一个哥德巴赫猜想问题。可以化解成一个大偶数能不能拆成二决一个哥德巴赫猜想问题。可以化解成一个大偶数能不能拆成二个数的和、然后判断这二个数是否是素数，判断一个数个数的和、然后判断这二个数是否是素数，判断一个数x x是否是素是否是素数的方法可以用数的方法可以用x x除以除以2 2，3 3，x-1x-1等。等。模块化设计就将大任务划分为若干个相对独立的小任务，每个小任务模块化设计就将大任务划分为若干个相对独立的小任务，每个小任务意义单一，
16、职责明确，各模块之间关系简单明了。意义单一，职责明确，各模块之间关系简单明了。结构化编码在设计具体代码中，尽量采用三种基本结构，少用结构化编码在设计具体代码中，尽量采用三种基本结构，少用或不用或不用gotogoto语句，选择容易理解的、占时空较少的语句。语句，选择容易理解的、占时空较少的语句。现在学习的是第20页，共21页总而言之，算法是程序设计的灵魂，虽然对于初学者来说，总而言之，算法是程序设计的灵魂，虽然对于初学者来说，学习一种新的程序设计语言感到有点难，但是在程序设计中要学习一种新的程序设计语言感到有点难，但是在程序设计中要设计一个好的程序首先要对程序的算法有较详细的了解，其次设计一个好的程序首先要对程序的算法有较详细的了解，其次才是选择适当的语言实现。以后在介绍各语句后，程序举例时才是选择适当的语言实现。以后在介绍各语句后，程序举例时都会涉及算法。都会涉及算法。现在学习的是第21页，共21页