《程序的灵魂--算法.ppt》由会员分享，可在线阅读，更多相关《程序的灵魂--算法.ppt（44页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章 程序的灵魂-算法程序设计概述一个程序应包括对数据的描述和对数据处理的描述。1对数据的描述，即数据结构。数据结构是计算机学科的核心课程之一，有许多专门著作论述，本课程就不再赘述。在C语言中，系统提供的数据结构，是以数据类型的形式出现的。2对数据处理的描述，即计算机算法。算法是为解决一个问题而采取的方法和步骤，是程序的灵魂。为此，著名计算机科学家沃思（Nikiklaus Wirth）提出一个公式：数据结构数据结构+算法算法=程序程序 实际上，一个程序除了数据结构和算法外，还必须使用一种计算机语言，并采用结构化方法来表示。2.1 算法的概念v算法:是指解决一个具体问题的意义明确的步骤的集合。
2、是有限的v概括地说，算法是指解题方案的准确而完整的描述。从程序来说，也可以说算法是一个有限条指令的集合，这些指令确定了解决某一特定类型问题的运算序列。v对于同一个问题可以有不同的解题方法和步骤，也就是有不同的算法。算法有优劣，一般而言，应当选择简单的、运算步骤少的，既运算快、内存开销小的算法（算法的时空效率）。2.2、简单算法举例例1 求12345。可先写出这样的算法：（1）先求12，得到结果2；（2）将步骤1得到的结果再乘以3，得到结果6；（3）将6再乘以4，得到24；（4）将24再乘以5，得到120。求12345v上述算法太繁琐，我们找一种通用的表示方法。S1:设变量p，被乘数，p=1;s
3、2:设变量i,代表乘数，i=2;s3:使pi,乘积放在被乘数变量p中，可表示为：p i p;s4:使i的值加1，即i+1 i;s5:如果i不大于5，返回重新执行步骤s3以及其后的s4、s5;否则，算法结束。最后得到的p就是5!的值。例2.求13579 11v如果题目改为求13579 11。上述算法稍作改动：s1:1 p;s2:3 i;s3:p i p;s4:i+2 is5:若i11,返回s3;否则，结束。求13579 11 可以看出，用这种方法表示的算法具有通用性、灵活性。S3到s5 组成一个循环，在实现算法时，要反复多次执行s3、s4、s5等步骤，直到某一时刻，执行s5步骤时经过判断，乘数i
4、已超过规定的数值而不返回s3步骤为止。计算机实现循环是轻而易举。求13579 11 请同学们仔细分析循环结束的条件，即s5步骤，如果在求求13579 11时，将s5步骤写成：s5：若i2500,算法停止。（1）使S=0（S作为累加变量）；（2）使N=1（N代表分母）；（3）S+1/N S （执行迭代，S为迭代变量）；（4）N+1 N；（5）若N100，转去执行（3）以及其后的各步骤；否则执行（6）；（6）打印S的值（即所求之总和）。例例5.求下列级数的值求下列级数的值可以写出下面的算法可以写出下面的算法v1、有有穷穷性性：一一个个算算法法应应当当包包含含有有限限的的步步骤骤，而而不不能能是是无
5、无限限的的步步骤骤；同同时时一一个个算算法法应应当当在在执执行行一一定定数数量量的的步步骤骤后后，算算法法结束，结束，不能死循环不能死循环。v事事实实上上“有有穷穷性性”往往往往指指“在在合合理理的的范范围围之之内内”的的有有限限步步骤骤。如如果果让让计计算算机机执执行行一一个个历历时时1000年年才才结结束束的的算算法法，算算法法尽尽管管有有穷穷，但但超超过过了了合合理理的的限限度度，人人们们也也不不认认为为此此算算法法是是有有用用的。的。v2、确确定定性性：算算法法中中的的每每一一个个步步骤骤都都应应当当是是确确定定的的，而而不不是是含含糊糊的的、摸摸棱棱两两可可的的。也也就就是是说说不不
6、应应当当产产生生歧歧义义。特特别别是是算算法用自然语言描述时应当注意这点。法用自然语言描述时应当注意这点。v例例如如：“将将成成绩绩优优秀秀的的同同学学名名单单打打印印输输出出”就就是是有有歧歧义义的的。“成成绩绩优优秀秀”是是要要求求每每门门课课程程都都90分分以以上上，还还是是平平均均成成绩绩在在90分以上？不明确，有歧义，不适合描述算法步骤。分以上？不明确，有歧义，不适合描述算法步骤。2.3.算法的特性v3、有有0个个或或多多个个输输入入（即即：可可以以没没有有输输入入，也也可可以以有有输输入）入）v所所谓谓输输入入是是指指算算法法执执行行时时从从外外界界获获取取必必要要信信息息。（外外
7、界界是是相相对对算算法法本本身身的的，输输入入可可以以是是人人工工键键盘盘输输入入的的数数据据，也可以是程序其它部分传递给算法的数据）也可以是程序其它部分传递给算法的数据）v例例如如：不不需需要要输输入入任任何何信信息息，就就可可以以计计算算出出5！；（0个个输入）输入）v例例如如：如如果果要要计计算算两两个个整整数数的的最最大大公公约约数数，则则需需要要输输入入2个整数个整数m，n。（。（2个输入）个输入）v4、有、有1个或多个输出个或多个输出（即算法必须得到结果）（即算法必须得到结果）v算算法法的的输输出出：算算法法得得到到的的结结果果。算算法法必必须须有有结结果果，没没有有结结果果的的算
8、算法法没没有有意意义义。（结结果果可可以以是是显显示示在在屏屏幕幕上上的的，也可以是将结果数据传递给程序的其它部分）也可以是将结果数据传递给程序的其它部分）v5、有效性、有效性v算算法法的的每每个个步步骤骤都都应应当当能能有有效效执执行行，并并能能得得到到确确定定的的结结果。例如：果。例如：b=0，则执行，则执行a/b是不能有效执行的。是不能有效执行的。2.4.怎样表示一个算法？怎样表示一个算法？为了表示一个算法，可以用不同的方法。常用为了表示一个算法，可以用不同的方法。常用的算法表示方法：的算法表示方法：自然语言，传统流程图，结构化流程图自然语言，传统流程图，结构化流程图（N-S流程图），伪
9、代码、计算机语言等。（重流程图），伪代码、计算机语言等。（重点：点：传统流程图传统流程图，N-S流程图流程图）2.4.1 用自然语言表示算法用自然语言表示算法 自然语言就是人们常用的语言，可以是汉自然语言就是人们常用的语言，可以是汉语、英语或其他语言。语、英语或其他语言。用自然语言表示通俗易懂；用自然语言表示通俗易懂；但文字冗长，容易出现但文字冗长，容易出现“歧义歧义”性；性；而且，用自然语言描述包含分支和循环的而且，用自然语言描述包含分支和循环的算法，不很方便。算法，不很方便。一般不使用自然语言描述算法一般不使用自然语言描述算法例如：描述计算并输出例如：描述计算并输出z=y/x的流程，可以用
10、自然的流程，可以用自然语言描述如下：语言描述如下：（1）输入）输入x，y。（2）判断）判断x是否为是否为0：若若X=0,则输出错误信息；则输出错误信息；否则计算否则计算y/xz，且输出，且输出z。自然语言描述举例自然语言描述举例算法描述语言：是为了说明程序的流程而专门规定的是为了说明程序的流程而专门规定的某种语言。它一般介于自然语言与程序设计语言之间，它某种语言。它一般介于自然语言与程序设计语言之间，它具有自然语言灵活的特点，同时又接近于程序设计语言的具有自然语言灵活的特点，同时又接近于程序设计语言的描述。描述。注意：算法描述语言所描述的流程，一般不能直接作为算法描述语言所描述的流程，一般不能
11、直接作为程序来使用，最后还需转换成用某种程序设计语言所描述程序来使用，最后还需转换成用某种程序设计语言所描述的程序。的程序。与程序设计语言的区别：前者比较自由，不象后者那样受语法的约束，只要描述前者比较自由，不象后者那样受语法的约束，只要描述得人们能理解就行，而不必考虑计算机处理时所要遵循的得人们能理解就行，而不必考虑计算机处理时所要遵循的规定或其它一些细节。规定或其它一些细节。算法描述语言算法描述语言 在程序设计过程中，一般不可能在一开始就用某种程序设计语言编制计算机程序，而是先用某种简单、直观、灵活的描述工具来描述处理问题的流程。当方案确定以后，再将这样的流程转换成计算机程序，这种转换往往
12、是机械的，已经不涉及功能的重新设计或控制流程的变化，而只需考虑程序设计语言所规定的语法要求以及一细节问题。一、流程的描述一、流程的描述2.4.2用流程图表示算法用流程图表示算法流程图：用一些约定的几何图形来描述算法。用某种图流程图：用一些约定的几何图形来描述算法。用某种图框表示某种操作，用箭头表示算法流程框表示某种操作，用箭头表示算法流程流程图（的符号及意义）美国标准化协会流程图（的符号及意义）美国标准化协会ANSI规定了一规定了一些常用的流程图符号，已为世界各国程序工作者普遍采用：些常用的流程图符号，已为世界各国程序工作者普遍采用：起止框输入输出框判断选择框处理框流程线连接点注释框vl起起止
13、止框框：表表示示算算法法的的开开始始和和结结束束。一一般般内内部部只只写写“开开始始”或或“结束结束”。vl l处处理理框框：表表示示算算法法的的某某个个处处理理步步骤骤，一一般般内内部部常常常常填填写写赋赋值操作。值操作。vl l输输入入输输出出框框：表表示示算算法法请请求求输输入入输输入入需需要要的的数数据据或或算算法法将将某些结果输出。一般内部常常填写某些结果输出。一般内部常常填写“输入输入”,“打印打印/显示显示”vl l菱菱形形框框（判判断断框框）：作作用用主主要要是是对对一一个个给给定定条条件件进进行行判判断断，根根据据给给定定的的条条件件是是否否成成立立来来决决定定如如何何执执行
14、行其其后后的的操操作作。它它有有一个入口，两个出口。一个入口，两个出口。vl l连连接接点点：用用于于将将画画在在不不同同地地方方的的流流程程线线连连接接起起来来。同同一一个个编编号号的的点点是是相相互互连连接接在在一一起起的的，实实际际上上同同一一编编号号的的点点是是同同一一个个点点，只只是是画画不不下下才才分分开开画画。使使用用连连接接点点，还还可可以以避避免免流流程程线的交叉或过长，使流程图更加清晰。线的交叉或过长，使流程图更加清晰。vl l注注释释框框：注注释释框框不不是是流流程程图图中中必必须须的的部部分分，不不反反映映流流程程和和操操作作，它它只只是是对对流流程程图图中中某某些些框
15、框的的操操作作做做必必要要的的补补充充说说明明，以帮助阅读流程图的人更好地理解流程图的作用。以帮助阅读流程图的人更好地理解流程图的作用。例：例：求求5 5！t=1i=2t=t*ii=i+1i5结束 NY 开始v传传统统流流程程图图采采用用流流程程线线指指出出各各框框的的执执行行顺顺序序，对对流流程程线线的的使使用用没没有有严严格格限限制制。因因此此，使使用用者者可可以以不不受受限限制制地地使使流流程程转转来来转转去去，使使流流程程图图变变得得毫毫无无规规律律。人人们们对对这这种种流流程程图图进进行行改改进进，规规定定几几种种基基本本的的结结构构，然然后后由由这这些些基基本本结结构构按按一一定定
16、规规律律组组成成算算法法结结构构，整整个个算算法法结结构构是是由由上上而而下下地地将将各各个个基基本本结结构构顺顺序序排排列列起起来来。这这样样可可以以在在一一定定程程度度上上，提高算法的质量。提高算法的质量。三种基本结构是：（1）顺序结构 按指令的顺序依次执行（2）判断选择结构：根据判别条件有选择地改变 执行流程（3）循环结构：有条件的重复地执行某个程序块2.4.3 三种基本结构和改进的流程图三种基本结构和改进的流程图(1)顺序结构程序设计v依次顺序执行程序语句 执行执行a块块执行执行b块块a块块b块块AB例如，令例如，令a、b的值的值分别为分别为5、10；a=5；b=10；(2)判别选择结
17、构程序设计v首先判别条件，若条件满足，程序执行a块，否则，执行b块；v举例，求a、b两个 数中的最大值；满足条件否满足条件否满足满足不满足不满足执行执行a块块执行执行b块块条件成立？条件成立？执行执行a块块执行执行b块块成立成立不成立不成立bmax？Max=a；max=b；YN(3)循环结构程序设计v循环又分“当型循环”和“直到型循环”v举例，求1100的累加和。int i，sum=0；while（i=100)sum=sum+i;i=i+1;直到条件满足为止直到条件满足为止执行循环中的指令执行循环中的指令当条件满足时当条件满足时执行循环中指令执行循环中指令i5打印打印t当型循环：当型循环：当条
18、件当条件p成立时，反复执行循成立时，反复执行循环体中指令，直到环体中指令，直到p条件不成立为止。当型条件不成立为止。当型循环先判断，再决定是否执行循环体，所以循环先判断，再决定是否执行循环体，所以在条件在条件p一次都不满足时，循环体可能一次一次都不满足时，循环体可能一次都不执行都不执行当条件当条件p满足时满足时执行循环中指令执行循环中指令直直到到型型循循环环：当当条条件件p不不成成立立时时，反反复复执执行行循循环环体体中中的的指指令令，直直到到p条条件件成成立立为为止止。直直到到型型循循环环先先执执行行循循环环体体，然然后后再再判判断断条条件件p，所以循环体至少执行一次。，所以循环体至少执行一
19、次。直到条件直到条件p满足为止满足为止执行循环中的指令执行循环中的指令2.4.5用伪代码表示算法用伪代码表示算法用伪代码表示算法（常常用于算法设计）用伪代码表示算法（常常用于算法设计）用传统流程图、用传统流程图、N-S图表示算法，直观易懂，但绘制图表示算法，直观易懂，但绘制比较麻烦，在设计一个算法时，可能要反复修改，而比较麻烦，在设计一个算法时，可能要反复修改，而修改流程图是比较麻烦的，因此，流程图适合表示算修改流程图是比较麻烦的，因此，流程图适合表示算法，但在设计算法过程中使用不是很理想。为了设计法，但在设计算法过程中使用不是很理想。为了设计算法方便，常使用伪代码工具。算法方便，常使用伪代码
20、工具。伪代码是用介于自然语言和计算机语言之间的文字和伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。伪代码不用图形符号，书写方便，符号来描述算法。伪代码不用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡格式紧凑，便于向计算机语言算法过渡 用某种程序设计语言编写的程序本质上也是问题处理方案的描述，并且是最终的描述。在一般的程序设计过程中，不提倡一开始就编写程序，特别是对于大型的程序。程序是程序设计的最终产品，需要经过每一步的细致加工才能得到，如果企图一开始就编写出程序，往往会适得其反，达不到预想的结果。2.4.6 用计算机语言表示算法用计算机语言表示算法例题例题例例2.20
21、求求5！，用！，用C语言表示语言表示Main()inti,t;t=1;i=2;while(i=5)t=t*i;i=i+1;printf(“%d”,t);例例求级数的值求级数的值Main()intsign=1;floatdeno=2.0,sum=1.0,term;while(deno=100)sign=-sign;term=sign/deno;sum=sum+term;deno=deno+1;printf(“%f”,sum);一、用计算机解决问题的过程一、用计算机解决问题的过程提出、分析提出、分析问题问题确定算法确定算法模型模型设计设计算法算法编写编写程序程序调试调试程序程序分析输出分析输出结果
22、结果正确正确合理合理结束结束不正确不正确2.5结构化程序设计方法结构化程序设计方法二、结构化程序设计思想二、结构化程序设计思想例：给例：给100个整数，打印输出其中的素数个整数，打印输出其中的素数基本思路：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。具体采用以下方法保证得到结构化的程序：自顶向下自顶向下 逐步细化逐步细化 模块化设计模块化设计 结构化编码结构化编码输入输入100个数存入个数存入x1，x2,x100打印打印x1.x100中中不等于不等于0的数的数S1NS流程图流程图让让x1x2,x100中的非素变为中的非素变为0S3S2输入输入xi当
23、当i=100i=i+1i=1S1细化细化xi0当当i=100i=i+1i=1YN打印打印xiS3细化细化输入输入100个数存入个数存入X1，x2,x100打印打印1.x100中不等于中不等于0的数的数S1NS流程图流程图让让x1，x100中的非素中的非素变为变为0S3S2判断判断xi是否是素数，是否是素数，若不是则将若不是则将xi=0当当isqrt(xi)S21细化细化输入输入xi当当i=100i=i+1i=1当当isqrt(xi)i=i+1xi0当当i=100i=i+1i=1YN打印打印xi输入输入100个数存入个数存入X1，x2,x100打印打印x1.x100中不等中不等于于0的数的数让让x1，x100中的非中的非素变为素变为0细化后的流程图细化后的流程图