当数学归纳法遇上递回：简介递回演算法的设计 When Mathematical Induction Meets Recursion - Introduction to the designing process of recursion algorithm (revision 2) 前言 前面已经有二位真‧强者发过递回文了，想必大家已经看懂递回在搞 什麽鬼。如果还没有看懂，就看这一篇，让你看完之後，可以对递回 有更进一步的认识；如果已经看懂的，就看这一篇，让我用数学归纳 法来搅乱你已经搞懂的观念XD！ 这一篇，不着重在递回怎麽写，或递回怎麽运作的。我把焦点集中在 如何构思一个递回演算法。希望透过这一篇，可以让大家对递回有更 深一层的认识。 数学归纳法简介 所谓的数学归纳法，应该可以算是整数五大公设之一(我不确定)，它 的内容如下： 当一个叙述满足 1. 在 n == 1 成立 2. 假定 n == k 成立时，n == k + 1 亦成立 我们就可以说此叙述在 n 为正整数的时候都会成立。其中，我们称 条件 1 为归纳基底(Induction Basis)，条件 2 为归纳假设(Induc- tion Hypothesis)。 举例来说，我们来证明 1 + 2 + 3 + .... + n == 0.5 * n * (n + 1) Pf: 1. 在 n == 1 时，显然成立。 2. 假设在 n == k 时成立 我们有 1 + 2 + 3 + ... + k == 0.5 * k * (k + 1) 我们二边同加 k + 1 1 + 2 + 3 + ... + k + (k+1) == 0.5 * k * (k + 1) + (k+1) == (k + 1) * (0.5 * k + 1) == 0.5 * (k + 1) * (k + 2) == 0.5 * (n') * (n' + 1), n' = k + 1 我们推得 n == k + 1 亦成立 3. 因为 1 2，由数学归纳法，可知适用所有 n 属於正整数，原命 题皆正确。 从这一个证明我们学到了什麽？ 1. 我们要有一个归纳基底(Induction Basis)，做为证明的源头 2. 我们假定我们在一定的范围内会证明原命题，我们也可以证明在 更大的范围原命题也是正确的，这叫归纳假设(Induction Hypo- thesis)。 3. 从 1 可以推得 2，2 可以推得 3，....，k 可以推得 k + 1， 从而你会解决题目。 递回简介 紧接着归纳法，趁大家还没有忘掉归纳法之前，我要赶快讲递回，以 方便我把二者混为一谈，让大家看到数归就会想到递回！ 所有的递回，无一例外，都必需要有二个部分，一个是终止条件，一 个是问题拆解。终止条件是用来界定我们什麽时候就不用再继续化简 问题（通常是我们已经会处理的小问题或被其他因素限制）；而问题 拆解的部分指的是我们把一个难以解决的大问题拆分为比较容易的小 问题。 来，现在我要催眠你，你相信： 归纳基底可以用来当做递回的终止条件， 归纳假设可以用来当做递回的问题拆解。 请牢牢记住！催眠结束。 接下来我们来说一下递回是什麽？递回是一个方法，我们会把一个大 问题拆解为若干个我们会解决的小问题(子问题)，我们透过整合小问 题的结果，来解决最初的大问题。 举几个例子： 「考试靠作弊」 考试很难，是一个大问题，我们可以把这一个大问题分成几个部 分来解决：努力读书、大量地做考古题、准备一个骰子、作弊。 我们可能会选努力读书，也可能大量地做考古题，也有可能在做 答的时候掷骰子来猜答案，当然...也有可能作弊(嘘)。不论如 何我们会把大问题简化成上面的小问题(子问题)，最後交出的答 案就会是上面小问题的整合。 当然，为了忠於不知道谁发明的俗谚，我们就假定我们考试的时 候有一些题目我们刚好没有读到，也没有做过类似题、掷骰子每 一次都是尖角向上(见鬼了 XD)，我们考试一定要靠作弊，请问 这是一个有效的递回关系吗？ 也许是，如果你作弊可以得到正确答案；也许不是，如果你不会 也没有能力作弊之类的。如果作弊这一个子问题可以被解决，它 就是一个有效的递回，如果子问题不能被解决，它就不是一个有 效的递回关系。 「考试靠作弊，作弊靠隔壁」 在这一步，我们的大问题由「考试」变成了「怎麽作弊」？不要 小看作弊了，作弊的方法千百种，要如何在高风险与高正确性之 间取得平衡是一个大问题(啥鬼?)。所以既然是大问题，我们就 继续化简问题。作弊的方法又有很多种，有小抄法、有通讯作弊 法、有左顾右盼法、有前後呼应法、...等等。我们把作弊这一 个大问题又化简成若干小问题(子问题)。作弊的结果就会是以上 的整合。 当然，又因为一大堆不会抗力之因素，你不能弄小抄、通讯器材 坏掉、耳朵咙了、嘴巴哑了，只能用左顾右盼法，那请问上面那 一句是用效的递回关系吗？ 也许是，也许不是。关键在隔壁的会不会写考卷，如果会这就是 一个有效的递回，如果不会，则作弊这一个子问题不能被解决， 连带考试也不能被解决，这就不会是一个有效的递回。 「考试靠作弊，作弊靠隔壁，隔壁靠墙壁」 我们一路把考试这一个大问题变成隔壁的问题。可是对隔壁来说 考试也是一个大问题呀！他不一定能弄出正确的答案。怎麽办呢？ 隔壁为了弄出答案，也把考试拆成若干小问题，大部分靠他自己 的聪明才智，有一部分实在写不出来，可是这又是拿 0 分或拿 100 分的关键，他傍惶无助的望着墙壁发呆，希望墙壁上会有提 示。 好了，上面的问题是不是有效的递回关系式呢？也许是，也许不 是。关键在於墙壁上有没有提示。如果有，则隔壁会写，作弊能 得到正确答案，我们就会写考卷，它就是一个有效的递回；如果 没有，隔壁不会写，作弊没有用，我们当然写不出来，它就不是 一个有效的递回。 「考试靠作弊，作弊靠隔壁，隔壁靠墙壁，墙壁倒下去」 像这一句很明显就不是一个有效的递回，因为墙壁倒下去，所以 墙壁上就不会有提示，进而隔壁不会写，作弊没有用，我们自己 的考卷当然写不出来，因此它就不是一个有效的递回。 回想一下我们学到了什麽？ 1. 数学归纳法感觉起来和递回很有关联 2. 递回是用来大事化小，把大问题变成我们可以解决的小问题 3. 递回一定要有一个已知的终止条件(可以是大问题的限制或我们已 经会解决的问题) 4. 考试不能靠作弊，因为墙壁会倒下去！XD 范例一 请写一段程式计算 1 + 2 + 3 + .... + n。当然，你不可以用公式。 我们要写一个函式 int sum(int n) 来计算这一个值。 解： 我们回想上面，我们的归纳步骤： 1. 在 n == 1 时，显然成立。 2. 假设在 n == k 时成立，我们可以推得 n == k + 1 亦成立 3. 因为 1 2，由数学归纳法，可知适用所有 n 属於正整数，原命 题皆正确。 因为程式语言的限制，为了让程式的撰写比较容易，我们稍微修改一 下我们的归纳假设(当然也是对的)： 1. 在 n == 1 时，显然成立。 2. 假设在 n == k - 1 >= 1 时成立，我们可以推得 n == k 亦成立 3. 因为 1 2，由数学归纳法，可知适用所有 n 属於正整数，原命 题皆正确。 所以我们可以这样想：在 n == 1 的时候，我们的 sum 的回传值很 明显：就是 1 嘛！然後，我们可以假定我们会算 n == k - 1 的值， 我们要解决 n == k 的问题，在 n == k 的时候， sum 的回传值要 等於什麽呢？因为我们知道 n == k - 1 的时候 sum 的回传值会是 前 k - 1 项的和，所以我们在 n = k 的时候，传回 sum(k - 1) + k。也就是说我们 sum 函式可以这样写： 我们的 sum 函式可以这样写： int sum(int n) { if (n == 1) { return 1; /* 这是归纳基底 */ } else { return (sum(n - 1) + n); /* sum(n - 1) 是归纳假设 */ } } 这样写到底对不对？我们可以用数学归纳法来做正确性证明： 1. 在 n == 1 的时候，sum(1) == 1 显然成立。 2. 假定在 n == k - 1 的时候，sum(k - 1) == 1 + 2 + ... + (k-1) 我们发现 sum(k) == sum(k - 1) + k == 1 + 2 + 3 + .... + (k-1) + k 所以可以证得 n == k 的时候，sum(k) 亦正确。 3. 由数学归纳法，知 sum 是满足题意的函式。 回想一下，我们学到了什麽？ 1. 归纳基底可以当成递回的终止条件。 2. 归纳假设可以帮我们解决问题(把问题拆解)。 3. 数学归纳法可以帮我们证明演算法的正确性。 范例二 请写一个程式来列出 n 阶河内塔如何从柱 1 移到柱 3。(柱 2 可以 是中继点) 解： 我们考虑我们要写一个函式 honai 它会有四个参数，第一个是我们 要移动多少个圆盘，第二个是我们的起点柱子，第三个是我们的终点 柱子，第四个是我们的中继柱子。 我们先尝试使用数学归纳法： 1. 归纳基底：n == 1 的时候，直接从起点移到终继点 2. 归纳假设：假定我们会解决 n == k - 1 的问题，试证我们也会 解决 n == k 的问题。 如果我们会解决 n == k - 1 的问题，我们可以先把起点上前 k - 1 个搬到中继柱子，把 第 k 个 搬到终点柱子，在把刚才 k - 1 个搬到终点柱子 n == k 时，问题可以被解决！ 3. 由 1 2 证明我们会解决河内塔问题！ int hanoi(int n, int from, int to, int mid) { if (n == 1) { printf("move from %d to %d\n", from, to); } else { hanoi(n - 1, from, mid, to); printf("move from %d to %d\n", from, to); hanoi(n - 1, mid, to, from); } } 结语 从这一篇文章我们可以知道：数归是一个用来设计递回演算法的有利 工具，你可以善用归纳基底、归纳假设弄出形形色色的递回，你也可 以用数归来证明演算法的正确性。当然，设计演算法、证明正确性的 工具不只一种，然而无疑的，数归却是我们在高中都学过的XD，而且 是一个相当简单而优美的方法。我想透过数归来介绍递回应该可以让 更多人「找到递回的真谛」吧。 另外，我想感谢《Introduction to Algorithms: A Creative App- roach》（中译: 建构式演算法）的作者 Udi Manber。就是他的这一 本书让我知道数归与递回之间的关系，这是一本好书，建议大家学演 算法的时候可以看看，他用了很多数归来证明演算法的正确性。 最後我想说：以後我不会在晚上发文了，不知不觉就天亮了。一整晚 没有睡觉。如果文章有错是正常的，我现在打一个字的仓颉拆码都要 想半天，所以还请大家帮忙 DEBUG。谢谢。 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.241.166 ※ 编辑: LoganChien 来自: 140.112.241.166 (10/16 08:18) ※ 编辑: LoganChien 来自: 140.112.241.166 (10/16 08:21)