《树型软件工程方法》之系列博文5

作业树设计原理

   TREESOFT

                      目  录

5 作业树设计原理. 1

5.1 结果倒推法…. 1

5.2 作业子树与问题…. 3

5.2.1 作业子树的物理意义…. 3

5.2.2 作业树的初始型态树…. 4

5.2.3 真问题型态树…. 5

5.3 问题递归处理…. 6

5.4 问题递归实例分析…. 9

5.4.1 冒泡排序问题…. 9

5.4.2 解一元二次方程问题…. 10

5.4.3 二分查找问题…. 11

5.6 结束语…. 12

中国人为什么不可以有自己的软件工程方法及其开发工具平台！

这是介绍《树型软件工程方法》的系列博文，请按文章标题所带的编号顺序阅读，否则你会看不懂本文。

5 作业树设计原理           

我们已经完成了对作业树相关概念的叙述，给出了按照问题求解算法设计作业树的方法，并且有过四个设计实例。然而，问题求解算法为什么能表示成作业树呢就涉及到作业树的设计原理，本文将对此进行讨论和分析。本文的内容很有趣，叙述也颇具艺术性。同时，本文的新概念比较多，分析求证过程也挺烦人。所以，阅读本文不仅要求熟悉作业树的相关概念，也还需要有点耐心，慢慢咀嚼评味。

5.1 结果倒推法

通常，人们在分析问题的时候总是采用反向推导的方法，即从问题应该得出的结果入手，再推导出求解问题的方法。形式地说：

在认为已经求得问题结果的假定下，推导出求得问题结果所需要满足的条件，以及在此条件控制下的可执行的操作和待求解的下级问题。分层逐级进行这样的推导，直至所得结果就是问题的解。

称问题求解的这种方法为结果倒推法。仔细分析就可以看出，这个结论中含有两层意义。通过对当前问题的结果倒推，首先获得了当前需要满足的条件和可执行的操作；同时显露出了待求解的下级问题。将待求解的下级问题作为当前问题，再进行结果倒推，分层逐级进行，最终总能求得原问题的解。可以用如下的算法来表述结果倒推法：

1) 将要被求解的问题作为当前问题。

2) 对于当前问题，先假定已经求得其结果，分析得出需要满足的条件，以及在此条件控制下的可执行的操作和待求解的下级问题。

3) 如果可执行操作所得结果就是问题的解，则原问题求解结束。否则，将待求解的下级问题作为当前问题，返回步骤(2)。

图5.1 结果倒推法的框图

图5.1是表示结果倒推法的框图。按这个框图人工求解问题是可以的，但无法将其编写成计算机程序，因为这只是求解问题的通用方法。在结果倒推法中，以“可执行操作所得出的结果就是问题的解”作为原问题求解结束的条件，这当然是合情合理的。既然问题求解已结束，当然也就没有“待求解的下级问题”。换句话说，没有“待求解的下级问题”等价于“可执行操作所得出的结果就是问题的解”，没有“待求解的下级问题”也是原问题求解结束的条件。这样，我们就可以用图5.2来表示结果倒推法。

图5.2 以“没有待求解的下级问题”作为原问题求解结束条件的结果倒推法框图

结果倒推法是具公理性的问题求解方法，是人们求解问题的通用方法，适用于任何问题的求解。我们将会看到，作业树的设计正是采用了这种方法。显然，采用结果倒推法编写出的程序自然贯彻了结果倒推的方法，运行相应程序也就相当于采用了结果倒推法求解问题。

      图5.3 用结果倒推法编程的框图

对于具体问题，我们更关心的是每一次结果倒推所获得的“需要满足的条件”的具体表示。至于是否还有“待求解的下级问题”并不重要，有就继续进行结果倒推，没有就结束求解，这是顺理成章的事。所以，我们只需要连续不断地完成每一次的结果倒推，最终总会出现只有“可执行的操作”没有“待求解的下级问题”的情形。现在，我们将“可执行的操作”和“待求解的下级问题”合并成一框” ，这样做并没有改变结果倒推法的原意。一方面，它们都是在“需要满足的条件” 的控制下；另一方面，可执行的操作是已知的，下级问题是待求解的，它们形式上的合并并不会混淆实质上的分离。如此就形成了图5.3的框图，称为用结果倒推法编程的框图，其各部分的意义如下。

1) 上部端园框为“结果倒推”框，借用了作业树控制节点的表示形式。其中：注释指明本框的功能是“结果倒推当前问题”；“上级控制下的可执行操作”是从当前问题分离出来的，但它并不受本框“需要满足的条件”的控制，而是受上一级“需要满足的条件”的控制；“需要满足的条件”是对当前问题结果倒推产生的，“Ct”即为其控制类型。显然，按照前面对作业树控制节点的定义，这一框的内容可以被编写成程序。

2) 左部梯形框为“下级问题”框。它含有对当前问题结果倒推所产生的“可执行操作”和“下级问题”。即本框的这两项内容和上部框中的“需要满足的条件”，都是对当前问题结果倒推所产生的。根据结果倒推法，本框的这两项内容应受控于“需要满足的条件”，编写出的程序也同样满足这个原则。由此也可以看出，上部框中的“上级控下的可执行操作”与本框的“可执行操作”是不同的。前者是属于当前问题之前的父问题的，后者则是属于当前问题的。

3) 右部矩形框为“结束语句”框。可以想象，在连续进行结果倒推的过程中，最终总会出现没有“待求解的下级问题”的情况，意味着原问题的求解已经结束，应该编写“结束语句”作为结果倒推法程序的出口。

将图5.2与图5.3比较就可看出，虽然形式上有些差异，但它们实质意义是相同的，都是采用结果倒推法求解问题。它们之间的主要差异是图5.3中没有“还有待求解的下级问题吗询问框，相应功能的实现已经在上面的第3点中做了说明。此外，图5.3中省去了“将原问题作为当前问题”，是为了显目地看出结果倒推法编程的主要功能框。再说人工采用结果倒推法编程自然是从原问题开始，省去这一框并不会产生歧义。剩下其它各部分的意义都是相同的，区别仅在于“直接求解问题”和“编程求解问题”。

5.2 作业子树与问题

为了探讨作业树的设计原理，就必须把作业树同所求解的问题相关联，进而说明结果倒推法在作业树设计中的应用。为此，我们先要定义几个重要概念：源问题、原问题和真问题，这些概念都直接与相应作业子树相对应。然后，有针对性地规范出真问题型态树，它将是我们研究的主要作业子树。

5.2.1 作业子树的物理意义

(1) 源问题。

凡可以求解出结果的问题都称为源问题，缩写为Sq(Sourse question)。我们是运用作业树来求解问题的，凡被求解的问题都要将其求解算法设计成作业子树。这里说是作业子树，即不仅仅是完整的作业树，还包括采用结果倒推法设计作业树的过程中的所有作业子树。换句话说，任一棵作业子树都求解一个Sq。所以说，可以求解出结果的待求解问题都是Sq，按问题求解算法设计出的作业树所求解的问题也是Sq。

(2) 原问题。

作业树所求解的Sq称为原问题，缩写为Oq(Original question)。显然，在作业树的范围内，Oq是最大范畴的Sq。

(3) 真问题。

作业节点及其左子树所组成的作业子树所求解的问题称为真问题，缩写为Tq(True question)。这里Tq的定义中没有涉及控制节点的右子树和中子树，因为它们都不参与Tq的求解，这在后面的讨论中会有论述。显然，作业树中任何节点都是相应Sq的根节点，同时也是Tq的根节点，剪去Sq的右子树和中子树后就得到了同根的Tq。

这里将Oq、Sq和Tq都以作业子树来定义，并非多此一举。将作业子树同所求解的问题相关联，使得其物理意义更明确。后面将会看到，Oq、Sq和Tq的定义，对于揭示作业树的设计原理至关重要。为了叙述的方便，我们经常会直接以Oq、Sq或Tq来代表相应的作业子树，并将相应作业子树的根节点说成是它们的根节点，这应该不会被误会。

5.2.2 作业树的初始型态树

根据作业树的定义，作业树的延伸设计是从起始节点开始的，我们将在博文《冒泡排序程序的结构化设计》中定义的图1.6的作业树初始型态树重画于图5.4。

图5.4 作业树的初始型态树

如前所述，作业树初始型态树由三部分组成：起始节点、问题求解子树和结束节点。初始型态树的结构十分简单，但却体现了结果倒推法用于作业树设计。与图1.6相比略有不同，图5.4中将左支的“受控程序段”分为“可执行操作”和“待求解的下级Sq”两部分。这里，“可执行操作”就是对Oq结果倒推所产生的已知的操作。

确立初始型态树是设计作业树的第一步，这一步设计出了作业树的起始节点和结束节点，以及在起始节点控制下的可执行操作。待求解的下级Sq中的所有节点则有待于下一步的设计。那么，我们是依据什么设计出起始节点和结束节点的呢是结果倒推法。

作业树初始型态树的设计原理是：在假定可以求得Oq结果的前提下，确立作业树的起始节点和结束节点，以及在起始节点控制下的可执行操作和待求解的下级Sq。

显然，上述结论是结果倒推法用于设计作业树的第一步。所谓“确立起始节点和结束节点”，实际就是画出初始型态树，这是公式化的简单设计。但“在假定可以求得Oq结果的前提下”却隐含了结果倒推法的意义，其是构造初始型态树这一步所要满足的条件。仅当认为问题是可解的，才有必要去设计作业树，确立作业树的起始节点；仅当认为问题求解是可行的，才能导出可执行操作和下级Sq；仅当认为可以求得问题的结果，才能确定运行完起始节点的左子树后就可结束作业树的运行，确立起始节点的右儿子为结束节点。

设计作业

来源：chuilequan2482