第2章 程序设计的灵魂——算法

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

2、出计算机从计算机解决问题的过程出发，设计出计算机能够执行的算法，并且实现该算法。能够执行的算法，并且实现该算法。具体问题分析问题设计算法编写程序调试程序得到答案32.1 算法与计算机算法o 算法算法：为解决一个问题而采取的方法和步骤，或者说：为解决一个问题而采取的方法和步骤，或者说是解题步骤的精确描述。是解题步骤的精确描述。“a set of rules that must be followed when solving a particular problem ”o “算法”即演算法的中文名称最早出自周髀算经。o 英文名称 Algorithm 来自于9世纪波斯数学家花拉子密（比阿勒霍瓦里松

3、）。“算法”原为“algorism”（阿拉伯数字的运算法则），18世纪演变为algorithm。42.1 算法与计算机算法o 对同一个问题，可有不同的解题方法和步骤对同一个问题，可有不同的解题方法和步骤o方法1：1+2，+3，+4，一直加到100 加99次o方法2：100+(1+99)+(2+98)+(49 +51)+50 = 100 + 49100 +50 加51次例： 求1001nn 好的算法：方法简单、运算步骤少、能迅速得出正确结果的算法。 对于算法的优劣评价可以用空间复杂度与时间复杂度来衡量。52.1 算法与计算机算法o计算机算法计算机算法：计算机能执行的算法。：计算机能执行的算法。n

4、是计算机处理信息的本质，因为计算机程序本质上是一是计算机处理信息的本质，因为计算机程序本质上是一个算法来告诉计算机个算法来告诉计算机确切的步骤确切的步骤（well-defined procedure）来来执行一个指定的任务。执行一个指定的任务。o计算机算法的特点计算机算法的特点n输入输入：一个算法必须有零个或以上输入量。：一个算法必须有零个或以上输入量。n输出输出：一个算法应有一个或以上输出量，输出量是算法计算的结果。：一个算法应有一个或以上输出量，输出量是算法计算的结果。 n明确性明确性：算法的描述必须无歧义，以保证算法的实际执行结果是精确：算法的描述必须无歧义，以保证算法的实际执行结果是精

5、确地符合要求或期望，并且要求实际执行结果是确定的。地符合要求或期望，并且要求实际执行结果是确定的。 n有限性有限性：（计算机只有有限个状态、有限个输入符号和有限个指令）：（计算机只有有限个状态、有限个输入符号和有限个指令）规定算法必须在有限个步骤内完成任务。规定算法必须在有限个步骤内完成任务。 n有效性有效性：又称可行性。算法中描述的操作都是可以通过已经实现的基：又称可行性。算法中描述的操作都是可以通过已经实现的基本运算执行有限次来实现。本运算执行有限次来实现。 62.1 算法与计算机算法o算盘有二五珠算盘 、一五珠算盘 、九珠算盘等o用算珠来表示数字。o有对应四则运算的珠算法则。o有操作指法

6、。o思考思考n输入？输入？n输出？输出？n明确性？明确性？n有限性？有限性？n有效性？有效性？72.2 图灵机模型o什么是“确切的步骤确切的步骤” 精确的定义？o20世纪的英国数学家图灵提出了著名的图灵论题，并提出一种假想的计算机的抽象模型，这个模型被称为图灵机。1912年6月23日1954年6月7日图灵机的艺术表示 （1936年提出）82.2 图灵机模型o 图灵的基本思想是用机器来模拟人们用纸笔进行数学运算的过程n在纸上写上或擦除某个符号； n把注意力从纸的一个位置移动到另一个位置； o 而在每个阶段，人要决定下一步的动作，依赖于 n(a) 此人当前所关注的纸上某个位置的符号。n(b) 此人

7、当前思维的状态。92.2 图灵机模型图灵机组成图灵机组成o构造出一台假想的机器，该机器由以构造出一台假想的机器，该机器由以下几个部分组成：下几个部分组成：n一条无限长的纸带一条无限长的纸带 TAPE。n一个读写头一个读写头 HEAD。n一套控制规则一套控制规则 TABLE。n一个状态寄存器。一个状态寄存器。n注意这个机器的每一部分都是有限注意这个机器的每一部分都是有限的，但它有一个潜在的无限长的纸的，但它有一个潜在的无限长的纸带，因此这种机器只是一个理想的带，因此这种机器只是一个理想的设备。图灵认为这样的一台机器就设备。图灵认为这样的一台机器就能模拟人类所能进行的任何计算过能模拟人类所能进行的

8、任何计算过程。程。102.2 图灵机模型图灵机工作原理图灵机工作原理o从读写头在纸带上读出一个方格从读写头在纸带上读出一个方格的信息的信息o并且根据它当前的内部状态开始并且根据它当前的内部状态开始对控制规则进行查寻。然后得出对控制规则进行查寻。然后得出一个输出动作，也就是是否往纸一个输出动作，也就是是否往纸带上写信息，还是移动读写头到带上写信息，还是移动读写头到下一个方格。程序也会告诉它下下一个方格。程序也会告诉它下一时刻内部状态转移到哪一个。一时刻内部状态转移到哪一个。o具体的控制规则就是一个列表，具体的控制规则就是一个列表，其实就是程序，样子如右侧表。其实就是程序，样子如右侧表。当前状当前

9、状态态s s输入数输入数值值i i输出输出动作动作o o下一时刻状态下一时刻状态s sB1前移CA0 往纸带上写1BC 0后移A112.2 图灵机模型o 图灵机只要根据每一时刻读写头读到的信息和当前的内部状图灵机只要根据每一时刻读写头读到的信息和当前的内部状态进行查表就可以确定它下一时刻的内部状态和输出动作。态进行查表就可以确定它下一时刻的内部状态和输出动作。o 图灵机就是这么简单！而只要你变化它的程序（也就是上面的规则表），那么它就可能为你做任何计算机能够完成的工作。可以说，图灵机就是一个最简单的计算机模型！122.3 程序设计的灵魂算法o一个程序应包括两个方面的内容n对数据的描述：数据结构

10、(data structure)n对操作的描述：算法(algorithm)o完整的程序设计程序设计应该是:著名计算机科学家沃思提出一个公式数据结构数据结构 + 算法算法 = 程序程序程序程序语言程序程序语言132.3 程序设计的灵魂算法例例2.1: 求求12345步骤1：先求12，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120n如果要求如果要求1 12 210001000，则要写，则要写999999个步骤个步骤n应该怎么办呢？应该怎么办呢？142.3 程序设计的灵魂算法可以设两个变量：可以设两个变量：一个变量代表被乘数，一

11、个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设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!的值。152.3 程序设计的灵魂算法如果题目改为：求1357911算法只需作很少的改动：S1： 1pS2： 3 iS3： pi pS4： i+2 pS5：若i11，返回S3。否则，结束。 用这种方法表示的算法具有通用性、灵活性。S3到S

12、5组成一个循环，在实现算法时 要反复多次执行S3，S4，S5等步骤，直到某一时刻，执行S5步骤时经过判断，乘数i已超过规定的数值而不返回S3步骤为止。此时算法结束，变量p的值就是所求结果。162.3 程序设计的灵魂算法例例2.2 判定判定20002500年中的每一年是否闰年中的每一年是否闰年，输出结果。年，输出结果。n 分析：闰年的条件是：o 能被4整除，但不能被100整除的年份都是闰年，如1996，2004年是闰年；o 能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。1. 不符合这两个条件的年份不是闰年。 172.3 程序设计的灵魂算法设设y y为被检测的年份，算

13、法可表示如下为被检测的年份，算法可表示如下 ：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继续执行，如y2500，算法停止。18o以上算法中每做一步都分别分离出一些范围(巳能判定为闰年或非闰年)，逐步缩小范围，直至执行S5时，只可能是非闰年。o“其它” 包括能被4整除，又能被100整除，而不能被400整除的那些年

14、份(如1990) 是非闰年。2.3 程序设计的灵魂算法192.3 程序设计的灵魂算法o 算法的三种基本结构算法的三种基本结构n Bohra和和Jacopini于于1966年提出了以下三种基本年提出了以下三种基本结构：结构：o 顺序执行结构顺序执行结构o 选择执行结构选择执行结构o 循环执行结构循环执行结构o由三种基本结构顺序组成的算法结构，可以解决任何复杂问题。由三种基本结构顺序组成的算法结构，可以解决任何复杂问题。o由基本结构所构成的算法属于由基本结构所构成的算法属于“结构化结构化”的算法，它不存在无规的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳律的转向，只在

15、本基本结构内才允许存在分支和向前或向后的跳转。转。202.4 计算机算法的表示2.4.1 用自然语言表示算法用自然语言表示算法o 自然语言就是人们日常使用的语言，可以是汉语或英自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现长，容易出现“歧义性歧义性”。自然语言表示的含义往往。自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题

16、外，一般不用自然语言描述算法。些很简单的问题外，一般不用自然语言描述算法。212.4 计算机算法的表示2.4.2 用流程图表示算法用流程图表示算法n美国国家标准化协会美国国家标准化协会ANSI(American National Standard Institute)1985年发布并规定了一些常用的流年发布并规定了一些常用的流程图符号。（国际标准化组织公布的标准程图符号。（国际标准化组织公布的标准ISO5807-85）n国家标准局批准的国家标准国家标准局批准的国家标准(GB1525-89)起止框起止框判断框判断框处理框处理框输入输入/输出框输出框注释框注释框流向线流向线连接点连接点222.4

17、计算机算法的表示o 三种基本结构的图示：顺序结构顺序结构选择结构选择结构232.4 计算机算法的表示o 循环结构的图示： 当型当型(While型型)循环结构循环结构 直到型直到型(Until型型)循环结构循环结构 242.4 计算机算法的表示o 三种基本结构的共同特点：三种基本结构的共同特点： n 只有一个入口。只有一个入口。 n 只有一个出口。（只有一个出口。（请注意：请注意：一个菱形判断框一个菱形判断框有两个出口，而一个选择结构只有一个出口。有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混不要将菱形框的出口和选择结构的出口混淆。）淆。）n 结构内的每一部分都有机

18、会被执行到。结构内的每一部分都有机会被执行到。n 结构内不存在结构内不存在“死循环死循环”( (无终止的循环无终止的循环) )。252.4 计算机算法的表示o流程图是表示算法的较好的工具。包括以下几部分 ：n表示相应操作的框；n带箭头的流程线；n框内外必要的文字说明。1.将例将例2.1求求5!的算法用流程图表示。的算法用流程图表示。262.4 计算机算法的表示o将例将例2.2判定闰年的算法用流判定闰年的算法用流程图表示程图表示用流程图表示算法要比用文字描述算法逻辑清晰、易于理解。 272.4 计算机算法的表示2.4.2 用用N-S流程图表示算法流程图表示算法1.1.传统流程图的弊端传统流程图的

19、弊端o流程线的使用没有严格限制o占用太多地方2 . 19732 . 1973年，年， I.NassiI.Nassi和和B.ShneidermanB.Shneiderman进行改进。进行改进。o完全去掉了带箭头的流程线。o全部算法写在一个矩形框内，在该框内还可以包含其它的从属于它的框，或者说，由一些基本的框组成一个大的框。o这种流程图又称N-S结构化流程图。28 N-S流程图用以下的流程图符号： (1)顺序结构(2)选择结构(3)循环结构2.4 计算机算法的表示29将例将例2.1的求的求5!算法用算法用N-S图表示图表示2.4 计算机算法的表示30 将例将例2.3判定闰判定闰年的算法用年的算法用

20、N-S图表示图表示31 2.4.3 用伪代码表示算法用伪代码表示算法o 概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。o 特点：它如同一篇文章一样 ，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便 、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。o 用处：适用于设计过程中需要反复修改时的流程描述。2.4 计算机算法的表示32 IF x is positive THEN print x ELSE print -x也可以用汉字伪代码表示：也可以用汉字伪代码表示： 若若 x为正为正 打印打印 x 否则否则 打印打印 -x也可以中英

21、文混用，如：也可以中英文混用，如： IF x 为正为正 print x ELSE print -x例： “打印x的绝对值”的算法可以用伪代码表示为：2.4 计算机算法的表示33开始开始 置置t的初值为的初值为1 置置i的初值为的初值为2 当当i=5，执行下面操作：，执行下面操作： 使使t=ti 使使i=i+1 循环体到此结束循环体到此结束 输出输出t的值的值 结束结束也可以写成以下形式：也可以写成以下形式： BEGIN算法开始算法开始 1t 2 i while i5 ti t i+1 i print t END算法结束算法结束例求例求5!。用伪代码表示算法：。用伪代码表示算法：2.4 计算机算

22、法的表示342.4 计算机算法的表示2.4.4 用计算机语言表示算法用计算机语言表示算法n概念：概念：用计算机实现算法。用计算机实现算法。计算机是无法识别流程图的。计算机是无法识别流程图的。只有只有用计算机语言编写的程序才能被计算机执行。因此在用流程图用计算机语言编写的程序才能被计算机执行。因此在用流程图描述出一个算法后，还要将它转换成计算机语言程序。描述出一个算法后，还要将它转换成计算机语言程序。 o程序设计语言n特点：特点：用计算机语言表示算法必须严格遵循所用的语言的语法用计算机语言表示算法必须严格遵循所用的语言的语法规则。规则。提供了一种表达数据与处理数据的功能提供了一种表达数据与处理数

23、据的功能程序的执行过程实际上是对程序所表达的数据进行处理的程序的执行过程实际上是对程序所表达的数据进行处理的过程。过程。359种控制语句：if( )elsefor( )while( )dowhile( )continuebreakswitchgotoreturn数据类型基本类型构造类型指针类型空类型void自定义类型typedef数值类型字符类型char枚举类型enum整 型浮点型单精度型float双精度型double短整型short长整型long整型int数组结构体struct共用体union34种运算符：算术运算符：+ - * / % + -关系运算符： = !=逻辑运算符：！ & |位运

24、算符 ： | &赋值运算符：= 及其扩展条件运算符：?:逗号运算符：,指针运算符：* &求字节数 ：sizeof强制类型转换：(类型）分量运算符：. -下标运算符：其它 ：( ) -32个关键字：(auto break case char constcontinue default do double elseenum extern float for gotoif int long register returnshort signed sizeof static structswitch typedef unsigned union voidvolatile while2.4 计算机算法的

25、表示362.4 计算机算法的表示例例 将例将例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程序，仍然只是程序，仍然只是描述了算法，并未实现算法。只有运行程描述了算法，并未实现算法。只有运行程序才是实现算法。应该说，用计算机语言序才是实现算法。应该说，用计算机语言表示的算法是计算机能够执行的算法。表示的算法是计算机能够执行的算法。37 2.

26、5 结构化程序设计方法o 一个结构化程序一个结构化程序 就是用高级语言表示的结构化算法。用就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和维护。序便于编写、便于阅读、便于修改和维护。o 结构化程序设计强调程序设计风格和程序结构的规范化，结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。提倡清晰的结构。o 结构化程序设计方法的基本思路是：把一个复杂问题的结构化程序设计方法的基本思路是：把一个复杂问题的求解过程求解过程 分阶段进行，每个阶段处理的问题都控制在人分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。们容易理解和处理的范围内。 38采取以下方法来保证得到结构化的程序：采取以下方法来保证得到结构化的程序：o自顶向下；自顶向下；o逐步细化；逐步细化；o模块化设计；模块化设计；o结构化编码。结构化编码。两种