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