第二章程序的灵魂——算法.ppt

1、第二章是程序的灵魂算法，以及程序设计概述。程序应该包括数据描述和数据处理描述。1数据描述，即数据结构。数据结构是计算机科学的核心课程之一，关于它有很多专门的工作，所以我们在本课程中不再重复。在C语言中，系统提供的数据结构以数据类型的形式出现。2数据处理的描述，即计算机算法。算法是解决问题的方法和步骤，是程序的灵魂。为此，著名的计算机科学家尼克劳斯沃思提出了一个公式：数据结构算法=程序。事实上，除了数据结构和算法，程序还必须使用计算机语言，并采用结构化的方法来表达它。算法：指的是解决特定问题的一组定义明确的步骤。简而言之，算法是指对解决方案的准确而完整的描述。从程序的角度来看，也可以说一个算法是

2、一组有限的指令，它决定了解决一个特定类型问题的操作顺序。解决同一个问题有不同的方法和步骤，即不同的算法。算法有优点也有缺点。一般来说，我们应该选择运算步骤少、运算速度快、内存开销低(算法的时间和空间效率)的简单算法。2.1算法概念，购买电视机的步骤：选货，开发票，付款，拿发票，提货，回家，考大学，填清单，交注册费，拿准考证，考试，拿到录取通知书，报到，2.2，简单算法示例，示例1这个算法可以先写：(1)先找到12个，得到结果2；(2)将步骤1得到的结果乘以3，得到结果6；(3)将6乘以4得到24；(4)将24乘以5，得到120。12345，上面的算法太麻烦了，我们找到一个通用的表示方法。S1:

3、让变量p，被乘数，p=1；让变量I代表乘数，I=2；S3:将pi的乘积放入被乘数变量p，它可以表示为：p i pS4:将I的值加1，即I 1i；S5:如果I不大于5，则返回并重新执行步骤s3以及随后的步骤s4和S5；否则，算法结束。最后一个p是5！的价值。2.如果标题更改为13579 11，请拨打13579 11。上述算法稍作修改：s 1: 1 p；s 23360 3 I；s3: p i p如果i11，返回S3；否则，结束。13579 11.由此可见，该方法所表达的算法具有通用性和灵活性。S3到s5构成一个环路。当实现该算法时，步骤s3、s4、s5等。应当重复执行，直到某个时刻，当执行步骤s5

4、时，判断乘数I已经超过指定值，因此不返回步骤S3。用计算机实现这个循环很容易。13579 11，请仔细分析循环结束的条件，即步骤s5。如果您正在寻找13579 11，将步骤s5写成：S5；如果I11，返回s3。这有什么问题？结果会是什么？有50个学生想打印出那些分数超过80分的。解答：n是学生证，n1是第一学生证，ni是第一学生证。g代表学生的分数，gi代表第I个学生的分数，算法表示如下：S2:如果gi80，打印ni和gi，否则不打印。S3: i 1 i如果i50，则返回s2并继续执行；否则，算法结束。在这个例子中，变量I被用作下标来控制序列号(哪个学生，哪个年级)。当我超过50时，意味着50

5、名学生的分数已经被处理，算法结束。在示例4中，判断2000-2500年的每一年是否为闰年，并输出结果。解决办法：闰年的条件如下：(1)一年可以被4整除，但不能被100整除，就是闰年；例如，在1996年和2004年(2)，可以用100和400等分的年份是闰年。比如1600，2000。不符合这两个条件的一年不是闰年。算法如下：以y为检测年份，并采取以下步骤：s 13360 2000y；S2:如果y不能被4整除，则y输出为“不是闰年”。然后转到s6。S3:如果y可被100整除，并且可被400整除，则输出y作为“闰年”；否则，输出y为“不是闰年”。然后转到s6。S4:如果y可被100整除并且可被400

6、整除，输出y作为“闰年”，然后转到s6。S5:输出y“不是闰年”。s 6:y 1y；当y2500时，转到s2继续执行，例如y2500，算法停止。(1)使S=0(S作为累积变量)；(2)让N=1(N代表分母)；(3)S 1/N S(执行迭代，S是迭代变量)；(4)北纬1度；(5)如果N100，转至(3)和后续步骤；否则，执行(6)；(6)打印s的值(即需求的总和)。要找到以下系列的值，您可以编写以下算法：1。有限性：一个算法应该包含有限的步骤，而不是无限的步骤；同时，一个算法应该在执行一定数量的步骤后完成，它不能是无止境的。事实上，“贫穷”通常指的是“在合理范围内”的有限步骤。如果一台计算机被允

7、许执行一个需要1000年才能完成的算法，这个算法虽然很差，但是超过了合理的限制，人们认为这个算法没有用。2.确定性：算法中的每一步都应该是确定的，而不是模糊不清的。也就是说，不应该有歧义。特别是，当用自然语言描述算法时，我们应该注意这一点。例如，“打印出成绩优异的学生名单”就有歧义。“优秀成绩”是要求每门课程90分以上，还是平均成绩超过90分？不清楚，不明确，不适合描述算法步骤。2.3。算法的特点，3 .有0个或更多输入(即，可能没有输入或可能有输入)。所谓的输入是指当算法被执行时从外部世界获得必要的信息。(外部世界与算法本身有关，输入可以是手动键盘输入的数据，也可以是程序其他部分传输给算法的

8、数据。)例如，您可以计算5！(0个输入)例如，如果你想计算两个整数的最大公约数，你需要输入两个整数m，n(2个输入)4。有一个或多个输出(即算法必须得到结果)。算法的输出：算法获得的结果。算法必须有结果，没有结果的算法是没有意义的。(结果可以显示在屏幕上，或者结果数据可以传输到程序的其他部分。)5 .有效性算法的每一步都应得到有效的执行，并能得到明确的结果。例如，如果b=0，执行a/b不能有效执行。2.4 .如何表示算法？要表示一个算法，可以使用不同的方法。常用的算法表示方法：自然语言、传统流程图、结构化流程图、伪代码、计算机语言等。(重点：传统流程图，N-S流程图)，2.4.1该算法用人们常

9、用的自然语言表达，可以是中文、英文或其他语言。用自然语言很容易理解；然而，文本冗长，容易产生“歧义”；此外，用自然语言描述包含分支和循环的算法也不方便。通常不使用自然语言来描述算法，例如描述计算和输出z=y/x的过程，可以用自然语言描述如下：(1)输入X，y。(2)判断X是否为0:如果X=0，输出错误信息；否则计算y/x z和输出Z.例如，自然语言描述，算法描述语言：它是一种专门用来解释程序流程的语言。它通常介于自然语言和编程语言之间。它在自然语言中是灵活的，接近于编程语言的描述。注意：一般来说，算法描述语言描述的过程不能直接作为程序使用，最后需要转换成某种编程语言描述的程序。与编程语言的区别

10、：前者是免费的，不像后者，后者受语法的限制，只要它是以人们可以理解的方式描述的，而不考虑计算机处理应该遵循的规则或其他细节。算法描述语言，在编程过程中，一般不可能一开始就用某一种编程语言来编译一个计算机程序，而是要用一种简单、直观、灵活的描述工具来描述处理问题的过程。方案确定后，这个过程被转换成计算机程序。这种转换通常是机械的，不涉及功能的重新设计或控制过程的改变，而只需要考虑语法要求和编程语言指定的详细问题。1.过程描述；2.4.2算法用流程图表示；流程图：一些约定的几何图形被用来描述算法。用特定的框架表示操作，用箭头表示算法流程，以及流程图(符号和含义)。美国标准化协会的ANSI规定了一些

11、常用的流程图符号，这些符号已被世界各地的程序员广泛采用：起止框、输入输出框、判断选择框、处理框、流程线、连接点、注释框、l起止框：表示算法的开始和结束。通常，内部只写“开始”或“结束”。l处理框：表示算法的一个处理步骤，赋值操作通常在里面填写。l输入/输出框：表示算法请求输入所需的数据或算法输出一些结果。一般来说，“输入”和“打印/显示”L菱形框(判断框)是内部填写的，主要用于判断给定的条件，并根据给定的条件是否为真来决定如何进行后续操作。它有一个入口和两个出口。l连接点：用于连接不同位置绘制的流线。相同数字的点是相互联系的。事实上，相同数字的点是相同的点，但它们不能分开画。连接点的使用还可以

12、避免流线的交叉或过长，使流程图更加清晰。评论框：评论框不是流程图的重要部分，也不能反映流程和操作。它只是对流程图中一些方框的操作做了必要的补充说明，以帮助读者更好地理解流程图的功能。例子：要求5英镑！t=1，i=2，t=t*i，i=i 1，i5，end，N，Y，start，传统的流程图使用流程线来指示每个块的执行顺序，并且对流程线的使用没有严格的限制。因此，用户可以不受限制地改变流程，使流程图不规则。人们改进这个流程图，规定几个基本结构，然后由这些基本结构按照一定的规则形成算法结构。整个算法结构按照从上到下的顺序排列基本结构。这可以在一定程度上提高算法的质量。三种基本结构如下：(1)顺序结构按

13、照指令的顺序执行；(2)判断选择结构：根据判断条件有选择地改变执行流程；(3)循环结构：有条件地重复执行某个程序块；(2.4.3)三个基本结构和改进的流程图；(1)顺序结构编程，依次执行程序语句、块A、块B和块A。a=5；b=10(2)判别和选择结构化程序，首先判断条件，如果条件满足，程序执行方框A，否则执行方框B；例如，找出a和b的最大值；满足条件否、满足、不满足、执行块A、执行块B、条件成立吗？执行块A、执行块B、是、否、B最大值？Max=a；max=b；(3)循环结构的编程。该循环分为“当型循环”和“直到型循环”，并计算1100的累积和。int i，sum=0；而(I=100)sum=s

14、um I；I=I 1；在循环中执行指令，直到满足条件。当条件满足时，在循环中执行指令。i=100？sum=sum I；I=I 1；Y，和=0；三个基本结构有以下共同之处：l只有一个入口：不允许从结构外部随意转移到结构中的某一点。只有一个出口：不允许从建筑的某个位置随意转身(跳出来)。l结构的每个部分都有被执行的机会。(没有“死语句”)在L结构中没有“死循环”(循环)。已经证明，由三个基本结构序列组成的算法结构可以解决任何复杂的问题。由基本结构组成的算法属于“结构化”算法。2.4.4算法用N-S流程图表示，基本结构的顺序组合可以表示任何复杂的算法结构，因此基本结构之间的流程线是多余的，因此美国学

15、者I . Nasii和B.shneiderman在1973年提出了一种新的流程图形式。所有算法都写在一个矩形框中，带有箭头的流线被完全去除。这个流程图被称为南北结构流程图(箱线图)。N-S流程图适用于结构化编程、序列结构编程、执行块A、执行块B、顺序执行程序语句、先执行操作A、后执行操作B、判断和选择结构化编程、条件是否满足、满足、不满足、执行块A、执行块B、条件为真时执行操作A、条件不为真时执行操作B。a、b操作允许空操作，即不做任何事情。注意选择结构作为一个整体，代表一个基本结构。循环结构编程，循环分为“当-型循环”和“直到-型循环”，当条件p满足时，执行循环中的指令直到条件p满足，例如：

16、ask for 5！该算法由N-S图表示、1 t、2 I、t * I t、I I、直到i5、打印t，当类型循环：当条件p成立时，重复执行循环中的指令，直到条件p不成立。当类型循环在决定是否执行循环体之前进行判断时，如果条件p不满足一次，则循环体可能不会执行一次，当条件p满足时，执行循环中的指令，直到类型循环：当条件p不为真时，重复执行循环体中的指令，直到条件p成立。直到类型循环首先执行循环体，然后判断条件p，所以循环体至少执行一次。直到满足条件p，执行循环中的指令，2.4.5使用伪代码来表示算法，这通常用于算法设计。该算法采用传统的流程图和N-S图表示，直观易懂，但绘制起来比较麻烦。设计算法时，可能需要反复修改，但修改流程图很麻烦。因此，流程图适于表示算法，但是为了方便设计算法，通常使用伪代码工具。伪代码用自然语言和计算机语言之间的单词和符号来描述算法。伪码不使用图形符号，书写方便，格式紧凑，便于向计算机语言算法过渡。用某种编程语言编写的程序本质上是对问题解决方案的描述和最终描述。在一般的编程过程中，不建议一开始就编写程序，尤其是对于大规模的程序。程序是程序设计的最终产品，它需要每一步的精心