第二章 程序设计的灵魂__算法

1、第二章第二章 程序设计的灵魂程序设计的灵魂算法算法清华大学 自动化系刘连臣2021年7月6日计算机语言与程序设计基础计算机语言与程序设计基础 1主要内容o目标：目标：以计算机能执行的算法特征算法特征为线索，了解计算机程序计算机程序=数据结构数据结构+算法算法，掌握结构化程序设结构化程序设计基本理念计基本理念，为程序设计语言的学习奠定基础。o提纲2.1 2.1 算法与计算机算法算法与计算机算法2.2 2.2 程序设计的灵魂程序设计的灵魂算法算法2.3 2.3 计算机算法的表示计算机算法的表示2.4 2.4 算法结构化分析算法结构化分析22.1 算法与计算机算法o 程序设计的目的是什么？程序设计的

2、目的是什么？o 从计算机解决问题的过程出发，设计出计算机从计算机解决问题的过程出发，设计出计算机能够执行的算法，并且实现该算法。能够执行的算法，并且实现该算法。具体问题具体问题分析问题分析问题设计算法设计算法编写程序编写程序调试程序调试程序得到答案得到答案2.1 算法与计算机算法o 请举出下面比较形象或好理解的例子1、有解但无算法2、无解也无算法3、可计算与不可计算4、可证明与不可证明 32.1 算法与计算机算法o 1。有解但无算法的问题：比如，圆周率Pi的小数点后面是否有连续的100万个0 ?4因为Pi是一个客观存在的实数，所以Pi的值是确定的，因此这个问题的解也是存在的。要么是yes,要么

3、是no，虽然我们不知道他到底是什么，但他是客观存在的，不随时间改变，不随人的认识而改变。但是没有算法可以计算这个问题的答案。当然，可以用一种笨办法来解决这个问题，就是不停地计算Pi的小数点后面的值，如果发现了有连续的100万个0，则这个问题的答案就是yes，但是如果没有发现，我们必须一直计算下去，而且永远无法停止，所以这种笨办法根本称不上是算法，因为它不满足算法在有限步内终止的条件。所以这个问题是没有算法的。（至少目前认为如此，也许以后可以从数论中找到某种方法来求出小数点后面是否有连续的k个0，或从概率的角度计算Pi的小数点后面的值的分布等等等等）。2.1 算法与计算机算法5o 2.无解也无算

4、法的问题：例如，给定任意一个命题，是否存在一种算法判断这个命题是真是假？这就是著名的图灵停机问题。如果存在这个算法，那么我们只要找到这个算法就可以一劳永逸了，以后无论拿到什么新的命题，都可以用这个算法来验证一下，立刻就知道该命题是真是假，这样我们就掌握了整个宇宙的终极真理：）。但是图灵已经证明了这样的算法是不存在的，这个问题也是无解的。（证明中主要利用了康托尔对角线删除法，就是用来证明实数和自然数不等势的那种对角线删除法）62.1 算法与计算机算法o 算法算法：为解决一个问题而采取的方法和步骤，或者说：为解决一个问题而采取的方法和步骤，或者说是解题步骤的精确描述。是解题步骤的精确描述。“a s

5、et of rules that must be followed when solving a particular problem ”o “算法”即演算法的中文名称最早出自周髀算经。o 英文名称 Algorithm 来自于9世纪波斯数学家花拉子密（比阿勒霍瓦里松）。“算法”原为“algorism”（阿拉伯数字的运算法则），18世纪演变为algorithm。72.1 算法与计算机算法o 对同一个问题，可有不同的解题方法和步骤对同一个问题，可有不同的解题方法和步骤o方法1：1+2，+3，+4，一直加到100 加99次o方法2：100+(1+99)+(2+98)+(49 +51)+50 = 10

6、0 + 49100 +50 加51次例： 求1001nn 好的算法：方法简单、运算步骤少、能迅速得出正确结果的算法。 对于算法的优劣评价可以用空间复杂度与时间复杂度来衡量。82.1 算法与计算机算法o计算机算法计算机算法：计算机能执行的算法。：计算机能执行的算法。n是计算机处理信息的本质，因为计算机程序本质上是一是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机个算法来告诉计算机确切的步骤确切的步骤（well-defined procedure）来来执行一个指定的任务。执行一个指定的任务。o计算机算法的特点计算机算法的特点n输入输入：一个算法必须有：一个算法必须有零个零个或以上

7、输入量。或以上输入量。n输出输出：一个算法应有：一个算法应有一个一个或以上输出量，输出量是算法计算的结果。或以上输出量，输出量是算法计算的结果。 n明确性明确性：(确定性确定性) 算法的描述必须无歧义，以保证算法的实际执行算法的描述必须无歧义，以保证算法的实际执行结果是精确地符合要求或期望，并且要求实际执行结果是确定的。结果是精确地符合要求或期望，并且要求实际执行结果是确定的。 n有限性有限性：(有穷性有穷性)（计算机只有有限个状态、有限个输入符号和有（计算机只有有限个状态、有限个输入符号和有限个指令）规定算法必须在有限个步骤内完成任务。限个指令）规定算法必须在有限个步骤内完成任务。 n有效性

8、有效性：又称可行性。算法中描述的操作都是可以通过已经实现的基：又称可行性。算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。本运算执行有限次来实现。 92.1 算法与计算机算法o算盘有二五珠算盘 、一五珠算盘 、九珠算盘等o用算珠来表示数字。o有对应四则运算的珠算法则。o有操作指法。o思考思考n输入？输入？n输出？输出？n明确性？明确性？n有限性？有限性？n有效性？有效性？2.1 算法与计算机算法o 思考：找到计算机适合的算法n 找出1到1000之间，所有满足方程 x2+y3=z4的所有正整数解。n 找出1到1000之间，所有满足方程组 2010=10 x+20y+401z ；x

9、+y=z 的正整数解。n 找出方程f(x)=x3-5x2+16x-80=0的根。10112.2 程序设计的灵魂算法o一个程序应包括两个方面的内容一个程序应包括两个方面的内容n对数据的描述：数据结构(data structure)n对操作的描述：算法(algorithm)o完整的程序设计程序设计应该是:著名计算机科学家沃思提出一个公式数据结构数据结构 + 算法算法 = 程序程序程序程序语言程序程序语言Niklaus Wirth122.2 程序设计的灵魂算法例例2.1: 求求12345步骤1：先求12，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将

10、24再乘以5，得120n如果要求如果要求1 12 210001000，则要写，则要写999999个步骤个步骤n应该怎么办呢？应该怎么办呢？132.2 程序设计的灵魂算法可以设两个变量：可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果, 算法可改写：S1：使p=1。S2：使i=2。S3：使pi，乘积仍放在变量p中，可表示为：pi p S4：使i的值加1，即i+1 i。S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。142.

11、2 程序设计的灵魂算法如果题目改为：求1357911算法只需作很少的改动：S1： 1pS2： 3 iS3： pi pS4： i+2 iS5：若i11，返回S3。否则，结束。 用这种方法表示的算法具有通用性、灵活性。S3到S5组成一个循环，在实现算法时 要反复多次执行S3，S4，S5等步骤，直到某一时刻，执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算法结束，变量p的值就是所求结果。152.2 程序设计的灵魂算法例例2.2 判定判定20002500年中的每一年是否闰年中的每一年是否闰年，输出结果。年，输出结果。n 分析：闰年的条件是：o 能被4整除，但不能被100整除的

12、年份都是闰年，如1996，2004年是闰年；o 能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。1. 不符合这两个条件的年份不是闰年。 162.2 程序设计的灵魂算法设设y y为被检测的年份，算法可表示如下为被检测的年份，算法可表示如下 ：S1：2000 yS2：若y不能被4整除，则输出y “不是闰年”。然后转到S6。S3：若y能被4整除，不能被100整除，则输出y “是闰年”。然后转到S6。S4：若y能被100整除，又能被400整除，输出y“是闰年”，否则输出“不是闰年”。 然后转到S6。S5: 输出y “不是闰年”。S6：y+1 yS7：当y2500时，转S2继

13、续执行，如y2500，算法停止。17o以上算法中每做一步都分别分离出一些范围(巳能判定为闰年或非闰年)，逐步缩小范围，直至执行S5时，只可能是非闰年。o“其它” 包括能被4整除，又能被100整除，而不能被400整除的那些年份(如1900) 是非闰年。2.2 程序设计的灵魂算法182.2 程序设计的灵魂算法o 算法的三种基本结构算法的三种基本结构n Bohra和和Jacopini于于1966年提出了以下三种基本年提出了以下三种基本结构：结构：o 顺序执行结构顺序执行结构o 选择执行结构选择执行结构o 循环执行结构循环执行结构o由三种基本结构顺序组成的算法结构，可以解决任何复杂问题。由三种基本结构

14、顺序组成的算法结构，可以解决任何复杂问题。o由基本结构所构成的算法属于由基本结构所构成的算法属于“结构化结构化”的算法，它不存在无规的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。转。Corrado Bhm192.3 计算机算法的表示2.3.1 用自然语言表示算法用自然语言表示算法o 自然语言就是人们日常使用的语言，可以是汉语或英自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现长，容易出现“歧义性歧义性”。

15、自然语言表示的含义往往。自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，一般不用自然语言描述算法。些很简单的问题外，一般不用自然语言描述算法。202.3 计算机算法的表示2.3.2 用流程图表示算法用流程图表示算法n美国国家标准化协会美国国家标准化协会ANSI(American National Standard Institute)1985年发布并规定了一些常用的流年发布并规定了一些常用的流程图符号。（国际标准化组织公

16、布的标准程图符号。（国际标准化组织公布的标准ISO5807-85）n国家标准局批准的国家标准国家标准局批准的国家标准(GB1525-89)起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点212.3 计算机算法的表示o 三种基本结构的图示：顺序结构顺序结构选择结构选择结构222.3 计算机算法的表示o 循环结构的图示： 当型当型(While型型)循环结构循环结构 直到型直到型(Until型型)循环结构循环结构 232.3 计算机算法的表示o 三种基本结构的共同特点：三种基本结构的共同特点： n 只有一个入口。只有一个入口。 n 只有一个出口。（只有一

17、个出口。（请注意：请注意：一个菱形判断框一个菱形判断框有两个出口，而一个选择结构只有一个出口。有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混不要将菱形框的出口和选择结构的出口混淆。）淆。）n 结构内的每一部分都有机会被执行到。结构内的每一部分都有机会被执行到。n 结构内不存在结构内不存在“死循环死循环”( (无终止的循环无终止的循环) )。242.3 计算机算法的表示o流程图是表示算法的较好的工具。包括以下几部分 ：n表示相应操作的框；n带箭头的流程线；n框内外必要的文字说明。1.将例将例2.1求求5!的算法用流程图表示。的算法用流程图表示。252.3 计算机算法

18、的表示o将例将例2.2判定闰年的算法用流判定闰年的算法用流程图表示程图表示用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。 262.3 计算机算法的表示2.3.3 用用N-S流程图表示算法流程图表示算法1.1.传统流程图的弊端传统流程图的弊端o流程线的使用没有严格限制o占用太多地方2 . 19732 . 1973年，年， I.NassiI.Nassi和和B.ShneidermanB.Shneiderman进行改进。进行改进。o完全去掉了带箭头的流程线。o全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大的框。o这种流程图又称N-S结构化流程图

19、。27 N-S流程图用以下的流程图符号： (1)顺序结构(2)选择结构(3)循环结构2.3 计算机算法的表示28将例将例2.1的求的求5!算法用算法用N-S图表示图表示2.3 计算机算法的表示29 将例将例2.3判定闰判定闰年的算法用年的算法用N-S图表示图表示30 2.3.4 用伪代码表示算法用伪代码表示算法o 概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。o 特点：它如同一篇文章一样 ，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便 、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。o 用处：适用于设计过程中需要反复修改时

20、的流程描述。2.3 计算机算法的表示31 IF x is positive THEN print x ELSE print -x也可以用汉字伪代码表示：也可以用汉字伪代码表示： 若若 x为正为正 打印打印 x 否则否则 打印打印 -x也可以中英文混用，如：也可以中英文混用，如： IF x 为正为正 print x ELSE print -x例： “打印x的绝对值”的算法可以用伪代码表示为：2.3 计算机算法的表示32开始开始 置置t的初值为的初值为1 置置i的初值为的初值为2 当当i=5，执行下面操作：，执行下面操作： 使使t=ti 使使i=i+1 循环体到此结束循环体到此结束 输出输出t的值

21、的值 结束结束也可以写成以下形式：也可以写成以下形式： BEGIN算法开始算法开始 1t 2 i while i5 ti t i+1 i print t END算法结束算法结束例求例求5!。用伪代码表示算法：。用伪代码表示算法：2.3 计算机算法的表示332.3 计算机算法的表示2.3.5 用计算机语言表示算法用计算机语言表示算法n概念：概念：用计算机实现算法。用计算机实现算法。计算机是无法识别流程图的。计算机是无法识别流程图的。只有只有用计算机语言编写的程序才能被计算机执行。因此在用流程图用计算机语言编写的程序才能被计算机执行。因此在用流程图描述出一个算法后，还要将它转换成计算机语言程序。描

22、述出一个算法后，还要将它转换成计算机语言程序。 o程序设计语言n特点：特点：用计算机语言表示算法必须严格遵循所用的语言的语法用计算机语言表示算法必须严格遵循所用的语言的语法规则。规则。提供了一种表达数据与处理数据的功能提供了一种表达数据与处理数据的功能程序的执行过程实际上是对程序所表达的数据进行处理的程序的执行过程实际上是对程序所表达的数据进行处理的过程。过程。349种控制语句：if( )elsefor( )while( )dowhile( )continuebreakswitchgotoreturn数据类型基本类型构造类型指针类型空类型void自定义类型typedef数值类型字符类型char

23、枚举类型enum整 型浮点型单精度型float双精度型double短整型short长整型long整型int数组结构体struct共用体union34种运算符：算术运算符：+ - * / % + -关系运算符： = !=逻辑运算符：！ & |位运算符 ： | &赋值运算符：= 及其扩展条件运算符：?:逗号运算符：,指针运算符：* &求字节数 ：sizeof强制类型转换：(类型）分量运算符：. -下标运算符：其它 ：( ) -32个关键字：(auto break case char constcontinue default do double elseenum extern float for

24、gotoif int long register returnshort signed sizeof static structswitch typedef unsigned union voidvolatile while2.3 计算机算法的表示352.3 计算机算法的表示例例 将例将例2.1表示的算法（求表示的算法（求5!） 用用C语言表示。语言表示。#include void main( ) int i,t; t=1; i=2; do t=t*i; i=i+1; while (i=5) printf(%dn,t); 变量定义循环结构输出语句应当强调说明：应当强调说明：写出了写出了C程序，

25、仍然只是程序，仍然只是描述了算法，并未实现算法。只有运行程描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。表示的算法是计算机能够执行的算法。36 2.4 结构化程序设计方法o 一个结构化程序一个结构化程序 就是用高级语言表示的结构化算法。用就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。序便于编写、便于阅读、便于修改和维护。o 结构化程序设计强调程序设计风格和程序结构的规范化，结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。提倡清晰的结构。o 结构化程序设计方法的基本思路是：把一个复杂问题的结构化程序设计方法的基本思路是：把一个复杂问题的求解过程求解过程 分阶段进行，每个阶段处理的问题都控制在人分阶段进行，每个阶段处理的问