《从问题到程序:用Python学编程和计算》——3.3 程序终止性-阿里云开发者社区

开发者社区> 华章计算机> 正文

《从问题到程序:用Python学编程和计算》——3.3 程序终止性

简介:
+关注继续查看

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

3.3 程序终止性

本节讨论一个与循环和递归有关的重要问题:程序的终止性。一个程序的执行是否一定结束,这是一个很重要的问题。例如程序对所有可能的输入是否都能结束(终止),或者函数对所有的参数是否都能终止并给出结果。如果一个程序对于某些输入(或一个函数对于某些参数)不终止,遇到这些输入或参数,程序就会无穷无尽地运行下去,既不给出结果,也不报告运行错误。这种情况通常也不符合用户的需要。在很多实际应用中,这种情况是绝对不能允许的。请考虑一部汽车的刹车控制程序。

首先可以想到,只要程序里的每个基本语句都终止,直线型和分支型程序就必然终止。但循环程序的情况则不同,即使循环体中的语句保证终止,这个循环也可能不终止。如果在一个while循环的执行中,循环体里语句的执行不能把循环条件变为假,这个循环就会无休止地继续下去,循环之后的语句永远也得不到执行的机会。递归函数(递归程序)也存在类似的问题,它也可能无穷无尽地递归调用下去。[ 这里没考虑Python解释器对递归深度的默认限制。这种限制是强行终止程序,但结果毫无保证。]

但另一方面,有些程序可能确实需要运行很长时间,等了很久也没有得到结果,并不一定说明这个程序不能结束。

3.3.1 调和级数的部分和

看一个例子:由数学知识可知,下面调和级数的部分和增长非常慢:

image

现在希望了解这个部分和的增长情况,考察该级数的前多少项之和能超过某个给定的数。可以定义下面的函数:

def harmony(num):
    s = 0
    n = 0
    while s < num:
        n += 1
        s += 1/n
    return n

用一些参数值做试验:

print(harmony(5))
print(harmony(10))
print(harmony(15))
print(harmony(20))

可以看到,程序输出3个结果后很长时间都没有进一步的动静。在这种情况下,我们没有办法判定究竟是程序出了问题,永远不会结束,还是过一会就能得到结果。为了了解程序运行的情况,可以考虑在循环里加一个输出信息的语句:

        if n % 1000000 == 0:
            print(s)

这个语句要求每一百万次循环输出一次部分和。在执行harmony(20)时,可以看到输出的值慢慢地增长。只要等的时间足够长就能得到结果。但如果调用harmony(25),考虑到浮点数的计算误差等,我们还能得到结果吗?请读者考虑这个问题。

3.3.2 程序终止性不可判定

有关程序的终止性问题,被人们称为计算机之父的英国数学家图灵给出了一个理论结论(1934年):程序终止性问题是不可判定的。也就是说,我们不可能做出一个判断程序终止性的软件工具,使其对任何程序和程序的任何输入,都能给出该程序将终止或不终止的结论。在实际中,有时判断一个程序是否终止也很困难。看下面的简单程序。

【例】本问题称为Collatz猜想(Collatz conjecture)。德国数学家Lothar Collatz猜想下面函数对所有正整数n终止(参考http://en.wikipedia.org/wiki/Collatz_conjecture):

image

如果这个函数对所有的正整数终止,那也就是说,对于任何正整数参数,本函数的值总是1,因此它就等价于总得到1的常函数。

很容易写出Python程序实现这个函数。下面是一个循环实现:

image

人们用大量的正整数试验这个函数,发现它都终止,但至今无人能严格证明Collatz猜想是正确的(即函数collatz终止),也没人能证明这个猜想不正确,没找到能使collatz函数不终止的输入。人们通过试验发现,采用一些参数,变量n可能经历非常大的值或反复上下跳跃,但最终都能达到1,但却没有找到任何有价值的规律。

读者可以基于上面程序做一些试验,例如检查它对具体的参数迭代多少次后才能达到1,或者考察在此过程中曾经达到的最大数值等。

虽然有上面的理论结论,我们不可能做出完成终止性判断的系统(工具),但在实际工作中还是需要考虑这个问题,通过对具体程序的具体分析,设法确定自己写出的程序一定能终止。这里的基本问题就是检查程序里的循环或者递归,设法确认它们一定终止。只要迭代器给出的序列有穷,相应的for循环一定终止。对于while循环,一种常用方法是设计一个基于循环中变量的整型表达式,证明该表达式的值随着一次次迭代严格下降,但其值一定不小于某个数(例如0)。如果这样的表达式存在,该循环就一定终止。这里不再深入,有关算法的专门书籍都有这方面讨论。

重看前面的程序,其中的大多数循环的终止性都比较容易判断。另一些程序的终止性有数学上的保证,例如牛顿迭代法等。

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

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
9964 0
函数计算搭建小程序Web应用后端服务
使用Severless架构搭建移动App、小程序和Web应用后端服务,弹性伸缩使用云资源。
396 0
【转】C# 计算程序运行时间
 1 //计算程序运行时间(.net1.1 于.net2.0的区别)在.net2.0中提供了Stopwatch类,简单例子  2 using System.Diagnostics;  3  4 private Stopwatch stw = new Stopwatch();  5  6 pri...
600 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,阿里云优惠总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系.
13722 0
通过pl/sql计算程序的运行时间
在sqlplus中运行sql语句或者pl/sql的时候如果需要统计运行的时间,只需要开启set timing on选项即可。 SQL> set timing on SQL> SQL> select count(*)from cat;   COUNT(*) ----------        408 Elapsed: 00:00:00.15 如果在运行pl/sql的时候如果需要计算程序运行的时间。
618 0
10059
文章
0
问答
来源圈子
更多
+ 订阅
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载