《从问题到程序:用Python学编程和计算》——3.4 定义函数-阿里云开发者社区

开发者社区> 华章出版社> 正文
登录阅读全文

《从问题到程序:用Python学编程和计算》——3.4 定义函数

简介:

本节书摘来自华章计算机《从问题到程序:用Python学编程和计算》一书中的第3章,第3.4节,作者 裘宗燕,更多章节内容可以访问云栖社区“华章计算机”公众号查看。

3.4 定义函数

在最简单的程序中,可能只用到表达式、语句和几种控制结构。但是,仅限于这些基本机制,很难写出很长的解决复杂问题的程序。随着遇到的问题更复杂,我们必须组织好程序的结构,在语句层面之上的基本结构就是函数。一个函数包装起一段代码并给予命名,引进参数将其通用化。定义好的函数可以通过调用表达式使用,非常方便。学习编程的重要一步就是学习定义函数:理解为什么需要定义函数,学会识别编程中定义函数的需求,掌握正确定义函数的技术。本小节和下一章将集中讨论这个问题。

3.4.1 为什么定义函数

实际中需要用程序处理的问题都很复杂,学习编程,也必须学习处理复杂问题的思想和技术。要处理的问题越复杂,解决它的程序也会越长。越长的程序将更难开发、更难阅读和理解,编程序的人也更难把握,这些情况又影响到开发者对程序功能的把握和检查,以及后续的维护。在修改一个程序时,必须清楚地理解所做改动对整个程序的影响,修改不当就可能破坏程序的内在一致性。显然,程序变得更大了之后,理解要做的修改对程序行为的影响也更困难。此外,随着程序变大,其中更容易出现在不同地方需要做相同或类似工作的情况,分别写出代码既会使程序变长,也增加了不同部分之间的互相联系。

在科学与工程领域,解决复杂问题的基本方法就是将其分解为相对简单的子问题,分别处理,然后用子问题的解去构造整个问题的解。为了支持复杂计算过程的描述,程序语言需要提供分解手段。随着人们对程序设计实践的总结,一些抽象机制被引进各种编程语言。这些机制非常重要,不理解它们的功能和使用技术,就不可能把握和处理复杂的计算过程,完成复杂的程序或软件系统。Python中最基本的抽象机制就是函数。

从理论上说,编程语言里的函数定义功能并没有带来新的计算描述能力。没有这种功能的编程语言也可以描述所有可能的计算。但从编程实践的角度看,选择适当的计算描述代码,将其定义为函数,却是一项极其重要的工作。没有这样一套结构,根本不可能写出解决复杂问题的好程序。

在计算机发展的早期,确实出现过不提供函数定义功能的编程语言。但人们在使用中发现,用这样的语言描述比较大的程序,例如几千行代码的程序,是非常困难的。因此,今天所有流行的语言都提供了函数定义或其他类似功能。下面先讨论函数定义的意义。

函数抽象的意义

一个函数是一段代码的包装和抽象,它应该实现某种有用的计算。定义好的函数可以在程序里调用,要求执行其中包装的代码。但是,我们显然可以以适当方式把这段代码直接写在调用该函数的地方,为什么要把它定义为一个函数呢?

例如,我们可以定义一个函数cube实现立方的计算,在需要时写调用:

c1 = cube(x)
c2 = cube(y)

也可以不写函数定义,在这些地方直接写:

c1 = x * x * x
c2 = y * y * y

采用前一写法有什么好处?这是一个功利性的问题。

实际上,定义函数的效益是多方面的,下面说明一些情况:

image
image
image

函数和函数分解还有很多可能的作用。此外,除了函数可以作为有用的程序模块外,Python还提供了另外一些可以作为程序模块的结构,有关情况将在后面介绍。

上述讨论中提出了函数的一些重要作用,其中许多还派生出一些对任何软件开发都非常重要的原则或技术。例如,作用2中讨论的问题被人们总结为一条重要的编程原则(唯一定义原则):程序中的任何重要功能都应该只有一个定义。作用3倡导的程序构造方式被称为自下而上的程序开发,从底层出发,一步步向上构造有用的功能块,支持复杂功能的实现;作用4提出的程序构造方式被称为自顶向下的程序开发,又称为逐步求精。这些原则和做法都非常重要,在后面的章节和后续课程里,可以看到许多相关的例子和讨论。

函数和程序

一个Python程序由一系列语句构成,执行这个程序就是一个个地执行其中的语句。一些语句直接完成计算,或者做赋值,或者产生输入输出,控制语句的执行将指挥其中的语句块完成各种操作。Python程序中的函数定义也是语句,其执行并不完成任何有价值的实际计算,而是完成一个函数的定义工作。

每个函数的体中封装了一段代码,函数头部描述外部与这个函数的联系:函数名是什么,外部可以通过哪些参数给函数送进信息。参数表里列出函数的形式参数,简称形参,用参数名表示。函数有返回值,但返回值的情况在函数头部并不描述,由函数体里的return语句确定。如果没提供返回值,函数自动返回None值。

到目前为止,我们已经看到的Python程序都是由一系列普通的语句(包括控制结构)和一些函数定义组成,后面还会看到其他结构。在程序执行时,普通语句直接产生效果,而函数定义的执行只是做好一个函数对象,并给它命名,并不执行函数体里的语句。只有被明确调用时函数才进入执行状态。易见,要想在程序的执行中起作用,一个函数或者需要被程序里的普通语句直接调用,或者需要被另一个被调用执行的函数调用。没被调用的函数不会在程序的执行中起任何作用。

前面章节里已经给出过一些函数定义实例。下面主要关注程序的函数分解,研究与函数的定义和使用有关的各种问题,其中将特别关注函数头部的设计问题。

3.4.2 学习定义函数

函数定义是一种比较复杂的程序结构。要定义好一个函数,必须按语言规定的形式写出函数的各个结构成分,包括函数头部的函数名和参数表,以及相应的函数体。不满足有关语法就不是一个函数定义。显然,定义函数,最重要的问题还是函数功能的选择和程序功能的分解。下面将讨论与函数定义有关的思考过程和一些重要技术细节。

函数定义中的工作

显然,函数定义不应是随心所欲的产物,应该是深入分析和理解问题之后的设计。定义函数时需要做的工作很多,包括:

image

最后一个问题虽然很重要,但却是一般编程都需要考虑和处理的问题,不是仅与定义函数有关的特殊问题,因此不是本节主题。下面主要关注前两个问题。

程序的函数分解

image
image
image
image
image
image
image
image

3.4.3 函数:两种观点及其联系

从形式上看,一个函数就是包装起来并予以命名的一段代码(还有参数化),是程序中具有逻辑独立性的动作性实体。函数需要定义,又能作为整体在程序中调用,完成其代码描述的工作。函数封装把函数内部与其外部分开,形成两个相互隔离的世界,站在这两个不同的世界看问题,就形成了对于函数的内部观点和外部观点。一边是站在在函数之外,从函数使用者的角度看函数;另一边是站在函数内部,从定义者的角度看。看到两者之间的差异和联系,对认识函数,思考与函数相关的问题,都是非常重要的。

函数内部和外部

图3.5列出了从这两种不同角度看函数时需要考虑的一些重要问题。函数头部规定了函数内部和外部之间的交流方式和通道,定义了函数内部和外部都需要遵守的共同规范。

image

从一个函数的外部看,该函数实现了某种有用的功能。只要知道函数名和参数的情况就可以使用它,利用其功能。在调用函数时提供数目和类型适当的实参,正确接受返回值,就能得到预期的计算结果或者效果。

使用函数时,我们不应该关心函数功能的具体实现。这种超脱很重要,不掌握这种思想方法,就无法摆脱琐碎细节的干扰,不能处理复杂问题。初学者常犯的一个毛病是事事都想弄清楚。这种考虑不但常常不必要,有时甚至不可能。例如,对Python内置函数,我们不知道它们的实现方法,这并不妨碍在程序中正确使用它们。

内部观点是函数实现者的考虑,所关心的问题自然不同。这时的重要问题包括函数调用时外部将提供哪些数据(由参数表规定),各为什么类型(对Python程序,我们无法在描述上对参数提出类型要求,但在心里应该有明确的认识);如何从这些参数出发完成所需计算,得到所需结果(算法问题);函数应在什么情况下结束?如何产生返回值?在考虑函数实现时,不应关心程序的哪些地方将调用它,提供的具体实参值是什么等。

函数头部的重要性就在于它描述了函数内部和外部之间的联系,是两方交换信息的接口。如前面实例所示,在定义函数之前应首先有一个全面考虑,据此定义好函数的头部,规定好一套规范(特别是函数的参数)。此后开发者的角色就分裂了,应该根据是定义函数还是使用函数去观察和思考问题。实际上,一旦清晰地确定了函数的功能,描述好函数头部之后,函数的定义和使用完全可以由两个人或两批人分别做。只要他们遵循共同规范,对函数功能有共同理解,就不会有问题。在大型软件的开发中,经常需要做这种分解。

注意,这两句话很重要:“遵循共同规范”,“对函数功能有共同理解”,人们经常在这里出现偏差。我们写程序时也必须注意,务必保证对同一函数的两种观点之间的一致性。

下面分别进一步研究从这两个角度考虑函数时遇到的问题。

函数的定义

确定了需要定义的函数的功能、参数和返回值的安排,并选择了适当的函数名之后,下面的工作就是写出函数体的代码,完成函数的定义。

如果所需函数的功能比较简单,很容易基于Python基本操作和内置函数描述好,就可以直接完成函数的定义。如果函数要做的工作比较复杂,可以考虑进一步对它做功能分解,把其中有意义的重要部分抽象为另外的一个(或几个)函数,通过函数调用完成操作,而后再实现那个(或那些)函数。这样做就产生了另一层功能分解。这种分解可以一层层做下去,直到所需功能可以比较容易地直接实现为止。

在Python语言里定义函数,有一个问题需要注意:定义的头部无法描述对参数的要求,而实际上,多数函数对其参数都有某些特殊要求。例如:

image

虽然Python中的文字量都有确定的类型,但是一个变量可以以任何类型的对象为值。因此,一般而言,我们无法根据上下文确定一个表达式(包括函数实参)的类型。换句话说,某个调用的实参是否满足函数的需要,要到实际执行该函数调用时才能确定。在这种情况下,要保证函数里的计算有意义,就需要在程序里做一些必要的检查。这种检查有可能很复杂,前面遇到过这样的例子,例如定义基于三角形的三条边求面积函数:

def triangle(a, b, c):
    if a > 0 and b > 0 and c > 0 and \
       a + b > c and b + c > a and a + c > b:
        s = (a + b + c)/2
        return (s * (s – a) * (s – b) * (s – c))**0.5
    else:
        return float("nan")

由于Python没有对实参类型的强制性要求,因此上面有关函数参数的条件还不够。实际上,为提供完整的保证,这里首先需要检查几个参数的类型。

要求一个表达式e的类型是t,可以写条件表达式type(e) == t,例如上面函数中可以增加条件type(a) == float等。Python的标准写法是调用内置函数isinstance(a, int),它是检查a的值是否为类型float的一个实例。

把上面函数的检查补充完全,应该写:

def triangle(a, b, c):
    if (ininstance(a, int) or isinstance(a, float)) and \
       (ininstance(b, int) or isinstance(b, float)) and \
       (ininstance(c, int) or isinstance(c, float)) and \
        a > 0 and b > 0 and c > 0 and \
        a + b > c and b + c > a and a + c > b:
        s = (a + b + c)/2
        return (s * (s – a) * (s – b) * (s – c))**0.5
    else:
        return float("nan")

这里假设允许整数和浮点数作为边长。上面的条件总共写了5行,前面几行都需要续行符。还应注意or的优先级低于and,这里必须写括号。

上面讨论中提出的方法是在函数开始用一个条件语句检查参数,在参数满足条件时才去做正常的计算。这种做法很合理。但是,如果实际参数不满足函数的需要,后面的代码应该怎么写?这是一个很棘手的问题,只能根据具体情况处理。上面函数中采用了返回特殊浮点值的方式,是一种可能的做法。实际上,Python语言为执行中发现错误和错误的处理提供了更高级的处理机制,有关情况将在第6章讨论。

另一可能想法是设法给使用者提供一些信息,希望他们总用合法的参数调用函数。这方面的常规做法是用注释说明函数对参数的要求,还可以同时说明函数的功能、用法等。注释是仅供人阅读的程序成分,Python解释器在处理程序时,将简单丢掉其中的所有注释。为了能在程序执行中提供信息,Python增加了称为文档串的机制。

如果在一个函数体里的第一个语句是一个字符串,这个串就是函数的文档串。Python对出现在这里的串做特殊处理,将其保存在执行环境中,使人可以在程序运行中查看。人们通常用函数的文档串描述函数对参数的要求和函数的功能。由于这种描述可能较长,一般采用一对三引号的字符串形式,在程序中占据多行。

实际上,为函数提供文档串,已经成为Python编程中的一种常规做法。Python的内置函数,标准库程序包里的各种函数等都有文档串。例如:

>>> print(abs.__doc__)
abs(number) -> number

Return the absolute value of the argument.

上面print输出的三行就是内置函数abs的文档串内容。解释器把文档串保存在函数名下的 doc 成分中(注意,doc前后各有两个下划线符)。内置函数abs的文档串说该函数要求一个数作为参数,返回一个数。实际功能是返回参数的绝对值。

前面说过,在函数体里,形参也看作局部变量,其特点就是在函数体开始执行前已经有了值,它们的值由函数调用时的实参(表达式)得到。形参在函数体内的使用方式与其他变量一样,可以再次赋值。如果执行到某个位置这个函数应该结束,就应该写一个return语句,并根据需要用return之后的表达式描述返回值。

如果我们定义的一些函数非常有用,可以将它们包装成模块,供自己在今后的编程中使用。有价值的模块还可以提供给别人使用。各种标准库、重要的第三方Python程序库,也就是这样逐步发展起来的。

函数的调用

函数调用的形式是函数名后面跟一对圆括号,括起用逗号分隔的若干表达式,这些表达式称为实际参数,简称实参。调用函数时,必须提供一组数目正确、类型和值满足函数需要的实参,才能得到我们期望的结果。

如果要调用的是无参函数(函数定义的参数表为空),也必须写一对空括号,不能省略。如果提供的实参个数不对(多了或者少了),执行这个函数调用时,解释器就会报TypeError错(类型错误)。如果实参的类型或者值不符合需要,函数执行中有可能报出某种错误,也可能得到奇怪的结果,或者出现其他问题(例如进入死循环)。例如:

image

具体现象将因情况的不同而不同。

函数调用是一种基本表达式,它们经常出现在表达式里(进而出现在语句里),调用代码段通过赋值等方式获得函数的返回值。实际上,即使一个函数返回有意义的值,Python也允许我们不使用其返回值,为此只需把函数调用写成一个独立的语句。如果函数有返回值,但在调用时没有用,解释器就把这个返回值简单丢掉。对于返回值为None的函数,通常总是写独立的调用语句。例如前面反复使用的内置函数print。

在函数调用执行时,解释器顺序地(从左到右)算出每一个实参表达式的值,得到一组结果对象;让对应的函数形参分别以这些对象为值,然后执行这个函数的体。在函数里对形参赋值不会影响函数调用时的实参,即使相应的实参是变量。Python明确规定从左到右求值实参表达式。这个规定在一些情况下也可能造成影响。后面会看到这样的情况。

图3.6用一个例子显示了函数调用中实参与形参的关系。这里的变量m和n作为调用f的实参,f(m,n)执行时,实参m和n的值分别送给f的形参a和b。图中箭头表示变量与值的关联关系,实线箭头表示的是函数f调用后,开始执行函数体的时刻变量和值的关联情况。可以看到,这时变量m和函数形参a以同一个对象为值,n和形参b以同一个对象为值。如果执行到函数里对b赋值的语句,就会导致b的值被修改,使b以另一个(字符串)对象为值(如图中虚线箭头所示)。但从图示可见,这个修改不会影响变量n的值。

image

如果函数调用的实参表达式又是一个函数调用,解释器就会转过去,先完成那个函数调用,把调用返回的结果作为当前调用的实参。Python允许在表达式里写出任意嵌套深度的函数调用,解释器总按上述规则处理。

函数定义和调用的关系

要保证函数的使用能得到预期效果,函数调用就必须与定义相互协调,相互配合。在实际中,我们常常希望所用的函数是“全函数”,也就是说,给它任意一个或一组类型合适的实参,它总能给出正确的函数值,或者总能完成所需工作(对于无返回值的函数)。有些函数确实是这样,例如内置函数print,它甚至对参数个数也没有明确规定。

相对而言,我们比较容易保证实际参数的类型满足函数的需要,下面讨论主要针对实参的值。一般而言,很多函数对于实参的值有要求,即只能处理合法类型参数的一些情况。

前面讨论的求最大公约数函数是一个典型例子。如果两个整数都是0,其最大公约数(在数学里)没有定义。前面考虑让函数在这种情况下返回0,是自己设计的一种权宜之计。这样做有两个优点:1)使函数对所有实参情况都能返回值(把函数“补全”),以方便其使用。2)由于任何一对整数的最大公约数都不是0,因此0(相对于最大公约数的计算结果而言)是个闲置值,在计算中不会被误解。而且,在调用这个函数之后,只要检查得到的结果是不是0,就可以判断是否得到了真正的最大公约数。

应该看到,这样定义也对函数的调用提出要求。由于原来的函数不是“全函数”,调用这种函数时,有两种可能的做法:

1)保证只用符合函数实际需要的实参去调用。这就要求在每个函数调用前检查实参的值,满足条件时才调用函数。这件事可以用if语句做。但是这里也有麻烦:没有通过检查的情况怎么办?还是处理错误数据的问题,逃不掉。

2)在调用函数之后检查结果,确定返回值正确后再使用,不正确的情况另行处理。

前一方式是在调用前检查和处理,后一方式是在调用后检查和处理。两种方式都能解决问题,但都需要在每个调用的上下文中检查和处理,实现起来比较麻烦。

进一步说,有时还会遇到无法给出合适返回值的情况。举个简单例子。假定要定义一个函数,计算数轴上两个线段的长度比(取整),线段由两个端点的坐标给出。函数定义为:

image

这个函数很简单,但它对有些参数情况无定义:后一线段的两坐标相同时(退化为一个点),比率为无穷大。这个情况很难办,因为没有闲置的整数值可用(每个整数都可能是某个调用的正确结果)。这种情况下,只能采用上面的第一种办法处理:采用如上方式简单地定义好函数,要求使用者调用函数前检查参数,遇到y2 – y1为0时另行处理。

这些情况说明,一般而言,在函数的定义和调用之间往往有必要的配合。定义函数是把完成某种计算的代码包装为一个逻辑体,使之可以方便地调用。但要注意函数可能不是全的,对一些参数值不能给出结果。有些是本质性的(如两个0无最大公约数等),有些可能是实现方式造成的。在定义函数时,应尽可能定义全函数,对特殊情况给以说明。使用时必须关注函数对特殊情况的处理,采取相应措施:或是在调用前检查参数,保证函数执行不会出错;或是在调用函数后检查得到的结果,保证使用有关结果继续计算还有意义。

参数检查和断言语句assert

如果认为需要,我们可以在函数开始用条件语句检查参数并适当处理。但是,很多时候,不满足需要的实际参数应该看作运行错误,而不应该让函数返回一个任选的值。此外,有时某些变量(不一定是参数)的值不满足特定条件,操作也无法进行下去,也应该看作运行时错误。典型情况如在做除法之前发现除数为0。这些情况都说明,我们需要一种机制,以便能说明在一定条件下应该中断当前的计算。为满足这类需求,编程语言都提供了一种称为断言的机制,Python的机制是断言语句。

断言语句用关键字assert描述,这是是一种非常特殊的语句,专门用于检查某些条件是否成立。断言语句有两种形式:

image

这里的条件也称为断言,它应该是一个表示某种逻辑条件的表达式。第二种形式里的表达式可以是任意的表达式。

如果在执行中遇到第一种形式的断言语句,解释器求值其条件。如果求出的结果是真,解释器继续向下执行,就像没遇到这个断言语句一样。如果条件不为真,解释器就报AssertionError错误。默认情况下这将导致程序的执行终止。综合这两条可以看出,断言语句也就是强制要求断言成立,否则就报错。

第二种语句形式执行时的基本情况与第一种相同,只是当条件的值为假时,解释器继续求值语句中的表达式部分,把得到的值作为AssertionError的参数。

与if语句不同,断言语句只应用于描述程序(函数)正确执行的必要条件。如果用断言语句描述了参数需要满足的条件,就可以保证只有参数正确时,函数才会执行所需的计算。人们主要利用断言语句帮助程序调试,检查一些重要的执行条件。

以求阶乘的函数为例。显然,这个函数的参数必须是整数,此外,函数的参数为负时,阶乘也没有定义(在前面的函数定义中,对后者采用了权宜的做法)。加入适当的断言语句后,函数的定义是:

def fact(n):
    assert isinstance(n, int) and n >= 0
    prod = 1
    for k in range(2, n+1):
        prod = prod * k
    return prod

这里加入了参数类型检查,其实,前面许多程序(包括函数)里都可以增加这种检查。如果用不满足条件的实参调用,解释器就会报错:

>>> fact(-2)
Traceback (most recent call last):
  File "<pyshell#4>", line 1, in <module>
    fact(-2)
  File "D:/Progs/pyptop-02/fact-assert.py", line 4, in fact
    assert n >= 0
AssertionError

错误信息告诉我们,在执行哪个文件的哪个函数(给出了函数名fact)时发生错误,而且给出了行号(第4行)和出错的断言语句。根据这些信息很容易找到出错位置。断言语句的第二种形式用于提供进一步的信息。例如,将函数定义改为:

def fact(n):
    assert isinstance(n, int) and n >= 0, "Argument is " + str(n)
    prod = 1
    for k in range(2, n+1):
        prod = prod * k
    return prod

如果出错,解释器不但给出前面的信息,还会给出当时实参的值。例如:

>>> fact(-3)
Traceback (most recent call last):
  File "<pyshell#3>", line 1, in <module>
    fact(-3)
  File "D:\MyBooks\ptop-Python\Progs\basic.py", line 98, in fact
    assert isinstance(n, int) and n >= 0, "Argument is " + str(n)
AssertionError: Argument is -3

如果在程序里的某个位置,只有一些变量的值满足某些要求时,才能继续计算,就可以用断言语句描述这种要求,这样做有几方面的益处:

image

3.4.4 通用和专用的方法

编程序就是为了解决问题,而要解决问题,首先要设法找到能解决问题的方法。实际上,存在着一些应用面比较广泛的问题解决方法,可能用于解决许多问题。另一方面,也可能存在解决某个问题的特殊方法。前一类方法可称为通用的方法,后一类则是专用的方法。本节讨论这方面的一些情况。

通用求解方法

对于计算问题的通用方法,前面已有些讨论。例如生成和筛选,设法生成一组候选解,从中找出真正的解。对于一些问题,如果没办法直接找到解,而判断一个结果是否为解却比较简单,就可以考虑通过生成和筛选的方式求解。

实际上,生成和筛选只是一种求解模式,要想将它应用于具体问题,还需要针对具体问题定制这个方法。首先需要针对具体问题,设计一种生成候选解的方法,该方法应该比较简单,易于实现,而且必须保证问题的解位于其生成的候选集中,这样才能确保得到解。再就是要找到一种有效方法,判别一个候选是不是真正的解,以保证不会漏掉所需的解。一般而言,筛选出的可能是一组对象(一组解)。合用的筛选函数就是一个做判断的谓词。下面通过例子说明其中的情况。

假设现在希望做出一个函数,求出任一浮点数(参数)的立方根。根据计算机的特点,我们只能期望找到一个接近参数立方根的浮点数。具体怎样“接近”要看问题的需要,例如,要求得到的结果的立方与原数之差不超过0.001。

解决这个问题的一种简单想法是采用生成和筛选的一种特例,枚举和检查:选择一系列数值做试验,从中选出一个满足需要的值,作为立方根的近似值。

下面的第一个问题是被检查的数值怎么选。最方便的方法是用一个循环,生成一组等距的浮点数。如果试验的数值足够密集,就可能得到足够好的解。至于筛选,自然是用有关数值的立方与原数比较,根据误差筛选出满足要求的解。

我们首先考虑按照0.001步长做试验。写出的函数定义如下:

def cbrt(x):
    x = float(x)  # 能转换也说明 x 是合理的参数
    sign = -1 if x < 0.0 else 1
    x = abs(x)
    test, root = 0.0, 0.0
    
    while test**3 <= x:
        if abs(test**3 - x) < abs(root**3 - x):
            root = test
        test += 0.0001
        
    return sign * root

这里把负数的求根也归结到正数,统一处理,为此,函数开始时用一个条件表达式提取出x的符号,再求出x的绝对值用于后续计算。

现在可以做试验,检查这个函数的功能。不难看到:采用一定的步长检查,未必能保证对所有数值找到满足要求的根,对较大的数都找不到,而且误差越来越大。例如:

>>> cbrt(2)**3
1.9956169789998675
>>> cbrt(20)**3
19.990770343995848
>>> cbrt(200)**3
199.9963601920295
>>> cbrt(2000)**3
1999.899757798265

反思这里的计算方法,可以看到一些问题:采用固定步长的一系列数自做试验,固定了解的小数点之后的有效位数。立方根的值随着参数而单调增长,而随着试验的数变大,前后两个数的立方之差也会变得越来越大。要想对较大的数值(例如200)得到满足要求的立方根近似值,就需要缩短步长(例如从0.001改为0.0001)。但是这种方法不能解决问题,对于更大的数,步长可能仍然不够小。另一方面,参数变大,缩小步长,都会导致函数里的循环做更多次迭代,使计算时间变得更长。这些讨论说明,将枚举和检查以上面方式应用于求立方根,不太合适。当然,这并不说明枚举和检查方法不好,只是使用不当。

现在考虑另一种采用逐步逼近方式的数值计算方法:取一个包含解(立方根)的区间,在工作中的每一步设法缩小区间的范围,而且保证所需的解仍在区间里。这样不断做下去,到区间足够小的时候,就可以用区间中点作为解的近似值。

不难看到,这也是一种通用方法,计算立方根只是它的一个具体应用。要实现这种方法,也需要解决几个问题:初始区间如何选择?用什么方法缩小区间的范围?实际上,任何能保证不丢掉解的方法都可以考虑。下面考虑一种方法:每一步将原区间二分(称为二分法),从中选出合适的半区间(包含解的半区间)。我们知道,“一尺之棰,日取其半,万世不绝”。但另一方面,反复折半,可以把区间变得任意短,因此可以得到任意精度的解。

相应的函数定义:

def cbrt(x):
    y = abs(x)
    a, b = 0.0, y
    while True:
        m = (a + b)/2
        if abs(m**3 - y) < 0.001:
            return -m if x < 0.0 else m
        if m**3 > y:
            b = m
        else:
            a = m

这里用变量a和b界定考虑的区间范围,先设定初始区间,然后进入一段重复计算,不断缩小区间的范围。上面函数里的循环用True作为条件,说明这个循环不通过头部的条件检查而退出,这里用条件下的return语句结束循环,条件是m的立方根值与参数之差满足我们的需要,其中m的值是区间的中点。如果m不满足需要,就根据其值的情况决定半区的选择,为此只需要修改a或者b的值。然后反复。

不难确认,前一方法的缺点现在已经解决了:

>>> cbrt(200.0)**3
199.9990560136106
>>> cbrt(20000.0)**3
20000.000561170757

似乎问题都解决了。但是,其实这个程序有错,对一些参数不能给出正确的结果。

实际上,如果参数x的绝对值小于1,其绝对值的立方根将不在 [0, y] 的范围内。对这样的参数调用上述函数,将会出现什么情况呢?请读者首先通过分析给出一个判断,而后在计算机上做些试验,看看自己的分析对不对。

纠正错误的方法很简单,只需要修改a和b的初始化语句:

    if y >= 1:
        a, b = 1.0, y
    else:
        a, b = y, 1.0

读者还可以进一步试验,考察这个函数逼近解的速度。例如对不同的数,函数里的循环需要做多少次迭代。对于不同的精度要求呢?还可以做些理论分析。

专用方法

通用方法具有较广泛的适用性,但解决问题的效率相对较低。针对要解决的具体问题,通过研究,也可能开发出一些针对具体问题的专用方法。

对于求立方根,人们给出了一个逼近公式:

image

并证明了,从任何一个非0初始值x0开始,按这个公式递推得到的无穷序列,其极限就是x的立方根。也就是说,序列中的值将能任意接近实际的立方根。

根据这个公式,可以定义出下面函数,其中采用前面提出的结束条件:

def cbrt(x):
    if x == 0.0:
        return 0.0
    x1 = x
    while True:
        x1 = (2.0 * x1 + x / x1 / x1) / 3
        if abs(x1**3 - x) < 0.001:
            return x1

这个函数不需要检查参数正负,但需要把0作为特殊情况专门处理。

我们说,一般而言,专用的方法比通用方法效率更高。上面两个函数(前一个是二分法逼近)以完全不同的方式解决同一个问题,可以用它们做些试验。对这两个简单函数,一个合理的评价标准是循环执行的次数,它反映了在计算过程中变量逼近最终结果的速度。为了考察循环的执行次数,只需要在函数里增加一个计数变量,在适当的时候输出该变量的值。这个工作非常简单,请读者自己完成。

在结束本节之前,这里还想介绍在逼近计算中经常提到的两个概念。在前面两个函数的定义中,我们都要求结果的立方根值与原参数之差不超过一个固定的数,这样的允许误差值称为绝对误差,因为这种判断依据(判据)是直接给定的,与实际计算的情况无关。在一些情况下,采用这种判据是合理的。但在另一些情况下,这种判据就不太合理了。以求立方根为例,如果参数是20000.0,结果的误差不超过0.001应该可以满足通常的需要了。但如果求0.00001的立方根,误差0.001的结果完全是没有意义的。

为解决这个问题,人们提出了相对误差的概念,也就是说,要求基于计算中处理的数据考虑允许误差。对于求立方根,可以考虑用下面判据:
image

这样,对任何实际参数,得到的结果都能比较合理。这里写0.001只是示例,很容易修改为所需的其他值。实际中人们也经常采用逼近序列中的前后两个值之差作为结束的判据,因为如果一步移动的距离很短,估计距离目标也不太远了。例如要求达到
image

基于这种误差判断,可以写出下面的函数定义:

def cbrt(x):
    if x == 0.0:
        return 0.0
    x1 = x
    while True:
        x2 = (2.0 * x1 + x / x1 / x1) / 3
        if abs((x2 - x1) / x1) < 0.001:
            return x2        
        x1 = x2

注意,由于结束判断牵涉到前后两个近似值,这里用了两个变量,其中x2保存最新求出的近似值,x1保存前一个近似值。在确定了x2还不够好的时候,就把它的值交给x1,以便继续工作下去。这是一种亦步亦趋的递推。下面是两个例子:

>>> cbrt(200.0)**3
200.00001782197174
>>> cbrt(0.01)**3
0.010000000022781627

从这两个算例中可以看到,对较大和较小的参数,函数给出的结果都比较合理。

上面求立方根的方法也是牛顿迭代法,有关情况后面还有介绍。这种方法由著名科学家牛顿提出,其收敛性有理论的保证。

一般而言,通用方法可能用于解决许多不同的问题,而专用方法只能用于解决特定的问题。从效率看,专用方法通常效率较高。如果需要解决一个具体问题,但一时找不到专用的特殊算法,也可以考虑通用的方法。由于计算机长于做反复操作,可以在很短时间里做很多尝试,因此,在许多情况下,某种通用方法也就足够了。

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享: