第2章-算法概要.ppt

1、第二章，程序的灵魂算法，主要内容，2.1算法的概念，2.2简单算法的例子，2.3算法的特点，2.4如何表示算法，2.5结构化编程方法，2.1算法的概念，广义上讲，解决问题所采取的方法和步骤称为“算法”。算法：解决问题的有限步骤。计算机算法：如何使计算机逐步工作的具体过程。2.1算法的概念和用计算机处理问题的步骤：1)设计好算法；2)用计算机语言实现算法编程。算法必须是“有效的”。算法设计还应充分考虑算法的质量。衡量算法质量的主要标准：简明程序。执行速度很快。占用更少的空间。2.1算法的概念，计算机算法可分为两类：数值算法：寻找数值解，如寻找方程的根，寻找函数的定积分等。非数字运算：它涵盖了广泛

2、的领域，最常见的是用于交易管理领域，如图书检索、人事管理、交通调度管理等。2.2简单算法示例，示例2.1:查找12345，步骤1:首先查找12，获得结果2，步骤2:将步骤1中获得的乘积2乘以3，获得结果6，步骤3:将6乘以4，获得24，步骤4:将24乘以5，获得120，这太麻烦了。如果你要求121000，你应该写99个步骤。S2:让我=2。S3:把和乘积保留在变量p中，变量p可以表示为=p。S4:把I的值增加1，即I=I.S5:如果I不大于5，返回重新执行步骤S3以及后续步骤S4和S5；否则，算法结束。p的最终值是5！的价值。2=1 * 23=21，6=2 * 34=31，24=6 * 45=

3、41，120=24 * 56=51，i5结束，S1: 1ps2: 3is3: pips4: i2is5:如果i11，返回s3。否则，结束。如果标题改为：13511算法只需要几处修改；算法简洁，用这种方法表达的算法具有通用性和灵活性。S3到S5构成一个循环，当实现该算法时，应重复执行S3、S4、S5等步骤，直到某个时刻，当执行S5时，判断乘数I已超过规定值，不返回步骤S3。这时，算法结束，变量p的值就是结果。有50名学生被要求打印出那些分数超过80分的。S1: 1is2:如果将打印gi80、ni和gi，则不会打印。S3:i1 S4:如果i50，返回S2并继续执行。否则，算法结束，变量I被用作下标

4、来控制序列号(哪个学生，哪个分数)。当我超过50时，意味着50名学生的分数已经被处理，算法结束。示例2.3确定20002500年的每一年是否为闰年，并输出结果。分析：闰年的条件如下：(1)所有能被4整除但不能被100整除的年份都是闰年，如1996年和2004年；(2)可被100和400整除的年份是闰年。例如，1600年和2000年是闰年。不符合这两个条件的一年不是闰年。假设Y是要检测的年份，算法可以表示如下：S1:2000年2月2日：如果Y不能被4整除，Y就不是闰年。然后转到S6。S3:如果y能被4整除，但不能被100整除，那么y输出为“闰年”。然后转到S6。S4:如果y能被100和400整除

5、，输出y就是“闰年”。然后转到S6。S5:输出y“不是闰年”。S6: y1ys7:当y2500时，转向S2继续执行，例如y2500，算法停止。上述算法中的每一步都分离一些范围(可以判断为闰年或非闰年)，并逐渐缩小范围，直到执行S5，S5只能是非闰年。“其他”包括可被4和100除尽但不能被400除尽的年份(如1990年)。例2.4，算法如下：S1:符号=1s 2:sum=1s 3:deno=2s 4:sign=(-1)sign 5:term=sign(1/deno)S6:sum=sum term S7:deno=deno 1s 8:如果deno100返回s4，否则，算法用词作为变量名，使算法更容

6、易理解：sum代表累计总和，deno是英文分母的缩写，sign代表数值的符号，term代表某个术语。重复步骤S4至S8，直到分母大于100。总共执行了99个循环，并将99个分数相加。和的最终值是多项式的值。对于大于或等于3的正整数，判断它是否是素数。概念：所谓质数是指除了1和数本身之外，不能被任何整数整除的数。例如，13是一个素数。因为它不能被2，3，4，12整除。分析：判断一个数n(n3)是否为素数的方法：取N为被除数，依次取2到(n-1)之间的每个整数为除数。如果它们都不能被整除，那么N就是质数。算法如下：S1:输入n的值S2: I=2 (I为除数)S3:n除以I得到余数r S4:如果r=

7、0，这意味着n可以被I整除，然后打印n“不是素数”，算法结束。否则，执行S5:1I 6:如果在-1，返回S3。否则，打印n“是一个质数”。然后结束。实际上，n不需要除以2到(n-1)的整数，只需要除以2到n/2的整数，甚至是2到1的整数。2.3算法的特点，有限性：它包含有限的操作步骤。决定性的：算法中的每一步都应该是决定性的。有零个或多个输入：输入是指在执行算法时需要从外部世界获得必要的信息。有一个或多个输出：算法的目的是求解，而“解”就是输出。有效性：算法中的每一步都应该得到有效的执行，并得到明确的结果。一个算法应该具有以下特征：2.4.1该算法是用自然语言表达的，自然语言是人们日常使用的语

8、言，可以是汉语、英语或其他语言。在自然语言中很容易理解，但是单词很长，容易出现歧义。2.4算法表示，2.4.2算法表示通过流程图，ANSI(美国国家标准协会)指定了一些常用的流程图符号：例2.6将找到5！该算法用流程图表示。如果需要打印最终结果，可以在菱形框下添加一个输出框。在示例2.7中，示例2.2中的算法由流程图表示。打印学生人数和分数超过80的50名学生的分数。如果包含该输入数据部分，流程图为例2.8。例2.3中判断闰年的算法用流程图表示，比用文字描述算法更清楚、更容易理解。在例2.9中，例2.4中的算法用流程图表示，而在例2.10中，例2.5中判断素数的算法用流程图表示。流程图包括以下

9、部分：(1)代表相应操作的方框；(2)带箭头的流线；(3)框内外必要的文字。2.4.3三个基本结构和改进的流程图，1。传统流程图的缺点传统流程图使用流程线来指出每个帧的执行顺序，并且对流程线的使用没有严格的限制。因此，用户可以不受限制地随意翻转流程，使得流程图不规则，而且读者必须花费大量的精力来跟踪流程，这使得人们很难理解算法的逻辑。如图所示，传统流程图的流程可以是：这种混沌算法称为BS型算法，意思是一碗没有线索的意大利面。缺点：难以读取和修改，使得算法的可靠性和可维护性难以保证。解决方法：必须限制箭头的滥用，即不允许随意翻转过程，只能按顺序进行。2.三个基本结构博赫拉和贾科平提出了以下三个基

10、本结构：序列结构、选择结构和循环结构，它们被用作表示一个好算法的基本单位。三种基本结构的图解：顺序结构、选择结构、循环结构示意图：While型循环结构、直到型循环结构，三种基本结构的共同特征：(1)只有一个入口。(2)只有一个出口。(请注意，菱形判断框有两个出口，而选择结构只有一个出口。不要混淆钻石盒的出口和选择结构的出口。(3)结构的每个部分都有被执行的机会。(4)结构中没有“无限循环”。在图中，从入口到出口没有穿过A盒的路径。错误的过程表示：过程中的无限循环，总结：以及由三个基本结构序列组成的算法结构可以解决任何复杂的问题。由基本结构组成的算法属于“结构化”算法，它没有不规则的转弯，只允许

11、在这个基本结构中分支和向前或向后跳跃。extension:只要它具有上述四个特征，它就可以作为基本结构使用。你可以定义自己的基本结构，这些基本结构构成了一个结构化的程序。此图符合基本结构的特征，即多分支选择结构，并根据表达式的值确定执行路线。虚线框中的结构是一个入口和一个出口，具有上述四个特征。如此构造的算法结构也是结构化算法。可以认为这源于三个基本结构。2.4.4该算法由南北流程图表示。1973年，美国学者纳西和施耐德曼提出了一种新的流程图形式。在该流程图中，带有箭头的流程线被完全删除。所有的算法都写在一个矩形框中，这个矩形框也可以包含其他的附属框，或者由一些基本框组成的大框。这个流程图也被

12、称为南北结构流程图。N-S流程图标有以下流程图符号：(1)顺序结构，(2)选择结构，(3)循环结构。复杂的南北流程图可以用三个南北流程图的基本框架组成。图中的A框或B框可以是简单的操作，也可以是三种基本结构之一。a框可以是选择结构，b框可以是循环结构，例2.11将是5！该算法用N-S图表示，例2.2的算法用例2.12的N-S图表示。(打印学生人数和分数高于80分的50名学生的分数)，没有输入数据。在示例2.12中，示例2.2的算法由南北图表示。(打印50名学生中得分高于80分的学生人数和成绩)，并输入数据。例2.13用N-S图展示例2.3中判断闰年的算法，例2.14用N-S图展示例2.4中的算

13、法，例2.15用N-S流程图展示例2.5中判断素数的算法。传统流程图分析：此图不符合基本结构特征！因为它不能分解成三个基本结构，所以不能直接用流程图三个基本结构的符号来表示。因此，必须首先进行必要的改造。在例2.15中，例2.5中判断素数的算法用N-S流程图表示。将传统流程图转化为N-S流程图，体现了算法的优势，比文本描述更加直观、生动、易懂；比传统流程图更紧凑，更易于绘制。特别是取消了流线，整个算法结构由每个基本结构依次组成。南北流程图中的上下顺序是执行顺序。用N-S图表示的算法都是结构化算法，因为它们不可能不规则地跳转，只能从上到下依次执行。概要：结构化算法由一些基本的结构序列组成。基本结

14、构之间没有向前或向后的跳跃，过程的转移只存在于基本结构中(如循环中的过程跳跃)；非结构化算法可以被等价的结构化算法代替，并且其功能保持不变。如果一个算法不能被分解成几个基本结构，它肯定不是一个结构化的算法。2.4.5该算法由伪代码表示。概念：伪代码用自然语言和计算机语言之间的字符和符号描述算法。特点：它像一篇文章一样从上到下写。每一行(或多行)代表一个基本操作。它不使用图形符号，所以写起来方便，格式紧凑，容易理解，并且容易过渡到计算机语言算法(即程序)。有用性：适用于设计过程中需要反复修改的过程描述。，也可以用中文伪代码表示：如果x是正打印x，否则打印-x可以用中文和英文混合，例如，如果x是正

15、打印x else打印-x，例如，“打印x的绝对值”的算法可以用伪代码表示为：如果x是正的，则打印x ELSE打印-x，将t的初始值设置为1，将I的初始值设置为2。当i=5时，执行以下操作：让t=ti使i=i 1的循环体在此结束，并输出t的值，该值也可以写成以下形式：BEGIN算法开始1t 2 i，而i5 t1 I 1 I打印t END算法结束，示例2.16要求5！示例2.17输出学生人数和分数高于80的50名学生的分数。BEGIN算法在i50输入ni和gi i1 I时开始1i，而i50如果gi80打印ni和gi i1i结束算法结束，2.4.6用计算机语言表达算法，概念：用计算机实现算法。计算机

16、无法识别流程图和伪代码。只有用计算机语言编写的程序才能被计算机执行。因此，在用流程图或伪代码描述一个算法之后，它应该被转换成一个计算机语言程序。特点：用计算机语言表达的算法必须严格遵循所用语言的语法规则，这不同于伪代码。用途：完成一项任务，包括设计算法和实现算法。设计算法的目的是实现算法。#包括void main() int i，t；t=1；I=2；而(I=5)t=t * I；I=I 1；printf(%dn，t)；在情况2.20中，在情况2.16 (5！)用c语言表示。应该强调的是，C程序是写的，但它仍然只描述算法，而没有实现它。只有运行的程序才是实现算法。应该说，用计算机语言表达的算法是计算机可以执行的算法。2.5结构化编程方法，结构化程序是用高级语言表达的结构化算法。一个由三个基本结构组成的程序必须是一个结构化的程序，易于编写、读取、修改和维护。结构化编程强调编程风格和结构的标准化，提倡清晰的结构。结构化编程方法的基本思想是分阶段解决复杂问题，每个阶段处理的问题都控制在人们容易理解和处理的范围内。采取以下方法确保程序的结构化：自上而下；逐渐提炼；模块化设计；结构化编码。两种