《数据结构与算法:Python语言描述》一第1章 绪论

第1章 绪论

作为基于Python语言的“数据结构与算法”教程,本章首先讨论一些与数据结构和算法有关的基础问题,还将特别关注Python语言的一些相关情况。

1.1计算机问题求解

使用计算机是为了解决实际问题。计算机具有通用性,其本身的功能很简单,就是能执行程序,按程序的指示完成一系列操作,得到某些结果,或者产生某些效果。要想用计算机处理一个具体问题,就需要有一个解决该问题的程序。经过长期努力,人们已经为各种计算机开发了许多有用的程序。在面对一个需要解决的问题时,如果恰好有一个适用的程序,事情就很方便了:运行这个程序,让它去完成所需工作。
实际中的计算需求无穷无尽,不可能都有现成的程序。如果面对一个问题,但没有适用的程序,可能就需要编写一个。一般而言,人们需要的不是解决一个具体问题的程序,而是解决一类问题的程序。例如,一个文本编辑器不应该只能编辑出一个具体的文本文件,而应该能用于编辑各种文本文件;Python解释器不是只能执行一个具体的Python程序,而是可以执行所有可能的Python程序。对于求平方根这样的简单问题,人们希望的也不是专用于求某个数(例如2)的平方根的函数,而是能求任何数的平方根的函数。求平方根是一个问题,求2的平方根是求平方根问题的一个实例。人们开发(设计,编写)一个程序,通常是为了解决一个问题,该程序的每次执行能处理该问题的一个实例。
简言之,用计算机解决问题的过程分为两个阶段:程序开发者针对要解决的问题开发出相应的程序,使用者运行程序处理问题的具体实例,完成具体计算(实际上,是计算机按程序的指示完成计算。为简单起见,人们常说程序完成计算,这样说不会引起误解)。开发程序的工作只要做一次,完成的程序可以多次使用,每次处理一个问题实例。当然,对于复杂的程序,完成后通常还需要修改完善,消除错误,升级功能。但这些是后话,无论如何,用计算机解决问题的第一步是开发出能解决问题的程序。

1.1.1程序开发过程

程序开发就是根据面对的问题,最终得到一个可以解决问题的程序的工作过程。真正的问题来自实际,是不清晰和不明确的,而程序是对计算机操作过程的精确描述,两者之间有着非常大的距离。因此,一般而言,程序开发工作需要经过一系列工作阶段才能完成。由于人的认识能力的限制,其中还可能出现反复。图1.1刻画了这一过程中的各个工作阶段,以及实际程序开发的工作流程。
分析阶段:程序开发的第一步是弄清问题。实际中提出(发现)的问题往往是模糊的,缺乏许多细节,是一种含糊的需求。因此,程序开发的第一步就是深入分析问题,弄清其方方面面的情况和细节,将问题严格化,最终得到一个比较详尽的尽可能严格表述的问题描述。在软件开发领域,这一工作阶段通常被称为需求分析。
设计阶段:问题的严格描述仍然是描述性的,而计算机求解是一个操作过程。“一个问题是什么”与“怎样做才能解决它”并不是一件事,在真正编程之前,需要先有一个能解决这个问题的计算过程模型。这种模型包括两个方面,一方面需要表示计算中处理的数据,另一方面必须有求解问题的计算方法,即通常所说的算法。由于问题可能很复杂,其中牵涉的数据不仅可能很多,数据项之间还可能有错综复杂的关系。为了有效操作,就需要把这些数据组织好。数据结构课程的主要内容就是研究数据的组织技术。如何在良好组织的数据结构上完成计算是算法设计的问题,是本书讨论的另一个重点。

编码阶段:有了解决问题的抽象计算模型,下一步工作就是用某种适当的编程语言实现这个模型,做出一个可能由计算机执行的实际计算模型,也就是一个程序。针对抽象计算模型的两个方面,编程中需要通过语言的各种数据机制实现抽象模型中设计的数据结构,用语言的命令和控制结构实现解决问题的算法。
检查测试阶段:复杂的程序通常不可能一蹴而就,写出的代码中可能有各种错误,最简单的是语法和类型错误。通过人或计算机(语言系统,编译器)的检查,可以发现这些简单错误。经过反复检查修改,最后得到了一个可以运行的程序。
测试/调试阶段:程序可以运行并不代表它就是所需的那个程序,还需要通过尝试性的运行确定其功能是否满足需要,这一工作阶段称为测试和调试。程序运行中可能出现动态运行错误,需要回到前面阶段去修改程序,消除这种错误。也可能发现得到的结果或效果不满足问题需要,这种错误称为逻辑错误。逻辑错误可能反映出编程中的失误,也可能是前面的算法设计有问题,甚至是开始的问题分析没做好。无论如何,发现错误之后,需要设法确定造成问题的原因,回到前面某个工作阶段去做适当的修正。然后根据情况在开发的后续步骤中做相应调整。这些工作需要反复进行,直至得到令人满意的程序。
图1.1和上面的说明阐释了从问题出发,最终得到可用程序的开发过程。在工作的第二和第三个阶段,算法和数据结构的设计和运用技术都扮演着重要角色:在第二个阶段需要设计抽象的数据结构和算法,第三个阶段考虑它们在具体编程语言中的实现。在设计阶段针对具体问题,建立一个可以用计算机实现的问题求解模型,而编码阶段(加上后续工作)真正实现这个求解模型,完成一个可以在计算机上运行的程序。
相对而言,设计阶段的工作更困难一些。其工作基础是问题的说明性描述,有关信息并不能简单地映射到问题的操作性求解过程中,需要人的智力参与。为了完成这一工作,需要考虑被求解问题的性质和特点,参考人们用计算机解决问题的已有经验、已经开发的技术和方法。这方面的一些讨论将是本课程的重要内容。
编码阶段的工作相对容易一些。例如要用Python作为编程语言来解决问题,就需要把已经建立的抽象数据模型映射到Python语言可以表示的结构,把实际问题的抽象求解过程映射到一个用Python语言描述的计算过程。这两方面配合就得到了一个用Python语言写出的解决问题的程序。
下面将通过实例说明程序开发中的一些情况。

1.1.2 一个简单例子

虽然一个问题的说明性描述与其操作性描述表达的是同一个问题,但它们却非常不同。前者说明了需要解决的问题是什么,针对什么样的问题,期望什么样的解;而后者说明通过怎样的操作过程可以得到所要的解。对于一个给定的问题,用某种严格方式描述一个求解过程,且对该问题的每个实例,该过程都能给出解,这个描述就是解决该问题的一个算法。从算法到与之对应的程序,映射关系比较清晰。
现在用一个最简单的问题来说明。假设需要求出任一个非负实数的平方根。这句话是问题的一个非形式描述,工作的第一步就是需要把它严格化。
首先假设实数是一个已经清楚的概念,基于它考虑这个问题。在上面说明中,没有讲清楚的概念是平方根。根据数学中平方与平方根的定义,非负实数 x 的平方根就是满足等式 y×yx 的非负实数y。这是一个严格的数学定义,说明了结果y应该满足的条件。但是,它并没有给出一种从任一x求出满足这个条件的y的方法。
从计算的角度看,上面定义还有一个重大缺陷:对于给定的数值,即使它只包含有穷位小数,其平方根通常也是一个无理数,不能写成数字的有穷表示形式。计算都需要在有穷步内完成,应该是一种有穷过程。因此一般而言,通过计算只能得到实数的平方根的近似值。在考虑求平方根的计算方法(算法)时,这个问题必须考虑,必须把近似误差作为参数事先给定。基于这一看法,上述问题可以修改为:对任意非负实数x,设法找到一个非负实数y,使得| y×y-x |<e,其中e是事先给定的允许误差。
这样就有了问题的一个严格描述。但这个描述是说明性的,说明了需要什么样的y,并没有告诉人们怎么得到这个结果。平方根是一个数学概念,要找到计算平方根的过程性描述(算法),也需要通过数学领域的知识。
人们已经提出了一些求平方根的方法。基本算术课程中介绍过如何求任一正实数的平方根,但在那个方法里需要做试除,不太适合机械进行(可以实现,但比较麻烦)。而求平方根的另一种算法称为牛顿迭代法,描述如下:
0.对给定正实数x和允许误差e,令变量y取任意正实数值,如令y=x;
1.如果y×y与x足够接近,即| y×y-x |<e,计算结束并把y作为结果;
2.取z=(y+x/y)/2;
3.将z作为y的新值,回到步骤1。
首先,这是一个算法,因为它描述了一个计算过程。只要能做实数的算术运算、求绝对值和比较大小,就可以执行上面描述说明的计算过程。
但是,要确定这个算法能求出实数的平方根,还需要证明两个断言:①对任一正实数x,如果算法结束,它一定能给出x的平方根的近似值;②对任意给定的误差e,这个算法一定结束(实际上,这件事还与误差e和计算机实数表示精度有关)。
第一个断言很清楚,步骤1的条件 | y×y-x |<e说明了这个断言成立。第二个断言则需要一个数学证明,证明计算过程中 y 值的序列一定收敛,其极限是 x 的平方根。这样,只要迭代的次数足够多,| y×y-x | 就能任意小,因此对任何允许误差 e,这个循环都能结束。这个问题请读者自己考虑,这里不进一步讨论。
有了上面算法,写出相应Python程序已经不困难了。很容易定义一个完成平方根计算的Python函数,实现上述算法。下面是一个定义:

def sqrt(x):
  y = 1.0
  while abs(y * y – x) > 1e-6:
       y = (y + x/y)/2
  return y

其中变量y的初值为1.0,允许误差为10-6。通过用各种数值测试,可以看到这个函数确实能完成所需要的工作。
从这个简单实例可以看到从问题的描述出发最终得到一个可用程序的工作过程。由于求平方根的问题比较简单,特别是其中涉及的数据只是几个简单实数,数据组织的工作非常简单。下一节的实例将更好展现数据组织的有关情况。
还有一个情况值得注意。在上述例子中,最不清晰的一步就是从平方根的定义到求平方根的算法。算法设计是一种创造性工作,依赖于对问题的认识和相关领域的知识,没有放之四海而皆准的路径可循。计算机科学领域有一个研究方向是算法的设计与分析,计算机教育中有相应课程,其中讨论算法设计和研究的许多经验,总结算法设计中一些规律性的线索和思路。但经验也只是经验,在设计新算法时可以参考,但不能保证有效。算法分析则是分析算法的性质,将在1.3节进一步介绍。

时间: 2017-05-02

《数据结构与算法:Python语言描述》一第1章 绪论的相关文章

《数据结构与算法 C语言版》—— 第1章 绪论

第1章 绪论 随着计算机产业的飞速发展,计算机的应用领域越来越广泛,已不再局限于科学计算,而是更多地用于控制.管理及数据处理等非数值计算的处理工作.所有的系统软件和应用软件都要用到各种类型的数据结构,在计算机中如何组织数据.处理数据就成了人们进行程序设计的关键所在.因此,我们必须研究数据的特性和数据间的相互关系及其对应的存储表示,并设计出相应的算法,更好地实现程序.数据结构是计算机专业的核心课程,该课程的学习可以帮助人们更好地进行程序设计,解决实际问题.

《数据结构与算法 C语言版》—— 第3章 栈 与 队 列

第3章 栈 与 队 列 栈和队列是在软件设计中常用的两种数据结构,它们的逻辑结构与线性表相同.其特点在于操作受到了限制:栈按"后进先出"的规则进行操作,队列按"先进先出"的规则进行操作.故称它们为操作受限制的线性表.

《数据结构与算法 C语言版》—— 第2章 线性表

第2章 线性表 线性结构是一种最简单.最基本,也是最常用的数据结构.线性结构的特点是数据元素之间是一种线性关系,即在数据元素的非空集合中:1)存在唯一的一个被称为"第一个"的数据元素:2)存在唯一的一个被称为"最后一个"的数据元素:3)除最后一个元素外,集合中每个数据元素均有唯一的后继:4)除第一个元素之外,集合中每个数据元素均有唯一的前驱.

《数据结构与算法:Python语言描述》一1.3算法和算法分析

1.3算法和算法分析 本节集中讨论算法的问题,特别是算法的性质及其分析技术. 1.3.1问题.问题实例和算法 在考虑计算问题时,需要清晰地区分问题.问题实例和算法三个概念,并理解它们之间的关系,这就是本小节讨论的内容.三个基本概念考虑一个计算问题时,需要注意到三个重要概念:问题:一个问题W是需要解决(需要用计算求解)的一个具体需求.例如判断任一个正整数N是否为素数,求任一个方形矩阵的行列式的值等.虽然可以严格定义"问题"的概念,但在这里还是想依靠读者的直观认识.总而言之,现实世界中存在

《数据结构与算法:Python语言描述》一1.2 问题求解:交叉路口的红绿灯安排

1.2 问题求解:交叉路口的红绿灯安排 本节展示一个具体问题的计算机求解过程,以此说明在这种过程中可能出现的一些情况,需要考虑的一些问题,以及一些可能的处理方法. 交叉路口是现代城市路网中最重要的组成部分,繁忙的交叉路口需要用红绿灯指挥车辆通行与等待,正确的红绿灯调度安排对于保证交通安全.道路运行秩序和效率都非常重要.交叉路口的情况多种多样,常见形式有三岔路口.十字路口,也有较为少见的更复杂形式的路口.进一步说,有些道路是单行线,在中国的交叉路口还有人车分流和专门的人行/自行车红绿灯等许多情况,

《数据结构与算法:Python语言描述》一2.3类的定义和使用

2.3类的定义和使用 前面给出了两个有理数类的定义,帮助读者得到一些有关Python类机制的直观认识.本节将介绍Python类定义的进一步情况.本书中对类的使用比较规范,涉及的与Python类定义相关的机制不多,只需要有最基本的了解就可以学习后面内容.另一方面,本书的主题是数据结构和算法,并不计划全面完整地介绍Python语言的面向对象机制和各种使用技术.本节主要想给读者提供一些可参考的基本材料,因此,下面有关Python语言的相关介绍将限制在必要的范围内,供读者参考,不深入讨论.有关Pytho

《数据结构与算法:Python语言描述》一3.5表的应用

3.5表的应用 本节通过一个简单的例子展示表结构的使用.这里给出了同一个问题的几种不同实现,其中使用了不同的表结构. 3.5.1Josephus问题和基于"数组"概念的解法 Josephus问题是数据结构教材中一个常见的实例:假设有n个人围坐一圈,现在要求从第k个人开始报数,报到第m个数的人退出.然后从下一个人开始继续报数并按同样规则退出,直至所有人退出.要求按顺序输出各出列人的编号.本节考虑第一种解决方法:基于Python的list和固定大小的"数组"概念,也就是

《数据结构与算法:Python语言描述》一1.4数据结构

1.4数据结构 从程序输入和输出的角度看,用计算机解决问题,可以看作实现某种信息表示形式的转换.如图1.5所示,把以一种形式表示的信息(输入)送给程序,通过在计算机上运行程序,产生出以另一种形式表示的信息(输出).如果: 具体的"信息表示A"表达了需要求解的某个问题的实例. 得到的"信息表示B"表达了与这个实例对应的求解结果. 那么就可以认为,这个程序完成了该问题实例的求解工作. 为了能用计算机处理与问题有关的信息,就必须采用某种方式表示它,并将相应表示送入计算机.

《数据结构与算法:Python语言描述》一第3章 线 性 表

第3章 线 性 表 在程序里,经常需要将一组(通常是同为某个类型的)数据元素作为整体管理和使用,需要创建这种元素组,用变量记录它们,传进传出函数等.一组数据中包含的元素个数可能发生变化(可以加入或删除元素).在有些情况下,可能需要把这样一组元素看成一个序列,用元素在序列里的位置和顺序,表示实际应用中的某种有意义的信息,或者表示数据之间的某种关系.线性表(简称表)就是这样一组元素(的序列)的抽象.一个线性表是某类元素的一个集合,还记录着元素之间的一种顺序关系. 线性表是最基本的数据结构之一,在实际