C语言程序设计_2 第6章算法初步.ppt

《C语言程序设计_2 第6章算法初步.ppt》由会员分享，可在线阅读，更多相关《C语言程序设计_2 第6章算法初步.ppt（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6 6章章 算法初步算法初步6.1 算法的概念算法的概念6.2 算法的表示方法算法的表示方法6.3 结构化程序设计结构化程序设计退出退出6.1 算法的概念算法的概念6.1.1 6.1.1 6.1.1 6.1.1 什么是算法什么是算法什么是算法什么是算法 当我们要编写一个程序的时候，我们总要首先想好这个程序当我们要编写一个程序的时候，我们总要首先想好这个程序是干什么的？应该如何实现这些目标？应该先进行什么处理、后是干什么的？应该如何实现这些目标？应该先进行什么处理、后进行什么处理？所处理的数据的格式是是什么？遇到一些复杂的进行什么处理？所处理的数据的格式是是什么？遇到一些复杂的问题，我们可能

2、还需要考虑采用什么数学方法。这一切都涉及一问题，我们可能还需要考虑采用什么数学方法。这一切都涉及一个专业名词个专业名词“算法算法”。所谓算法，就是程序处理问题的步骤与方法。所谓算法，就是程序处理问题的步骤与方法。很多时候，程序设计者所面临的问题就是寻找一个合适的算法。很多时候，程序设计者所面临的问题就是寻找一个合适的算法。例如，一个熟练的程序员，要设计一个下例如，一个熟练的程序员，要设计一个下“五子棋五子棋”的游戏程序，的游戏程序，对他而言，对他而言，C语言的编程规则已经清楚。他所面对的核心问题是语言的编程规则已经清楚。他所面对的核心问题是寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具

3、有寻找一种可以模拟人下棋的算法。因此，算法在软件设计中具有重要的地位。正如著名的计算机科学家沃思（重要的地位。正如著名的计算机科学家沃思（Nikiklaus Wirth）所指出的如下公式：所指出的如下公式：程序程序=数据结构数据结构+算法算法6.1.26.1.26.1.26.1.2算法的特性算法的特性算法的特性算法的特性 一一个个方方法法要要成成为为我我们们可可以以在在程程序序设设计计中中所所使使用用的的算算法法，需需要要具具备如下特征。备如下特征。1有穷性有穷性 一一个个算算法法要要在在有有限限的的步步骤骤内内解解决决问问题题（这这里里所所说说的的步步骤骤是是指指计计算算机机执执行行步步骤骤

4、）。计计算算机机程程序序不不能能无无限限地地运运行行下下去去（甚甚至至不不能能长长时时间间地地运运行行下下去去），所所以以一一个个无无限限执执行行的的方方法法不不能能成成为为程程序序设设计计中的中的“算法算法”。例如，求某一自然树例如，求某一自然树N的阶乘：的阶乘：N！=1*2*3*.*N 这这是是一一个个算算法法。因因为为对对任任何何一一个个自自然然数数而而言言，无无论论这这个个数数多多大大，总是有限的。用这个公式计算总是有限的。用这个公式计算N！总是需要有限的步骤。总是需要有限的步骤。但是，以下计算公式则不能作为算法，因为其计算步骤是无但是，以下计算公式则不能作为算法，因为其计算步骤是无限

5、的：限的：SUM=1+1/1+1/2+1/3+.+1/n+.事事实实上上有有穷穷性性是是指指合合理理的的范范围围之之内内，比比如如，设设计计了了一一个个算算法法是是有有限限的的，但但按按照照目目前前计计算算机机发发展展的的水水平平要要计计算算1000年年才才能能完完成成，这样的算法没有实际意义，可以不当作算法，可以视为无穷。这样的算法没有实际意义，可以不当作算法，可以视为无穷。实实际际上上，在在计计算算机机的的许许多多加加密密算算法法中中，可可以以解解密密的的方方法法不不是是不不存存在在，而而是是要要执执行行这这样样的的解解密密算算法法需需要要极极其其大大量量的的时时间间。这这样样就就实现了保

6、密。所谓保密就是让在一定的时间内信息不被他人知晓。实现了保密。所谓保密就是让在一定的时间内信息不被他人知晓。当当然然，计计算算机机技技术术的的进进步步回回对对算算法法有有影影响响。对对于于现现在在的的计计算算机机1000年年才才能能完完成成的的算算法法可可能能几几个个月月的的功功夫夫就就能能完完成成，到到那那时时某某些现在无穷性的方法将变成切实可行的算法。些现在无穷性的方法将变成切实可行的算法。2 确定性确定性 算算法法中中操操作作步步骤骤的的顺顺序序和和每每一一个个步步骤骤的的内内容容都都应应当当是是确确定定的的，不不应应当当是是含含糊糊不不清清的的。它它也也不不能能有有不不同同的的解解释释

7、存存在在，即即不不能能具具有有“二义性二义性”，不应当产生两种或多种以上的含义。，不应当产生两种或多种以上的含义。3 有零个或多个输入有零个或多个输入 输输入入就就是是从从外外界界取取得得必必要要的的信信息息。一一个个算算法法可可以以有有零零个个或或多多个个输输入入，例例如如：输输入入一一个个年年份份，判判断断其其是是否否是是闰闰年年。同同时时一一个个算算法法可以没有输入，例如：计算出可以没有输入，例如：计算出5！是多少。！是多少。4 有一个或多个输出有一个或多个输出 算算法法的的目目的的就就求求解解，“解解”就就是是我我们们想想要要得得到到的的最最终终结结果果。输输出出是是同同输输入入有有着

8、着某某些些特特定定关关系系的的量量。一一个个算算法法得得到到的的最最终终结结果果就就是输出。没有输出的算法是没有意义的。是输出。没有输出的算法是没有意义的。5 可执行性可执行性 一一个个算算法法应应当当是是可可以以由由计计算算机机执执行行的的，算算法法中中描描述述的的操操作作都都是是可以通过计算机的运行来实现。可以通过计算机的运行来实现。6.1.3 6.1.3 6.1.3 6.1.3 算法设计的要求算法设计的要求算法设计的要求算法设计的要求 什什么么样样的的算算法法是是好好的的算算法法呢呢？我我们们在在设设计计算算法法时时应应向向哪哪些些方方面面努力呢？一般包括以下这几个方面。努力呢？一般包括

9、以下这几个方面。1 正确性正确性 一一个个算算法法应应当当能能够够解解决决具具体体问问题题。其其“正正确确性性”可可分分为为以以下下几几个方面：个方面：l不含逻辑错误；不含逻辑错误；l对于几组输入数据能够得出满足要求的结果；对于几组输入数据能够得出满足要求的结果；l对于精心选择的典型、苛刻的输入数据都能得到要求的结果；对于精心选择的典型、苛刻的输入数据都能得到要求的结果；对于一切合法的输入都能输出满足要求的结果；对于一切合法的输入都能输出满足要求的结果；2 可读性可读性 算算法法应应该该可可以以用用能能够够被被人人理理解解的的形形式式表表示示。太太复复杂杂的的、不不能能被被程序员所理解的算法难

10、以在程序设计中采用。程序员所理解的算法难以在程序设计中采用。3 健壮性健壮性 健健壮壮性性指指算算法法具具有有抵抵御御“恶恶劣劣”输输入入信信息息的的能能力力。当当输输入入数数据据非非法法时时，算算法法也也能能适适当当的的作作出出反反应应或或进进行行处处理理，而而不不会会产产生生莫莫明明其其妙妙的的输输出出结结果果。例例如如，当当输输入入三三个个边边的的长长度度值值来来计计算算三三角角形形的的面面积积时时，一一个个有有效效的的算算法法在在三三个个输输入入数数据据不不能能构构成成一一个个三三角角形形时时，应应报报告告输输入入的的错错误误，应应返返回回一一个个表表示示错错误误或或错错误误性性质质的

11、的值值并并中中止止执行。执行。4 效率与低存储量的需求效率与低存储量的需求 高高效效率率和和低低存存储储量量是是优优秀秀程程序序员员追追求求的的目目标标。效效率率指指的的是是算算法法执执行行时时间间，对对于于一一个个问问题题如如果果有有多多个个算算法法可可以以解解决决，执执行行时时间间短短的的算算法法效效率率高高。存存储储量量需需求求指指算算法法执执行行进进程程所所需需要要的的最最大大存存储储空空间间。效效率率与与低低存存储储量量需需求求这这两两者者都都与与问问题题规规模模有有关关。占占用用存存储储量量最最小小、运运算算时时间间最最少少的的算算法法就就是是最最好好的的算算法法。但但是是，在在实

12、实际际中中，运运行行时时间间和和存存储储空空间间往往往往是是一一对对矛矛盾盾。要要根根据据具具体体情情况况选选择择更更优优先考虑哪一个因素。先考虑哪一个因素。6.2 算法的表示方法算法的表示方法 算算法法的的实实质质是是一一种种逻逻辑辑关关系系。对对于于这这样样一一种种关关系系，可可以以用用多多种种方方式式来来表表达达。常常用用的的有有自自然然语语言言、流流程程图图（传传统统的的流流程程图图和和结结构构化化的的流流程图）、伪代码、程图）、伪代码、N-S流程图、计算机语言等。流程图、计算机语言等。6.2.1 6.2.1 6.2.1 6.2.1 自然语言表示算法自然语言表示算法自然语言表示算法自然

13、语言表示算法 自然语言是相对于计算机语言而言的。就是指人们在日常生自然语言是相对于计算机语言而言的。就是指人们在日常生活中使用的语言，如汉语、英语、发语等。对于某些程序员来说，活中使用的语言，如汉语、英语、发语等。对于某些程序员来说，自然语言通俗易懂。但是，对于规模大、复杂的算法，使用自然自然语言通俗易懂。但是，对于规模大、复杂的算法，使用自然语言来描述，往往很冗长，不直观，而且容易发生歧义。比如对语言来描述，往往很冗长，不直观，而且容易发生歧义。比如对于以下这句话：如果于以下这句话：如果A大于大于B，就给它加就给它加1。在理解时就可能出现。在理解时就可能出现歧义，是给歧义，是给A加加1？还是

14、给？还是给B加加1。对于以上的一段话，如果我们用对于以上的一段话，如果我们用C语言进行编程则为：语言进行编程则为：if(AB)A=A+1;正是由于自然语言描述算法具有的缺陷，所以在程序设计中正是由于自然语言描述算法具有的缺陷，所以在程序设计中没有人使用。没有人使用。6.2.2 6.2.2 6.2.2 6.2.2 传统流程图表法传统流程图表法传统流程图表法传统流程图表法 流流程程图图表表示示法法就就是是用用各各种种图图框框表表示示各各种种操操作作。这这种种表表示示法法的的优优点点是是直直观观易易于于理理解解。流流程程图图表表示示法法是是美美国国国国家家标标准准化化协协会会ANSI（Amreica

15、n National Standard Institute）规规定定的的。一一些些常常用的流程图符号在用的流程图符号在Word中都可以通过中都可以通过“绘图绘图”命令来绘制。命令来绘制。6.2.3 6.2.3 6.2.3 6.2.3 用用用用N-SN-SN-SN-S流程图表示算法流程图表示算法流程图表示算法流程图表示算法 1973年年美美国国学学者者I.Nassi 和和B.Shneiderman提提出出了了一一种种新新的的流流程程图图形形式式。在在这这种种流流程程图图中中，完完全全去去掉掉了了带带箭箭头头的的流流程程线线。全全部部算算法法都都是是在在一一个个矩矩形形框框内内，在在该该框框内内还

16、还包包含含其其它它的的从从属属于于它它的的框框。式式者者说说由由一一些些基基本本的的框框组组成成一一个个大大框框。这这种种方方法法就就以以这这两两位位学学者者的名字缩写而成，被称为的名字缩写而成，被称为“NS盒图盒图”。N-S盒图可以表示以下几种典型结构。盒图可以表示以下几种典型结构。1 顺序结构顺序结构 在顺序结构中，算法的步骤是依照先后顺序依此执行的。即在顺序结构中，算法的步骤是依照先后顺序依此执行的。即执行完第一步骤后，再执行第二步骤。执行完第一步骤后，再执行第二步骤。2 选择结构选择结构 选择结构也叫做条件选择。即根据某一条件选择下一步的执选择结构也叫做条件选择。即根据某一条件选择下一

17、步的执行操作。如图行操作。如图6-4和图和图6-5所示。所示。3 循环结构循环结构 循环结构就是当某一条件满足或不满足时，一直执行某些操循环结构就是当某一条件满足或不满足时，一直执行某些操作的算法。它可以再细分为以下两种：作的算法。它可以再细分为以下两种：当型循环。当某一条件满足时一直执行某些操作。当型循环。当某一条件满足时一直执行某些操作。直到型循环。就是一直执行某些操作，直到某一条件不满足直到型循环。就是一直执行某些操作，直到某一条件不满足时为止。时为止。6.2.4 6.2.4 6.2.4 6.2.4 用伪码表示算法用伪码表示算法用伪码表示算法用伪码表示算法 所谓所谓“伪代码伪代码”就是程

18、序员自己定义的一种就是程序员自己定义的一种“语言体系语言体系”，它不同于自然语言（比自然语言简单），也不同于任何一种具体它不同于自然语言（比自然语言简单），也不同于任何一种具体的计算机语言（这样才有广泛性）。它有自己的文字和符号体系，的计算机语言（这样才有广泛性）。它有自己的文字和符号体系，用来描述算法。它比自然语言更接近计算机语言。便于向计算机用来描述算法。它比自然语言更接近计算机语言。便于向计算机语言过渡。语言过渡。并不是每一个程序员都需要也都可以定义并不是每一个程序员都需要也都可以定义“伪码伪码”。因为你。因为你自己定义一套伪码供自己一个人使用没有太大的意义。一般而言，自己定义一套伪码供

19、自己一个人使用没有太大的意义。一般而言，一个一个“伪码体系伪码体系”是由很大的软件公司定义，供全公司的程序员是由很大的软件公司定义，供全公司的程序员使用。使用。6.3 结构化程序设计结构化程序设计6.3.1 6.3.1 6.3.1 6.3.1 三种基本结构三种基本结构三种基本结构三种基本结构 传统的流程图用流程线描述各框的执行顺序。但对流程线的传统的流程图用流程线描述各框的执行顺序。但对流程线的使用并没有严格的限制，因此，若使用者不受限制的随意转移流使用并没有严格的限制，因此，若使用者不受限制的随意转移流程时，就变得很混乱。实际上，即便程序员努力控制流程的变化，程时，就变得很混乱。实际上，即便

20、程序员努力控制流程的变化，但当算法复杂时，流程图往往不可避免地变得复杂和混乱。而但但当算法复杂时，流程图往往不可避免地变得复杂和混乱。而但结构异常复杂时，结构异常复杂时，“NS盒图盒图”也很复杂。那么，能不能只使用也很复杂。那么，能不能只使用几种基本的结构，来组合表达出各种复杂的算法结构呢？几种基本的结构，来组合表达出各种复杂的算法结构呢？1966年，年，Bohra和和Jacopini给出了肯定的答案。他们证明了：给出了肯定的答案。他们证明了：使用顺序、分支（也叫做使用顺序、分支（也叫做“条件选择条件选择“）和循环这三种基本结构）和循环这三种基本结构可以表示任何一个算法的基本单元。可以表示任何

21、一个算法的基本单元。这正是我们在以上只讲述这三种基本结构的原因。这正是我们在以上只讲述这三种基本结构的原因。6.3.2 6.3.2 6.3.2 6.3.2 结构化程序设计结构化程序设计结构化程序设计结构化程序设计 从从目目前前的的编编程程实实践践看看，结结构构化化程程序序设设计计的的思思路路已已经经被被绝绝大大多多数数程程序序员员所所接接受受。人人们们普普遍遍认认为为，必必须须采采用用结结构构化化的的程程序序设设计计方方法法。因因为为结结构构化化程程序序具具有有结结构构清清晰晰、便便于于阅阅读读、便便于于修修改改和和便便于于维维护护的优点。的优点。结结构构化化程程序序设设计计的的基基本本思思路

22、路是是：把把一一个个复复杂杂的的问问题题的的求求解解过过程程分分阶阶段段进进行行，每每个个阶阶段段处处理理的的问问题题都都控控制制在在人人们们容容易易理理解解的的范范围围之之内。采取以下的方法保证得到结构化的程序：内。采取以下的方法保证得到结构化的程序：自顶向下；自顶向下；逐步细化（求精）；逐步细化（求精）；模块化设计；模块化设计；结构化编码。结构化编码。采采用用自自顶顶向向下下、逐逐步步细细化化的的方方法法可可以以使使程程序序的的结结构构清清晰晰、层层次次分分明明、容容易易改改写写。就就象象进进行行房房屋屋设设计计所所采采用用的的施施工工步步骤骤一一样样：先先进进行行整整体体的的规规划划，画

23、画出出施施工工的的图图纸纸，再再进进行行各各个个部部分分的的设设计计，最最后后进进行行细细节节的的设设计计（楼楼宇宇通通信信系系统统、安安全全设设施施的的装装备备、办办公公系系统统、室内的装修）。室内的装修）。结构化程序具有如下的特征：结构化程序具有如下的特征：一个程序单元由顺序、分支和循环这三种基本结构组成；一个程序单元由顺序、分支和循环这三种基本结构组成；一个大的程序由若干个不同功能的小模块组成；一个大的程序由若干个不同功能的小模块组成；每一个小模块只用一个入口和一个出口；每一个小模块只用一个入口和一个出口；6.3.3 6.3.3 6.3.3 6.3.3 结构化程序设计中的注意事项结构化程

24、序设计中的注意事项结构化程序设计中的注意事项结构化程序设计中的注意事项 在在我我们们使使用用这这三三种种基基本本结结构构来来构构造造程程序序模模块块时时，应应该该注注意意下下述述事项。事项。1 不可交叉不可交叉 在在顺顺序序结结构构、循循环环结结构构和和分分支支结结构构之之间间，允允许许互互相相嵌嵌套套（参参见见图图6-10），但但不不允允许许交交叉叉。具具体体地地说说，循循环环结结构构和和循循环环结结构构之之间间不不能能交交叉叉、分分支支结结构构和和分分支支结结构构之之间间不不能能交交叉叉、循循环环结结构构和和分分支支结构之间不能交叉。结构之间不能交叉。另外，循环和分支之间也不能交叉。另外，

25、循环和分支之间也不能交叉。【例【例6-1】(见课本）见课本）【例【例6-2】(见课本）见课本）同同样样的的道道理理，不不能能在在一一个个循循环环体体中中包包括括分分支支的的一一支支，而而在在另另一一循环体中，包含分支的另一支。这也交叉了。循环体中，包含分支的另一支。这也交叉了。在在具具体体编编程程实实践践中中，较较多多出出现现的的编编程程错错误误是是：分分支支与与分分支支交交叉、循环与循环交叉。分支与循环交叉这类错误并不多见。叉、循环与循环交叉。分支与循环交叉这类错误并不多见。2 不可从循环体外转入循环体内不可从循环体外转入循环体内 在在结结构构化化程程序序设设计计中中，我我们们强强调调一一个

26、个程程序序模模块块具具有有单单入入口口和和单单出出口口。一一般般不不允允许许从从循循环环体体内内转转到到循循环环体体外外（当当有有多多层层循循环环时时，特特别别强强调调这这一一点点）。值值得得特特别别说说明明的的时时，绝绝对对不不允允许许从从循循环环体体外外转到循环体内。转到循环体内。6.3.4 6.3.4 6.3.4 6.3.4 算法的合理性与优化算法的合理性与优化算法的合理性与优化算法的合理性与优化 在在一一个个算算法法被被设设计计出出来来之之后后，要要考考虑虑其其合合理理性性。如如果果可可能能，要要对其优化。对此，我们通过以下两个例子来说明。对其优化。对此，我们通过以下两个例子来说明。【例【例6-3】(见课本）见课本）【例【例6-4】(见课本）见课本）