计算机-第2章-算法概述

本章要点算法的概念算法的表示结构化程序设计方法常用算法简介主要内容2.1算法的概念2.2简单算法举例2.3算法的特性2.4算法的表示2.5结构化程序设计方法2.6常用算法简介一个程序应包括两个方面的内容:对数据的描述：数据结构(data

structure)对操作的描述：算法(algorithm)著名计算机科学家

提出一个公式:数据结构

+

算法

=

程序完整的程序设计应该是:数据结构＋算法＋程序设计方法＋语言工具§2.1

算法的概念广义地说，为解决一个问题而采取的方法和步骤，就称为“算法”。加99次方法2：100+(1+99)+(2+98)+…+(49+51)+50=100+49×100+50

加51次对同一个问题，可有不同的解题方法和步骤100例：求

nn

1方法1：1+2，+3，+4，一直加到100§2.1算法的概念为了有效地进行解题，不仅需要保证算法正确，还要考虑算法的质量，选择合适的算法。希望方法简单，运算步骤少。计算机算法可分为两大类别：数值运算算法：求数值解，例如求方程的根、求函数的定积分等。非数值运算：包括的面十分广泛，最常见的是用于事务管理领域，例如

检索、人事管理、行车调度管理等。§2.2

简单算法举例例2.1:

求1×2×3×4×5步骤1：先求1×2，得到结果2步骤2：将步骤1得到的乘积2再乘以3，得到结果6步骤3：将6再乘以4，得24步骤4：将24再乘以5，得120如果要求1×2×…×1000，则要写999个步骤可以设两个变量：一个变量代表被乘数，一个变量代表乘数。不另设变量存放乘积结果，而直接将每一步骤的乘积放在被乘数变量中。设p为被乘数，i为乘数。用循环算法来求结果,算法可改写：S1：使p=1S2：使i=2S3：使p×i，乘积仍放在变量p中，可表示为：p×i→pS4：使i的值加1，即i+1→i。S5：如果i不大于5，返回重新执行步骤S3以及其后的步骤S4和S5；否则，算法结束。最后得到p的值就是5!的值。S1：1→pS2：3

→

iS3：p×i

→

p

S4：i+2→

iS5：若i≤1000，返回S3。否则，结束。如果题目改为：求1×3×5×……×1000算法只需作很少的改动：上述算法采用了循环算法具有通用性、灵活性。例2.2

有50个学生，要求将他们之中成绩在80分以上者打印出来。设n表示学号，n1代表第一个学生学号，ni代表第i个学生学号。用G代表学生成绩，gi代表第i个学生成绩，算法表示如下:S1：1

→

iS2：如果gi≥80，则输出ni和gi，否则不输出。

S3:i+1→iS4：如果i≤50，返回S2，继续执行。否则算法结束*变量i作为下标，用来控制序号(第几个学生，第几个成绩)。当i超过50时，表示已对50个学生的成绩处理完毕，算法结束。例2.3

判定2000～2500年中的每一年是否闰年，将结果输出。分析：闰年的条件是：能被4整除，但不能被100整除的年份都是闰年，如

1996,2004年是闰年；能被100整除，又能被400整除的年份是闰年。如1600,2000年是闰年。不符合这两个条件的年份不是闰年。用变量y来放置被检测的年份，算法可表示如下S1：2000→yS2：若y不能被4整除，则输出y

“不是闰年”。然后转到S6。S3：若y能被4整除，不能被100整除，则输出y

“是闰年”。然后转到S6。S4：若y能被400整除，输出y“是闰年”，否则输出“不是闰年”。然后转到S6。S5:输出y

“不是闰年”。S6：y+1→yS7：当y≤2500时，转S2继续执行，如y＞2500，算法停止。以上算法中每做一步都分别分离出一些范围(巳能判定为闰年或非闰年)，逐步缩小范围，直至执行S5时，只可能是非闰年。“其它”包括能被4整除，又能被100整除，而不能被400整除的那些年份(如1990)是非闰年。例2.4

求算法如下

：99

1001

1

......1

1

12

3

41

束。S1：sign=1S2：sum=1S3：deno=2S4：sign=(-1)×signS5：term=sign×(1/deno)S6：sum=sum+termS7：deno=deno+1

S8：若deno≤100返回S4，否则算法结有意义的单词作变量名，以使算法更易于理解：sum表示累加和，deno是英文分母（denominator）缩写，

sign代表数值的符号，term代表某一项。反复执行S4到S8步骤，直到分母大于100为止。一共执行了99次循环，向sum累加入了99个分数。sum最后的值就是多项式的值。例2.5

对一个大于或等于3的正整数，判断它是不是一个素数。概念：所谓素数，是指除了1和该数本身之外，不能被其它任何整数整除的数。例如，13是素数。因为它不能被2，3，4，…，12整除。分析：判断一个数n(n≥3)是否素数的方法：将n作为被除数，将2到(n-1)各个整数轮流作为除数，如果都不能被整除，则n为素数。算法如下：S1：输入n的值

S2：i=2

（i作为除数）S3：n被i除，得余数rS4：如果r=0，表示n能被i整除，则打印n“不是素数”，算法结束。否则执行S5S5：i+1→iS6：如果i≤n-1，返回S3。否则打印n

“是素数”。然后结束。实际上，n不必被2到(n-1)的整数除，只需被2到n/2间整数除，甚至只需被2到SQRT(n)

之间的整数除即可。§2.3

算法的特性一个算法应该具有以下特点：正确性算法首先应该是正确的。即对于任意的一组输入(包括合理的输入与不合理的输入)，总能得到预期的输出。可行性算法的每一步都能够被计算机理解和执行，而不是抽象和模糊的概念。(大概,近似,比较小等)确定性算法每个步骤都有确定的执行顺序，每一步是什么，都必须明确，无二义性。有限性无论算法有多么复杂，都必须在有限步之后结束。算法的评价通常解决问题的途径并不是唯一的，计算机解决一个问题的算法同样不是唯一的，恰恰相反，很多步骤和思路完全不同的算法可以解决相同的问题。评判一个算法的优劣可从算法执行时间（常用语句执行次数与问题规模n的函数关系度量）和需占用的额外空间两方面考虑。称为时间复杂度和空间复杂度。(有关算法性能分析将在第七章中具体

。)19§2.4

算法的表示可以用不同的方法表示算法，常用的有：自然语言流伪代码§2.4.1

用自然语言表示算法自然语言就是人们日常使用的语言，可以是汉语或英语或其它语言。用自然语言表示通俗易懂，但文字冗长，容易出现“歧义性”。自然语言表示的含义往往不大严格，要根据上下文才能判断其正确含义，描述包含分支和循环的算法时也不很方便。因此，除了那些很简单的问题外，一般不用自然语言描述算法。§2.4.2

用流

表示算法流 是用一些图框来表示

。化 ANSI(American

National

StandardInstitute)规定了一些常用的流

符号：起止框判断框处理框输入/输出框注释框流向线连接点使用电脑

绘制流可以直接用笔和纸绘制流

;也可以在电脑中使用文本编辑工具（如WORD）或绘图 绘制流

;目前已经有多款专门适用于画流

的

，如

OfficeVisio、OmniGraffle（运行在Mac

OS

X和iPad平台之上）和ProcessOn等。ProcessOn是一个面向流程用户的专业社交网站，ProcessOn

为：http:/ /#。23*使用ProcessOn绘制流的方法登录后，点击右上角的“新建文件”在弹出框中选择流

分类及相关模板，缺省为“未分类”、“空模板”。点击"确定"后，弹出画布，现在就可以作图了。在左边的图形符号集

中选择一个合适的符号，拖到画布

。这样流

的第一个图形就画好了。形状，按住鼠将鼠标移动到第一个图形的边缘，此时鼠标会变为标拖动，就拉出了一根带箭头的连接线。将鼠标松开，会自动弹出与刚才所画图形同一类型的图形列表，从中选择一个图形，则第二个图形就画好了，而且与第一个图形建立了连接。如果第二个图形与第一个图形不是同一类型，只须在弹出图形列表时鼠标点击画布其它任意位置，然后到

拖拽所需类型的图形到画布上。24双击图框（或右击图框，从快捷菜单中选“编辑文本”），在图框中输入文字，并可通过菜单下面的

设置字体、字号等文本格式。重复以上操作完成流

。选中某图框，当光标移到其角点处变为双向箭头时，可拖拽改变图框大小。当光标变为带四个方向箭头的形状时可拖拽移动图框位置。如果从上一个图形拉出的连接线没有与下一个图形相连，可选中连接线并将鼠标移动到其头部，当鼠标变为带四个方向箭头的形状时，按住鼠标拖拽到所需相连的图框，即可完成连接。根据需要，还可以对流

图形及连接线进行填充颜色、边框颜色、连接线类型等的设置。流

全部完成后，通过“文件”菜单中的“重命名文件”指定文件名保存；通过“文件”菜单中的“ 为…”，可

到本地计算机中，保存为PNG图形或PDF文件。*使用ProcessOn绘制流

的方法25例2.6

将求5!的算法用流表示如果需要将最后结果打印出来，可在菱形框的下面加一个输出框。例2.7

将例2.2的算法用流表示。打印50名学生中成绩在80分以上者的学号和成绩。如果包括输入数据的部分，流为例2.8

将例2.3判定闰年的算法用流表示用流表示算法要比用文字描述算法逻辑清晰、易于理解。例2.9

将例2.4的算法用流表示1

1

1

1

......

1

12

3

4

99

100例2.10

将例2.5判断素数的算法用流表示小结：流

是表示算法的较好的工具。一个流程图包括以下几部分

：(1)表示相应操作的框；

(2)带箭头的流程线；(3)框内外必要的文字说明。§2.4.3

三种基本结构Bohra和Jacopini提出了以下三种基本结构：顺序结构、选择结构、循环结构用这三种基本结构作为表示一个良好算法的基本单元。三种基本结构的图示：顺序结构选择结构循环结构的图示：当型(While型)循环结构直到型(Until型)循环三种基本结构的共同特点：只有一个

；只有一个出口；（请注意：一个菱形判断框有两个出口，而一个选择结构只有一个出口。不要将菱形框的出口和选择结构的出口混结构内的每一部分都有机会被执行到；结构内不存在“死循环”(无终止的循环)。图中没有一条从

到出口的路径通过A框。不正确的流程表示：流程内的死循环小结：由三种基本结构顺序组成的算法结构，可以解决任何复杂的问题。由基本结构所构成的算法属于“结构化”的算法，它不存在无规律的转向，只在本基本结构内才允许存在分支和向前或向后的跳转。扩展：只要具有上述四个特点的都可以作为基本结构。可以自己定义基本结构，并由这些基本结构组成结构化程序。此图符合基本结构的特点这是一个多分支选择结构，根据表达式的值决定执行路线。虚线框内的结构是一个一个出口，并且有上述全部的四个特点。由此构成的算法结构也是结构化的算法。可以认为这是由三种基本结构所派生出来的。例2.15

将例2.5判别素数的算法用N--S流 表示。传统流

分析：出口1出口2此图不符合基本结构特点！由于不能分解为三种基本结构，就无法直接用N--S流的三种基本结构的符号来表示。因此，应当先作必要的变换。例2.15

将例2.5判别素数的算法用N--S流 表示。传统流变换为：一个出口小结：结构化的算法是由一些基本结构顺序组成的。如果算法不能分解为若干个基本结构，则它必然不是一个结构化的算法。在基本结构之间不存在向前或向后的跳转，流程的转移只存在于一个基本结构范围之内(如循环中流程的跳转)一个非结构化的算法可以用一个等价的结构化算法代替，其功能不变。§2.4.5

用伪代码表示算法概念：伪代码是用介于自然语言和计算机语言之间的文字和符号来描述算法。特点：它如同一篇文章一样，自上而下地写下来。每一行(或几行)表示一个基本操作。它不用图形符号，因此书写方便、格式紧凑，也比较好懂，也便于向计算机语言算法(即程序)过渡。用处：适用于设计过程中需要反复修改时的流程描述。IF

x

is

positive

THENprint

xELSEprint

-x也可以用汉字伪代码表示：若x为正打印x打印-x也可以中英文混用，如：IF

xprint

xELSEprint

-x例：“打印x的绝对值”的算法可以用伪代码表示为：开始置t的初值为1置i的初值为2当i<=5，执行下面操作：使t=t×i使i=i+1输出t结束也可以写成以下形式：BEGIN1t2

iwhile

i≤5{t×i

ti+1

i

}print

tEND｛算法结束｝例2.16

求5!。用伪代码表示算法：例2.17

输出50个学生中成绩高于80分者的学号和成绩。用伪代码表示算法：BEGIN｛算法开始｝1

iwhile

i≤50{input

ni

and

gii+1

i}1

iwhile

i≤50{if

≥80

print ni

and

gii+1

I}END｛算法结束｝§2.4.6

用计算机语言表示算法概念：用计算机实现算法。计算机是无法识别流 和伪代码的。只有用计算机语言编写的程序才能被计算机执行。因此在用流 或伪代码描述出一个算法后，还要将它转换成计算机语言程序。特点：用计算机语言表示算法必须严格遵循所用的语言的语 则，这是和伪代码不同的。用处：要完成一件工作，包括设计算法 算法两个部分。设计算法的目的是为了实现算法。t,i

=

1,2while

i

<=

5:t=t*ii=i+1print(t)例2.20

将例2.16表示的算法（求5!）用Python语言表示。§

2.5

结构化程序设计方法一个结构化程序

就是用高级语言表示的结构化算法。用三种基本结构组成的程序必然是结构化的程序，这种程序便于编写、便于阅读、便于修改和

。结构化程序设计强调程序设计风格和程序结构的规范化，提倡清晰的结构。结构化程序设计方法的基本思路是：把一个复杂问题的求解过程分阶段进行，每个阶段处理的问题都控制在人们容易理解和处理的范围内。§

2.5

结构化程序设计方法采取以下方法来保证得到结构化的程序：自顶向下；逐步细化；模块化设计；结构化编码。两种不同的方法：自顶向下，逐步细化；自下而上，逐步积累。用这种方法逐步分解，直到作者认为可以直接将各小段表达为文字语句为止。这种方法就叫做“自顶向下，逐步细化”自顶向下，逐步细化方法的优点：结构清晰，层次分明容易写，容易读。如果发现某一部分中有一段内容不妥，需要修改，只需找出该部分修改有关段落即可，与其它部分无关。

提倡采用自顶向下，逐步细化的方法来设计程序。模块设计的方法模块化设计的思想实际上是一种“分而治之”的思想，把一个大任务分为若干个子任务，每一个子任务就相对简单了。在拿到一个程序模块以后，根据程序模块的功能将它划分为若干个子模块，如果这些子模块的规模还嫌大，还再可以划分为更小的模块。整个过程采用自顶向下方法来实现。子模块一般不超过50行划分子模块时应注意模块的独立性，即：使一个模块完成一项功能，耦合性愈少愈好。552.6

常用算法简介.22.6.3枚举算法迭代算法贪心算法562.6

常用算法简介实际工程中会遇到许多复杂的计算问题，有的问题若采用劣质算法求解，即便在巨型计算机上可能也要花费数个月时间，但采用优秀算法，可能在一台普通计算机上也仅需几分钟甚至数十秒就能解决。所以算法设计水平的优劣，对于问题的求解非常重要。可以将所有算法粗分为简单的算法和复杂的算法两大类：简单的算法：①一般有公式作为算法描述。②算法通过 计算解决问题。例如工程学、力学、数学等学科中电压=电阻*电流浮力=液体密度*物体排开液体的体积圆的面积=圆周率*半径*半径圆柱体体积=底面积*高输入和输出描述。即所谓“IPO”（输入-处理-输出）前面的例1--温度转换就是简单算法。57复杂的算法：①一般没有终极公式作为问题解法。②可通过一次次反复计算逐步得到问题的解或近似解。③每个计算周期计算问题的一部分或得到一个更好的近似解。用简单问题的解逐步

近原始问题解，适合于计算机求解。5859求两个数的最大公约数算法分析：这是一个经典的程序设计例子，可用多种算法完成该任务。方法一：直接用最大公约数的定义求解。例如，求252和105的最大公约数252/105

余数不为0

=〉不能整除（从稍小的数开始试算）？252/104与105/104？252/103与105/103？……×(不能整除)×(不能整除)×(不能整除)？252/21与105/21

能整除=〉最大公约数为21复杂算法举例方法二.求最大公约数的

算法定理：两个整数的最大公约数等于其中较小的数和两数的差的最大公约数。例如，求252和105的最大公约数252-105=147147-105=42105-42=6363-42=2142-21=21=>最大公约数为21因为：252-105*2=42105-42*2=21原来两数的最大公约数，等于除数和余数的最大公约数60方法三.用”辗转相除”算法求最大公约数原理：对所求的两个数p和q

(求greatest

common

divisor)(p,q)= (q,p%q)【这里%为取余数符号】当p%q为0时，两数的最大公约数即为q（将大数作为被除数，小数作为除数，若二者余数不为0，则将小数作为被除数，余数作为除数，…直到余数为0。）例如，求252和105的最大公约数252%105=〉42105%42=〉2142%21=〉0=>最大公约数为2161用自然语言描述”辗转相除”算法步骤1：任意输入两个数放入p和q中步骤2：如果p<q，交换p和q步骤3：求出p/q的余数放入r中步骤4：如果r=0则执行步骤8，否则执行下一步步骤5：令p= =r步骤6：计算p和q的余数r步骤7：执行步骤4步骤8：q就是所求的结果，输出结果q62用流

描述”辗转相除”算法6364u=int(input("请输入第一个整数："))v=int(input("请输入第二个整数："))if

v>u:u,v=v,ur=u%vwhiler!=0:u=vv=rr=u%vprint("最大公约数:",v)最大公约数的python实现65枚举法就是按问题本身的性质，一一列举出该问题所有可能的解，并在逐一列举的过程中，检验每个可能解是否真正满足问题所求。若是则采纳这个解，否则抛弃它。【例2-3-1】．求1-1000中，能被3整除的数。算法：从1-1000中一一列举，这是一个循环结构在循环中对每个数进行检验：凡是能被3整除的数，打印输出，否则继续下一个数。2.3.1

枚举算法流

：求1-1000中，能被3整除的数66【例2-3-2】判断谁是小偷。有四个嫌疑人：a说："我不是小偷。"b说："c是小偷。"c说："小偷肯定是d。"d说："c冤枉人！"四人中除小偷外有三人说的是真话，问到底谁是小偷？提示：依次假设a、b、c、d为小偷，然后判断他们说的话逻辑上是否合理：即四句话中正好有三句为“真”6768枚举法的基本思想根据问题描述和相关的知识，能为该问题确定一个大概的解空间范围。枚举法就是对该解空间范围内的众多候选解按某种顺序进行逐一枚举和检验，直到找到一个或全部符合条件的解为止。计算机程序实现枚举算法的基本方法是：用循环结构实现一一列举的过程，用分支结构实现检验的过程。692.3.2

迭代和递推算法迭代:是一种不断用变量的旧值递推新值的过程。迭代算法是计算机解决问题的一种基本方法。它利用计算机运算速度快、适合做重复性操作的特点，从一个初始变量值出发，让计算机对一组指令（或一定步骤）进行重复执行，每次执行这组指令（或步骤）时，都从变量的原值推出它的一个新值。最终得到所求解。例：验证谷角猜想数学家

发现，对应一个自然数n，若n为偶数，则将其除以2；若n为奇数，则将其乘以3再加1。经过有限次运算后，总可以得到自然数1。70验证谷角猜想的算法流：7172应用迭代算法的通常步骤确定迭代变量在可以用迭代算法解决的问题中，至少存在一个直接或间接地不断由旧值递推出新值的变量，这个变量就是迭代变量。一般在确定迭代变量的同时，还要指定其初始值。建立迭代关系式所谓迭代关系式，是指如何从变量的前一个值推出其下一个值的公式（或关系）。迭代关系式的建立是解决迭代问题的关键，通常可以顺推或倒推的方法来完成。73(3)．对迭代过程进行控制什么时候结束迭代过程？这是编写迭代程序必须考虑的问题。根据算法“有限性”的性质，不能让迭代过程无休止地重复执行下去。迭代过程的控制通常有两种情况：所需的迭代次数是个确定的值，可以计算出来。可以构建一个固定次数的循环来实现对迭代过程的控制。（常用for语句)所需的迭代次数开始时无法确定。需要进一步分析出用来结束迭代过程的条件。例如，当计算精度满足要求后结束。(常用while语句)那契(Fibonacci)数列的计算

那契(Fibonacci)数列，又称黄金分割数列，指的是这样一个数列：0、1、1、2、3、5、8、13、21、……在数学上，

纳契数列以如下被以递归的方法定义：F（0）=0，F（1）=1，F（n）=F(n-1)+F(n-2)（n≥2，n∈N*）养兔子模型，就是一个Fibonacci数列。假设一对兔子从出生后的第三个月开始，每个月都繁殖一对兔子，如没有或出售，每个月的兔子数形成一个Fibonacci数列。74求Fibonacci数列的前40个数的流75762.3.3

贪心算法贪心算法（又称贪