馆陶企业微信公众号小程序开发公司、馆陶企业网页设计方案、馆陶做网站开发价格、馆陶微信公众号制作运营报价明细表、馆陶网站设计公司费用、馆陶网站推广大概需要多少钱

馆陶企业微信公众号小程序开发公司、馆陶企业网页设计方案、馆陶做网站开发价格、馆陶微信公众号制作运营报价明细表、馆陶网站设计公司费用、馆陶网站推广大概需要多少钱

馆陶县，河北省邯郸市下辖县 [1]  ，地处河北省东南部，以卫运河为界与山东省冠县、临清市毗邻。全县辖4镇4乡277个行政村，总面积456平方公里，其中耕地面积48万亩，总人口36万人。馆陶是千年古县，赵王“在城（今冠县东古城）西北七里陶丘侧置馆，故名馆陶”，自西汉初置县，已有2200多年历史。

馆陶县先后荣获中国蛋鸡之乡、中国黑陶艺术之乡 、中国粮画之乡、中国轻工轴承之乡、中国黄瓜之乡、中国漆画艺术之乡、全国休闲农业和乡村旅游示范县、全国电子商务进农村示范县、全国义务教育发展基本均衡县、全国中医工作先进县、全国群众体育工作先进县等等30余项国家级殊荣。

近年来，馆陶县着力打造了五张名片。一是“最大”，禽蛋交易市场金凤市场，单体全国最大，鸡蛋远销广东、广西等地，2016年交易额达到110亿元；二是“最优”，馆陶是中国著名的黑陶艺术之乡，现代黑陶艺术经过馆陶人的继承和创新，达1000多个品种；三是“最好”，馆陶是中国唯一的黄瓜之乡，馆青牌黄瓜，连续四年荣获中国绿色博览会金奖；四是“最佳”，馆陶有独一无二的富含三价有机铬的黑小麦，可应用于抑制血糖和抗肿瘤等医学领域；五是“最美”，粮画小镇被评为“中国十大最美乡村”，即将由3A级景区升级成为国家4A级旅游景区。 [2-6] 

2020年4月，被河北省体育局评选为“2019年度体育工作最佳县（市、区）”。

示例 5.18

现在来考虑一下图5-22中的computeHt函数，图5-26重现了该函数的函数体。该函数接受（指向）节点n（的指针）作为参数，并计算n 的高度。我们将通过结构归纳法证明以下命题。

(1)        n->height = 0;(2)        c = n->leftmostChild;(3)        while (c != NULL) {(4)            computeHt(c);(5)            if (c->height >= n->height)(6)                n->height = 1+c->height;(7)            c = c->rightSibling;
           }复制代码

图 5-26　图5-22中computeHt(n)函数的函数体

命题S(T )。在对指向树T 根节点的指针调用computeHt时，T 中每个节点的正确高度都会被存储在该节点的height字段中。

依据。如果树T 只有一个节点n，那么在图5-26中的第(2)行，c 会被赋上NULL值，因为n 没有子节点。因此，第(3)行的测试会立即失败，而且while循环的循环体永远都不会执行。因为第(1)行会将n->height置为0（这对叶子节点而言是正确的值），所以可以得出结论，当T 只有一个节点时S(T )成立。

归纳。现在假设n 是有多个节点的树T 的根节点，那么n 至少有一个子节点。我们可以在归纳假设中假定，在第(4)行调用computeHt(c)时，以c 为根节点的子树中每个节点（包括c 本身）的height字段中都被装入了正确的高度。现在需要证明，第(3)行到第(7)行的while循环可以正确地将n->height置为比n 的子节点的最大高度大1。要做到这一点，就需要执行另一次归纳，这是嵌套在该结构归纳法证明过程中的，就像是程序中循环嵌套在另一个循环中那样。该归纳使用的是“普通的”归纳法而不是结构归纳法，它的命题如下。

命题S' (i )。在第(3)到第(7)行的循环执行i 次之后，n->height的值要比n 前i 个子节点的最大高度大1。

依据。依据是i=1的情况。因为n->height在循环外——第(1)行——会被置为0，并且肯定不会有比0还小的高度，所以第(5)行的测试会得到满足。第(6)行就会将n->height置为比n 的第一个子节点的高度大1。

归纳。假设S' (i )为真。也就是说，在循环的迭代i 次之后，n->height会比前i 个子节点的最大高度大1。如果有第i+1个子节点，那么第(3)行的测试会成功，而且会第i+1次执行循环体。第(5)行的测试会将新的高度与之前的最大高度相比较。如果新高度c->height比前i 个高度中最大值加1要小，就不用对n->height进行任何改变。这是对的，因为前i+1个子节点的最大高度是可以与前i 个子节点的最大高度相同的。不过，如果新的高度比之前的最大值大，第(5)行的测试就会成功，这样n->height就会被置为比第i+1个子节点的高度大1，这是正确的。

现在可以回到结构归纳了。当第(3)行的测试失败时，就已经考虑过n 的所有子节点了。内层的归纳S' (i )说明，当子节点的总数为i 时，n->height要比n 各子节点的最大高度大1。这就是n 的正确高度。将归纳假设S 应用于n 的各子节点，就得到结论：正确的高度已经存储到每个子节点的height字段中。因为已经得知n 的高度也已经正确地计算出来，所以可以得出结论：T 中所有节点都被赋上了它们正确的高度值。

现在已经完成了结构归纳法的归纳步骤，并得出结论：对每棵树调用computeHt都可以正确地计算树中每个节点的高度。

结构归纳法的模板

下面简述了进行正确的结构归纳法证明的过程。

1. 指定要证明的命题S(T )，其中T 是一棵树。

2. 证明依据，也就是只要T 是一棵单节点的树，S(T )就为真。

3. 建立归纳步骤，设T 是以r 为根节点的树，而且有k≥1棵子树，分别为T1、T2、…、Tk。表示假定有归纳假设，即S(Ti )对每棵子树Ti（i=1、2、…、k）都为真。

4. 证明在(3)中提到的假设下S(T )为真。

5.5.1　结构归纳法为何有效

要说明结构归纳法为何是一种有效的证明方法，其原因与普通归纳法有效的原因类似：如果结论为假，那么就会有个最小的反例，而且该反例既有可能违背依据，也可能违背归纳过程。也就是说，假设有命题S(T )，已经证明了它的依据和结构归纳步骤，而存在一棵树或多棵树可以让S 为假。设T0是可以让S(T0)为假的这样一棵树，并设T0与让S 为假的任一棵树的节点一样少。

有两种情况。第一种，假设T0由单个节点组成。那么根据依据，有S(T0)为真，所以这种情况不可能发生。

现在就只剩下T0有多个节点的情况了，这里假设T0有m个节点，那么T0就是由根节点r 与一个或多个子节点构成。设以这些子节点为根的树分别是T1、T2、…、Tk 。这里可以声明T1、T2、…、Tk 的节点数均不超过m-1。因为如果某棵树（假如是Ti）的节点数达到或超过m，那么由Ti（可能还有其他子树）和根节点r 组成的T0就至少会有m+1个节点。这与T0刚好有m 个节点的假设是矛盾的。

因为T1、T2、…、Tk 这些子树的节点数都不超过m-1，所以就可以知道这些树都不能违背S，因为选择了T0是让S为假的最小子树。因此可知S(T1)、S(T2)、…、S(Tk)都为真。而假设已经得到证明的归纳步骤说明了S(T0)也为真，这样又与T0违背S 的假设产生了矛盾。

在考虑完这两种可能的情况后，我们就知道：不管一棵树只有一个节点还是有多个节点，T0都不可能是S 的例外。因为S 是没有例外的，所以S(T )一定对所有的树T 都为真。

5.5.2　习题

1. 通过结构归纳法证明：

(a) 图5-15的前序遍历函数会以前序打印出树的标号；

(b) 图5-17中的后序函数会以后序列出标号。

2. * 假设分支系数为b 的单词查找树是用具有图5-6中所示格式的节点表示的。用结构归纳法证明：如果树T 有n 个节点，那么它的节点中有1+(b-1)n 个NULL指针。那么，共有多少非NULL指针？

3. * 节点的度是指节点所具有的子节点的数目。2用结构归纳法证明：在任意树T 中，节点的数目都要比节点的度之和大1。

2分支系数和度是相关的概念，但它们是不同的，分支系数是树中各节点度的最大值。

4. * 用结构归纳法证明：在任意树T 中，叶子节点的数目都要比具有右兄弟节点的节点的数目大1。

5. * 用结构归纳法证明：在任意用最左子节点右兄弟节点的数据结构表示的树T 中，NULL指针的数目都要比节点的数目大1。

6. * 在5.2节开始的部分，我们给出了树的递归定义和非递归定义。使用结构归纳法证明：每棵以递归方式定义的树在非递归定义下也是同样的树。

7. ** 证明习题(6)的逆命题：每棵以非递归方式定义的树在以递归方式定义时也是相同的树。

树的归纳的谬误形式

我们常常会想着对树的节点数进行归纳，就是假设命题对具有n 个节点的树成立，并证明它对具有n+1个节点的树也成立。如果不够谨慎，就很可能作出这种荒谬的证明。

在第2章中对整数进行归纳证明时，我们提出了一种合理的方法，就是试着用S(n)证明命题S(n+1)，并称这种方法为“后靠”。有时候有人可能把这一过程看作从S(n)开始并证明S(n+1)，称这种方法为“前推”。在整数的情况下，这基本上是相同的意思。不过，对树而言，我们不能先假设命题对具有n 个节点的树成立，并在某个位置加上一个节点，然后就说证明了结果对所有具有n+1个节点的树都成立。

例如，声明S(n)：“所有具有n 个节点的树都有一条长度为n-1的路径。”n=1的依据情况显然为真。在错误的“归纳”中，可能会作出如下论证：“假设有一棵具有n 个节点的树T，它有一条长n-1的路径，假如说是到节点v 的。给v 加上子节点u。现在就有了一棵具有n+1个节点的树，而且它有一条长度为n 的路径，这样就证明了归纳步骤。”

当然，上述论证是谬误的，因为它没有证明结果对所有具有n+1个节点的树都为真，而只是证明了对选出的一些树为真。正确的证明不能是从n个节点“前推”到n+1个节点，因为我们不会从这一过程得出所有可能的树。我们必须从任意具有n+1个节点的树开始“后靠”，小心地选出一个节点，并将其删除，从而得到一棵具有n个节点的树。

馆陶企业微信公众号小程序开发公司、馆陶企业网页设计方案、馆陶做网站开发价格、馆陶微信公众号制作运营报价明细表、馆陶网站设计公司费用、馆陶网站推广大概需要多少钱