这篇文章在进行组合算法设计和教学过程中展示了一种基于数学归纳法的方法，尽管这种方法并不能涵盖设计算法时的所有可能方法，但它包含了大部分已知的技术方法。同时这种方法也提供了一个极好的并且也是直观的结构，从而在解释算法设计的时候显得更有深度。这种方法的核心是通过对数学定理证明过程中和设计组合算法过程中的两种智力过程进行类比。尽管我们承认这两种过程是为不同的目的服务的并且取得的是不同类型的结果，但是这两者要比看上去的更加相似。这种说法可以通过一系列的算法例子得到验证，在这些算法中都可以采用这种方法进行设计和解释。我们相信通过学习这种方法，学生能够对算法产生更多的热情，也能更深入更好的理解算法。

数学归纳法是一个非常强大的证明方法。使用如下：让T是一个我们想证明的定理。假设T包含一个值可为任意自然数的参数n。我们不需要直接证明T对所有的n都成立，我们只需要证明以下两点：（1）T对n=1时成立 （2）对于任意的n>1，T对于n-1成立。第一点往往很容易证明，证明第二点在很多情况下要比直接证明定理要容易，因为此时我们可以假设T对n-1已经成立。（从某种意义上来说，我们无条件的获得这一假设）。换句话说，减小定理的规模使用一个更小的n值而不是从头开始证明是很有帮助的，我们关注的就是这种减小。

这一原则对于算法同样也适用。归纳法让人们关注于从较小的子问题延伸到那些更大的问题上。可以通过从问题的任意一个实例入手，通过假设规模较小的相同问题已经得到解决，然后再试图解决该问题。例如，给定一个n（n>1）的序列对其进行排序（排序一个序列显然没必要），我们可以假定已经知道如何对n-1个数进行排序。然后我们可以要么排序前n-1个数，然后把第n个数插入到正确位置（这引出了一个叫插入排序的算法），要么一开始把第n个数放在它的最终位置然后再排序剩下的数（这引出了一个叫选择排序的算法）。我们只需要解决对第n个数的操作（当然这并不是唯一的排序方法，也不是唯一一种使用归纳法进行排序的方法）。

上面介绍的使用归纳法的例子很直观，然后有许多不同的方法来使用归纳法，由此带来了不同的算法设计技巧。这是一个非常强大和灵活的方法。我们将证明，在使用这种想法时很多问题变得很简单，这一点会让你惊讶不已。我们将采用其中的几种方法，并显示它们在设计算法时的强大力量。在我们讨论的归纳法的各种变形方法中，我们主要讨论巧妙的选择归纳序列，增强归纳假设，更强的归纳法以及最大的反例四种方法。

我们的处理方法有两种新奇之处。首先我们把看上去不同的算法设计技术归到同一个类别下，这将使得对一个新算法的查找更有条理性。其次，我们利用已知的数学证明技巧来设计算法，这一点很重要，因为它开启了利用在别的学科多年发展过程中形成的强大的技术进行算法设计的时代。

一般而言，在算法领域使用归纳法和数学证明技巧并不是第一次见到。归纳法在证明算法正确性上已经使用了很长时间，人们通过把对算法执行步骤的断言，证明它们在最初情况下成立和它们在特定操作步骤下保持不变结合起来，从而验证算法的正确性。这种方法最初由哥特斯和冯诺依曼提出的，后来由弗洛伊德和其他人对其进一步发展。Dijkstra和格里斯提出了一种和我们开发程序相似的方法，同时他们也给出了对其正确性的证明。尽管在此我们借鉴了他们的一些技术，但我们的重点却不同：我们关注于高层次的算法理念而不必下降到实际的程序层面。PRL和NuPRL（这里不会翻译，建议看http://www.cs.cornell.edu/info/projects/nuprl/book/node2.html）使用数学证明作为一个程序开发系统的基本构成。当然递归也被广泛用于算法设计之中（对于递归的详细讨论请看…）

我们的目标主要是用于教学，我们假设读者对数学归纳法和基本的数据结构已经很熟悉。对于任意一种证明技巧我们会对其类比进行一个简要的解释，然后给出一个或多个算法例子。对于给出的算法例子我们重点关注于如何使用这种方法。我们的目的不是在于对一个算法进行解释从而帮助一个程序员更容易地将其转换为程序，而是通过一种更容易理解的方式对其进行解释。这些算法通过一种创造性的过程加以解释而不是以一种成品的方式出现。我们教算法的目标不仅仅是向学生展示如何解决当前特定的问题，同时也是帮助他们解决未来新的问题。教学生如何把想法融入到算法设计中和教学生解决方案的实现细节同样重要。但前者通常要更难一些。我们相信我们的方法能够加强对这种思维过程的理解。

尽管归纳法建议通过递归加以实现，但也未必如此。（事实上我们称这种方法为归纳而不是递归，从而淡化递归实现的概念）在很多情况下，迭代也很容易，甚至尽管在算法设计中我们心里想的是使用归纳法（递归），但迭代却更有效率。

本文中提到的这些算法是经过筛选的，以便能更好的展现这种方法的魅力。我们选择的是一些简单的问题，在后续部分选择一些更复杂的例子。我们发现很多固定的算法在算法设计课上第一次教授时可以使用这种方法。（使用这种方法的算法导论书很快就要出来了）我们首先从三个简单的例子入手，（至少使用归纳法让他们看上去简单了）然后我们展示一些数学证明技巧以及它们在算法设计中类似的技巧，在每种情况下这种类比都在一个或多个例子中得到了阐明。

问题：给定一个实数序列an,an-1,…a1,a0和一个实数x，计算下面这个多项式的值

Pn(x)=anx^n+an-1x^(n-1)+…a1*x+a0

这个问题看上去并不像是一个使用归纳法求解直观例子，尽管如此，我们将证明使用归纳法能够直接带来很不错的解决方法。我们首先使用最简单几乎微不足道的方法求解，然后通过发现其中的变化，从而找到更好的解决方案。

这个问题涉及到n+2个数字。使用归纳法解决该问题的依据是对一个更小的问题进行求解。换句话说，我们尽量减小问题的规模，然后使用递归求解。（或者我们称其为归纳）第一步尝试是移除an，这将导致问题中计算的表达式变成：

Pn-1(x)=an-1x^(n-1)+an-2x^(n-2)+…+a1*x+a0

除了规模外这是一个同样的问题。因此我们可以使用下面的假设运用归纳法对其进行求解：

归纳假设：我们已经知道如何去计算一个多项式，该多项式在x处的输入项有an-1,…a1,a0（即我们知道如何计算Pn-1(x)）

我们现在可以使用这假设运用归纳法来解决该问题。首先我们需要解决最基本的情况，也就是计算a0；这是很简单的。然后我们必须表明如何通过借助规模较小的问题的解决方案（这里是Pn-1(x)的值）来解决原有问题（即计算Pn(x)）。在该例子中这是很直观的。我们仅仅需要计算x^n，乘以an然后加上Pn-1(x)即可。

在这一点上看上去使用归纳法很无聊因为它仅仅是复杂了一个简单的解决方案，上面提到的算法仅仅是按照多项式的数学方式对多项式从右到左进行计算而已。然而，我们很快就会看见这种方法的强大之处。

尽管这个算法是正确的，但其并不是高效的。它需要n+n-1+n-2+…+1=n(n+1)/2次乘法和n次加法计算。现在我们略微改变一下归纳法的使用方法，从而得到一个更好的解决方案。

改进：第一个改进之处在于我们注意到在求解过程中存在很多冗余计算：x的指数是从头开始计算的。当我们计算x^n时通过使用x^(n-1)的值能够帮我们节省很多乘法运算。这些都是在归纳法假设中通过对x^n计算的归纳得以实现的：

更强的归纳假设：我们已经知道了如何去计算多项式Pn-1(x)，同时我们也知道如何计算x^(n-1)的值。

这个归纳假设更强一些，因为它要求计算出x^(n-1)，但是它拓展起来更容易。我们在计算x^n时仅仅需要进行一步乘法操作，然后在进行一步乘法操作得到an*x^n，然后进行一步加法操作完成整个计算。（其实这个假设并不是太强，因为我们还是需要计算x^(n-1)的值）。总而言之，这里需要进行2n次乘法和n次加法。尽管这个归纳假设需要更多的计算，但总的说来它减少了工作量。我们在后面再来讨论这一点。在各种层面上看来这个算法很好，它高效，简单也容易实现。然而存在一个更好的算法，它是通过用一种不同的方式使用归纳法得以实现的。

我们通过移去最后一个系数an来简化问题。（这是一个很直截了当的做法）但是我们也可以移去第一个系数a0。这个规模更小的问题变成了计算由an,an-1…a1这些系数组成的多项式，如下所示：

P’n-1(x)=anx^(n-1)+an-1x^(n-2)…+a1

（注意到an现在是n-1次的系数，后面依次改变）

新的归纳假设（倒序）：我们知道如何去计算由系数an,an-1…a1构成的x多项式（即上面列出来的P’n-1(x)）

由于这个假设更容易拓展，故其更符合我们的目的。很明显Pn(x)=x*P’n-1(x)+a0。因此这里仅仅只要一次乘法和一次加法就可以通过P’n-1(x)计算得出Pn(x)。完整的算法可以通过下面这个表达式加以描述：

anx^n+an-1x^(n-1)+…+a1x+a0=((…((anx+an-1)x+an-2)…)x+a1)x+a0

这个算法被称为霍纳归纳以W.G.Horner命名。（这也是牛顿提出来的）。下面给出了计算多项式的算法。

计算表达式算法

(a0,a1,a2…an,x:real); //输入a0至an,x,全为实数

begin

** P:=an;**

** for i:=1 to n do**

** P:=x*P+an-i;**

end;

复杂度：这个算法仅仅需要n次乘法,n次加法以及一个额外的内存空间。尽管原先的解决方法看上去简单并且高效，但追求一个更好的算法是值得的。这个算法不仅仅是速度更快，同时相应的程序也更简单。

总结：上面给出的简单例子阐明了归纳法使用过程中的灵活性。霍纳规则的技巧仅在于考虑到输入是从左向右的，而不是直观上看到的从右向左。

当然这里有使用归纳法的许多其他潜在性，我们将在更多的例子中看到这一点

f是一个把有限集合A映射到其自身的函数。（例如A中的每一个元素都映射到A中的另一个元素）为了简化起见，我们把A中的元素表示为从1到n的数字。我们假定函数f以一个数组f1..n的形式出现，这样fi存放的是f(i)的值。（该值是一个位于1到n之间的整数）当A中的每一个元素都仅仅只有一个元素对应它时我们把函数f称为一一映射。函数f可以用图1中的图加以展示，在图中，两端数据都对应同一个集合，图中的边表示映射关系。（这种映射关系是从左至右的）

问题：找到一个包含最多元素的子集S(ScA)，使得函数f能够把S中的任何元素映射到S中的其他元素。(即f让S映射到自身)，同时S中的每一个元素仅仅只有唯一的一个S中的元素映射到自身。（即限制S让f成为一个一一映射）

如果f本来就是一个一一映射，那么全集A就满足了问题的条件，显然它也是最大的集合。在另一个方面来说，如果f(i)=f(j)存在且i≠j，那么集合S就不能同时包含i和j。例如在图1中S就不能同时包含2和3。不可能任意从两者中选择一个从集合中剔除出去。例如，假设我们决定删去3，由于1被映射到3，所以我们也必须删去1。（因为任意映射必须映射到S中而此时3已经不在S中了）。但是如果1被排除了，那么2也会因为同样的原因被删去。但是，这样得到的结果集不是最大的，因为我们很容易就能看到可以只删去2即可。这个问题其实是让我们去找到一种通用的方法来决定集合中包含哪些元素而已。

使用归纳法求解的思想集中在缩减问题的规模上，这种方法使用起来也很灵活。我们可以通过寻找一个要么属于S中的元素或要么不属于S中的元素来缩减问题规模。我们将在后面进行这一操作。我们先使用简洁明了的归纳假设：

归纳假设：我们已经知道如何去解决一个含n-1个元素集合的问题。

最基本的情况很简单：如果集合中只含有一个元素，集合必须映射到自身，这就是一个一一映射。假设我们已经有了一个含有n个元素的集合A，现在我们寻找一个满足问题条件的子集S。很显然找到一个不属于S集合的元素要比找到一个包含在S集合中元素简单。我们可以认为任何一个元素i如果没有被其他元素映射，那么i不可能包含在S中。（换句话说，在图右侧的元素i，如果没有一条边与之相连，那么i不可能在S中）否则的话，如果i∈S，假设S中有k个元素，那么这k个元素最多映射到k-1个元素，因此这个映射不可能时一一映射。如果存在这样的i，我们仅需要把i从集合中移除即可。我们现在有一个含有n-1个元素且让函数f映射到自身的集合A’=A-{i}。通过归纳假设我们知道如何去求解A’。如果不存在这样的i，那么映射就是一一映射，这样我们就解决了问题。

这种解法的关键在于我们必须移除i。我们在上面证明了i不可能属于S集。这是归纳法的优势之处。一旦我们移除了一个元素缩减了问题的规模我们就算完成了。然而我们必须格外小心，缩减后的问题和原问题几乎是一样的。（除了规模外）对于集合A和函数f的唯一条件就是f让A映射到自身。由于并没有元素映射到i，这个条件对于A-{i}后的集合依然成立。当没有元素可以移除的时候这个算法也就执行结束了。

实现：上面的算法是通过使用递归的过程加以描述的。在每一步中我们找到一个没有其他元素映射到它的元素，移除它，然后继续递归执行。然而实现方法并不需要用递归。我们可以对每一个元素i使用一个计数器ci。初始情况下ci需要和映射到i的元素数目相等。这可以通过扫描数组（进行n步）以及增加对应的计数器值而计算出来。然后我们把所有计数值为0的元素放在一个队列中。在每一步执行中，我们移除队列中的元素j（同时也移除集合中的对应值）。减小cf(j)的值，如果cf(j)=0，我们就把f(j)放在队列中。当队列为空时算法执行结束。算法描述如下：

映射算法（f:整型数组1..n）

begin

** S:=A{A是从1到n的数字构成的数组}**

** for j:=1 to n do cj:=0;**

** for j:=1 to n do increament(cf(j));**

** for j:=1 to n do**

** if cj=0 then put j in Queue;**

** while Queue is not empty do**

** remove i from the top of the queue;**

** S:=S-{i};**

** decrement cf(i);**

** if cf(i)=0 then put f(i) in Queue**

end;

复杂度：初始化部分需要O(n)的操作时间，每一个元素最多有一次机会被放置到队列中，把元素从队列中移除只需要常数时间。步骤的总数O(n)。

总结：在本例中减少问题的规模主要在从集合中删除元素上。因此我们试图在不改变问题条件的情况下寻找一种最简单的方法来移除元素。由于对于函数的唯一的要求是它必须把A映射到自身，故我们会很自然地选择一个没有其他元素映射到的元素。

检查线段的包含情况【Q3】

问题：输入是一条线上一系列间断线段的集合I1,I2…In。对于每一个线段Ij都给出了它的两个端点Lj（左端点）,Rj（右端点）。我们想标记出所有包含在其他线段中的线段。换句话说，一个线段Ij必须被标记出来，如果存在另一条线段Ik(k≠j)并且满足Lk≤Lj以及Rk≥Rj。为了简化起见我们假定所有的线段都是不一样的（例如任意两个线段都不可能同时具有相同的左端点和右端点，但是它们可能有两个端点中的某一个相同）。图2展示了这样的一个线段集合。（为了更好的展示，每一条线段都放在另一条线段上面而不是放在一条线上）

用直观的方法使用归纳法主要是移除一个线段I，对于剩下的线段使用递归的方法加以解决，然后在检查把I放回后的效果。问题在于把线段I放回需要检查所有其他的线段来判断他们中是否包含I或者被I所包含。这需要检查I和其余n-1条线段，算法中使用的比较将达到n-1+n-2+…+1=n(n-1)/2次。为了获得一个更好的算法我们需要做两件事：首先我们选择一条特殊的线段加以移除，其次我们尽可能多的使用从更小规模问题的解决方案中收集到的信息。

选定I为所有线段中具有最大左端点值的线段，由于其他线段左端点值都较之小，这样就不需要再检查左端点值了。因此，为了要检查I是否包含于其他线段之中，我们只需要检查其他线段中是否有右端点值比I右端点值更大的线段。为了找到这么一条具有最大左端点值的线段我们可以依据线段的左端点值对所有线段进行排序并且按照次序对其进行搜索。假定线段已经按照次序排好，L1≤L2≤…≤Ln。归纳假设如下：

归纳假设：我们已经知道如何去解决包含I1,I2…In-1条线段的问题。

最基本的问题很简单，如果只有一条线段，那么它肯定不会被标记。现在我们来考虑In。通过归纳假设我们知道已经确定了在线段I1到In-1中有哪些线段是包含在其他线段之中的，我们需要确定In是否包含其他（之前没有被标记过）的线段，以及In是否被包含在其他线段之中。让我们首先来检查In是否被包含在其他线段之中。如果In被包含在一条线段中，假如是Ij,j