USING INDUCTION TO DESIGN 使用归纳法设计算法 [1/14]

在数学定理证明和计算机算法设计之间采用类比的思想能够为算法设计提供一个极好的方法，通过解释这种做法来了解这种关键思想，从而对此有更深的理解。

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

数学归纳法是一个非常强大的证明方法。使用如下：让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个数的操作（当然这并不是唯一的排序方法，也不是唯一一种使用归纳法进行排序的方法）。

上面介绍的使用归纳法的例子很直观，然后有许多不同的方法来使用归纳法，由此带来了不同的算法设计技巧。

最后

以上就是成就魔镜为你收集整理的USING INDUCTION TO DESIGN 使用归纳法设计算法 [1/14]的全部内容，希望文章能够帮你解决USING INDUCTION TO DESIGN 使用归纳法设计算法 [1/14]所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。