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

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

1、第2章 程序的灵魂算法本讲稿第一页，共二十一页随着计算机理论的发展，程序不但要和数据结构、算法有关，还与随着计算机理论的发展，程序不但要和数据结构、算法有关，还与程序设计的方法、语言的工具和环境有关，因此又可以表示成：程序设计的方法、语言的工具和环境有关，因此又可以表示成：程序程序=数据结构数据结构+算法算法+程序设计的方法程序设计的方法+语言的工具和环境，下语言的工具和环境，下面介绍算法的基本概念。面介绍算法的基本概念。本讲稿第二页，共二十一页2.1 2.1 算法的概念算法的概念例例1 1：去火车站的方法：去火车站的方法例例2 2：求：求1 1100100的和的和例例3 3：祖冲之的割圆术求

2、：祖冲之的割圆术求 例例4 4：求：求1 1100100内的素数（筛法）内的素数（筛法）算法的实质是解决给定问题的有限操作步骤的描述，它指明算法的实质是解决给定问题的有限操作步骤的描述，它指明了其问题的解答过程。因些可给算法如下定义：了其问题的解答过程。因些可给算法如下定义：算法是一个过程，由一套清楚的规则组成的，这些规则指定了操作顺算法是一个过程，由一套清楚的规则组成的，这些规则指定了操作顺序，以便在有限步骤内得到特定问题的解。序，以便在有限步骤内得到特定问题的解。本讲稿第三页，共二十一页2.2 2.2 简单算法的举例简单算法的举例例例1 1：求：求1 1100100的和的和步骤步骤1 1：

3、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，否则结束，否则结束本讲稿第四页，共二十一页例例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、例例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,结束结束本讲稿第六页，共二十一页2.3 2.3 算法的特性算法的特性一个算法应具有以下特点：一个算法应具有以下特点：1.1.有穷性

5、有穷性有穷性有穷性 由于算法必须在有限步骤内得到问题的解，因些算法的操场作步骤由于算法必须在有限步骤内得到问题的解，因些算法的操场作步骤必要须是有限的，如用圆规和直尺不能将一个任意角三等分，其实是在必要须是有限的，如用圆规和直尺不能将一个任意角三等分，其实是在有限步骤内不能三等分。有限步骤内不能三等分。2.2.确定性确定性确定性确定性 算法的每一步骤都应该是确定的，不能是模糊不清的，譬如你不算法的每一步骤都应该是确定的，不能是模糊不清的，譬如你不能将烧菜的算法写成放盐，烧一会儿等。这样就不能确定少许和一会能将烧菜的算法写成放盐，烧一会儿等。这样就不能确定少许和一会儿到底是多少。欧几里德算法儿到

6、底是多少。欧几里德算法本讲稿第七页，共二十一页3.3.数据的输入数据的输入数据的输入数据的输入 由于算法通常是对数据的操作，因此需输入对那些数据进行由于算法通常是对数据的操作，因此需输入对那些数据进行操作，如求素数中的操作，如求素数中的n,n,欧几里德算法中的欧几里德算法中的mm、n n二个正整数，也二个正整数，也可能算法中没有显式的输入如求可能算法中没有显式的输入如求1 1100100的和、祖冲之的割圆术的和、祖冲之的割圆术求求。4.4.数据的输出数据的输出数据的输出数据的输出 由于算法是给出特定问题的求解，因此当获得解时应该输出，如欧由于算法是给出特定问题的求解，因此当获得解时应该输出，如

7、欧几里德算法中当几里德算法中当r r为为0 0时时n n的值，即为最大公约数的值，即为最大公约数5.5.有效性有效性有效性有效性 有效性又称可行性，如一个去火车站的算法要去杀一个人，有效性又称可行性，如一个去火车站的算法要去杀一个人，做脑外科手术，只有切菜刀，在除法中要除以做脑外科手术，只有切菜刀，在除法中要除以0 0都不具有有效都不具有有效性。性。本讲稿第八页，共二十一页2.4 2.4 算法的表示算法的表示 2.4.12.4.1 用自然语言表示算法用自然语言表示算法用自然语言表示算法用自然语言表示算法 虽然可以用人们使用的自然语言来描述算法，但自然语言虽然可以用人们使用的自然语言来描述算法，

8、但自然语言的种类繁多，而且其语句上下文有关系的，如：的种类繁多，而且其语句上下文有关系的，如：“你你C C语言考得语言考得怎么样？怎么样？”中的你不能确定究竟指哪一个同学。在程序设计中很少使用中的你不能确定究竟指哪一个同学。在程序设计中很少使用这种方法来描述算法。这种方法来描述算法。2.4.2 2.4.2 用流程图表示算法用流程图表示算法用流程图表示算法用流程图表示算法 流程图是用一些图框表各种操作。用；这种图形表示算法流程图是用一些图框表各种操作。用；这种图形表示算法比效直观，相对容易理解。比效直观，相对容易理解。本讲稿第九页，共二十一页本讲稿第十页，共二十一页例例1 1：画出欧几里德算法的

9、流程图：画出欧几里德算法的流程图本讲稿第十一页，共二十一页例例2 2：画出求：画出求3 3到到100100内的素数的流程图内的素数的流程图本讲稿第十二页，共二十一页2.4.32.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构和改进的流程图三种基本结构和改进的流程图 1.1.传统流程图弊端传统流程图弊端传统流程图弊端传统流程图弊端 传统的流程图由于用箭头来指出各种处理的执行次序，对控传统的流程图由于用箭头来指出各种处理的执行次序，对控制的走向没有严格的限制制的走向没有严格的限制,这样有可能会造成用户过多的使用转这样有可能会造成用户过多的使用转向造成一团乱麻向造成一团乱麻

10、,这种算法难以理解也难以阅读和修改，为了避这种算法难以理解也难以阅读和修改，为了避免这种情况应尽量少用这种无限制的转移。免这种情况应尽量少用这种无限制的转移。2.2.三种基本结构三种基本结构三种基本结构三种基本结构 为了减少过多的转向，限制转移可用三种基本结构为了减少过多的转向，限制转移可用三种基本结构(1)(1)顺序结构顺序结构(2)(2)判断结构判断结构(3)(3)重复结构（循环结构）重复结构（循环结构）本讲稿第十三页，共二十一页本讲稿第十四页，共二十一页2.4.42.4.4 用用用用N-SN-S流程图表示算法流程图表示算法流程图表示算法流程图表示算法 19731973年美国的年美国的Na

11、ssiNassi和和ShneidermanShneiderman提出了提出了chapinchapin图，即图，即N-SN-S图，它是一种没有流程线的流程图，它的基本结构如下：图，它是一种没有流程线的流程图，它的基本结构如下：本讲稿第十五页，共二十一页例例1 1：用：用N-SN-S图，画出欧几里德算法图，画出欧几里德算法 本讲稿第十六页，共二十一页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的值的值本讲稿第十七页，共二十一页2.4.62.4.6 用计算机语言表示算法用计算机语言表示算法用计算机语言表示算法用计算机语言表示算法 计算机的算通常是要在计算机中完成的，因此可以用计算机的计算机的算通常是要在计算机中完成的，因此可以用计算机的某种语言来表示算法，如用某种语言来表示算法，如用C C语言、语言、PASCALPASCAL语言或者其它语

13、言来语言或者其它语言来表示算法。表示算法。本讲稿第十八页，共二十一页2.5 2.5 构化程序设计方法构化程序设计方法 结构程序设计的思想和方法是荷兰计算机学家结构程序设计的思想和方法是荷兰计算机学家(E.W.Dijkstra)(E.W.Dijkstra)提出来的。随计算机的发展，计算机的软件也提出来的。随计算机的发展，计算机的软件也在不断的发展，因此如何提高计算机程序的质量减少出错可能在不断的发展，因此如何提高计算机程序的质量减少出错可能是每个程序设计者都要考虑的问题。是每个程序设计者都要考虑的问题。结构化程序设计就是为了使程序具有合理的结构，便于阅读、结构化程序设计就是为了使程序具有合理的结

14、构，便于阅读、修改和维护，从而提高了程序的可靠性，保证了软件的质量。那修改和维护，从而提高了程序的可靠性，保证了软件的质量。那么什么样的程序是结构化的程序的呢？当需要处理一个较复杂的么什么样的程序是结构化的程序的呢？当需要处理一个较复杂的问题时，可以采用一系列系统的、规范的方法保证其程序的正确问题时，可以采用一系列系统的、规范的方法保证其程序的正确性。具体来说，可采用下列方法得到结构化程序：性。具体来说，可采用下列方法得到结构化程序：本讲稿第十九页，共二十一页(1)(1)自顶向下、逐步细化自顶向下、逐步细化(2)(2)模块化设计模块化设计(3)(3)结构化编码结构化编码自顶向下是将一个复杂的问

15、题由抽象到具的的过程，避如要解决一个自顶向下是将一个复杂的问题由抽象到具的的过程，避如要解决一个哥德巴赫猜想问题。可以化解成一个大偶数能不能拆成二个数的和、然哥德巴赫猜想问题。可以化解成一个大偶数能不能拆成二个数的和、然后判断这二个数是否是素数，判断一个数后判断这二个数是否是素数，判断一个数x x是否是素数的方法可以用是否是素数的方法可以用x x除除以以2 2，3 3，x-1x-1等。等。模块化设计就将大任务划分为若干个相对独立的小任务，每个模块化设计就将大任务划分为若干个相对独立的小任务，每个小任务意义单一，职责明确，各模块之间关系简单明了。小任务意义单一，职责明确，各模块之间关系简单明了。

16、结构化编码在设计具体代码中，尽量采用三种基本结构，少用或不用结构化编码在设计具体代码中，尽量采用三种基本结构，少用或不用gotogoto语句，选择容易理解的、占时空较少的语句。语句，选择容易理解的、占时空较少的语句。本讲稿第二十页，共二十一页总而言之，算法是程序设计的灵魂，虽然对于初学者来说，学总而言之，算法是程序设计的灵魂，虽然对于初学者来说，学习一种新的程序设计语言感到有点难，但是在程序设计中要设计习一种新的程序设计语言感到有点难，但是在程序设计中要设计一个好的程序首先要对程序的算法有较详细的了解，其次才是选一个好的程序首先要对程序的算法有较详细的了解，其次才是选择适当的语言实现。以后在介绍各语句后，程序举例时都会涉及择适当的语言实现。以后在介绍各语句后，程序举例时都会涉及算法。算法。本讲稿第二十一页，共二十一页