Hanoi函数解析

Comment A1 这里暂时把 n 个盘看 作一个整体 Comment A2 这里暂时把 n 1 个 盘看作一个整体 1 C C 语言中的经典函数递归问题语言中的经典函数递归问题 Hanoi Hanoi 程序的解析程序的解析 在谭浩强编写的 C 程序设计 第三版 中有这样一个经典递归 红框中 程序 程序运行环境 Visual Stdio 2008 include stdafx h include void main void hanoi int n char one char two char three int m printf input the number of diskes scanf d printf The step to move d diskes n m hanoi m A B C getchar getchar void hanoi int n char one char two char three void move char x char y if n 1 move one three else hanoi n 1 one three two move one three hanoi n 1 two one three void move char x char y printf c c n x y 很显然 这是著名的 Hanoi 问题的解答程序 Hanoi 问题是一个古典的数学问题 是 一个用递归方法解题的典型例子 问题是这样的 古代有一个梵塔 塔内有 3 个座 A B C 开始时 A 座上有 64 个盘子 盘子大小不等 大的在下 小的在上 如图 1 1 所 示 有一个老和尚想把这 64 个盘子从 A 座移到 C 座 但每次只允许移动一个盘子 且在 移动过程中在 3 个座上都始终保持大盘在下 小盘在上 在移动过程中可以利用 B 座 A A B B C C 图图 1 11 1 一 首先 我们用数学知识来分析 1 逆向分析 要把 n 个盘从 A 移到 C 先要把 n 1 个盘从 A 移到 B 再把第 n 个 盘从 A 移到 C 最后把 n 1 个盘从 B 移到 C 要把 n 1 个盘从 A 移到 B 又必须先把 n 2 个盘从 A 移到 C 再把第 n 1 个盘从 A 移到 B 最后把 n 2 个盘从 C 移到 B 如此循环 直到遇到第一个盘 这是终止递归的 标志 又是层层解开递归的钥匙 Comment A3 这里所有的 1 指的 是移动最后一个盘 Comment A4 整体 1 第一次移动 到 B Comment A5 整体 1 第二次移动 到 C Comment A6 整体 1 2 第一次移 动到 B Comment A7 整体 1 2 第二次移 动到 C 2 从上面的分析中 我们经过观察可以得到下面的结论 每次移动 整体 的最后一个盘时 都须要把上面所有的盘 大于一个盘 并且 把它们也看作一个整体 移动两次 而层层递推到第一个盘时 第一个盘只需移 动其本身 1 次 更不需移动第 0 个盘 2 次 由此 移动次数的数学表达如下 C n n C n 1n 1 2 1 C n 2n 2 C n 3n 3 2 1 C 2 2 C 1 1 2 1 C 1 1 1 这样 迭代求出 C n 12 n 前后两次 整体 移动的方法基本是一样的 此时完全可以忽略底座的状态 这就只需在编程时控制好 A B C 座的位置 以便在函数执行相同动作时 可 以得到不同的效果 2 顺向分析 移动 2 个盘 A B A C B C 移动 3 个盘 A C A B C B A C B A B C A C 这里经过观察 我们又可以得出结论 一种移动中 两次进行的 整体 移动仅仅是字母的相同方式的变更 把 A 换成 B 把 B 换成 C 把 C 换成 A 在 移动 3 个盘 的过程中 2 次运用到了 移动 2 个盘 的方法 同样地 在移动 n 个盘时 我们可以自信地说 通过两次连续 依次运用 前面的步骤 中间再插入 A C 便完成了所有工序 下面是图解法 移 C N 盘 移 B N 1 盘 移 C N 1 盘 移 B N 2 盘 移 C N 2 盘 移 B N 2 盘 移 C N 2 盘 限于表达空间 这里 移 C N 盘 指向 C 移动 N 个盘 且每次 最后一盘 的移动被省 Comment A8 这里对 A B C 重 新分配了在下一个 hanoi 函数中的位 置 目的是实现从 A 到 B 的调运 下同 Comment A9 注意 运行到这一步 时仍需再一次调用 hanoi 函数 Comment A10 记为 1 1 而实际上 它一步就可以完成了 Comment A11 方法同 2 1 语句 上 文已经分析过 Comment A12 方法同 3 1 语句 3 略 由以上同样可以看出移动的总次数为C n 12 n 二 然后 我们再运用 C 语言的知识来分析 要用 C 语言中的递归函数来分析 首先必须明白递归函数的运作原理 以上文 的递归函数的调用为例 第一次是 main 函数调用 hanoi m A B C 此时 在 运 行 hanoi 函数时 n 值全赋为 m 的值 one 值全赋为 A two 值全赋为 B three 值全赋为 C 亦即 当函数头中的变量一旦取到值时 函数内所有的变量取值 随 即确定下来 而不是函数运行到那一条语句才把该句中的变量值确定下来 所以 第一次使用 Hanoi 是时 有 else hanoi 2 A C B move A C 这里是前两层与第 3 层之间的运作关系 hanoi 2 B A C hanoi 函数首先运行 hanoi 2 A C B 语句 记为 3 1 它的下面两条语句 记为 3 2 3 3 把 3 1 展开如下 else hanoi 1 A B C hanoi 2 A C B move A B hanoi 1 C A B 接着 hanoi 函数又继续运行 hanoi 1 A B C 语句 记为 2 1 它的下面两 条语句记为 2 2 2 3 把 2 1 展开 if n 1 hanoi 1 A B C move A C 然后反推到执行 2 2 move A B 再到 2 3 hanoi 1 C A B 再返回执行 3 2 move A C 再到 3 3 hanoi 2 B A C 当调用 hanoi 时 要注意变量 n one two three 中值的不断更新及其更新方法 以 2 1 为例 hanoi n 1 one three two 1 A B C void hanoi int n char one char two char three 这里 2 1 语句中变量 或表达式 的具体值已经存在 分别为 1 A B C 在上文 中我直接以常量的形式写出 是为了更直观地表达这种更新方法 这有同于赋值 却 与赋值有相当的差别 读者可以自己体会 4 通过上面的 C 语言分析 以及细致观察 我们又可以得出一些有趣的结论 文章开头程序的红框中两条 move 语句是交替执行的 下面我们用事实来说 话 把 if 下的 move 语句替换为 printf hidden n 看看运行结果 再把 else 下的 move 语句替换为 printf hidden n 看看运行结果 Comment A13 位置是函数 hanoi 本 身的 Comment A14 取 m 1 为特例 确 定这里应填写的变量 Comment A15 按第 n 层与上面 n 1 层的关系编写 5 结果正如我们所料 事实上 我们这里的变量 one two three 提供的仅仅是一个临时储存位置的功 能 这里临时储存的是 A B C 三个座位 且三个座位可在 one two three 三变量中按我 们的要求不断更换位置 记住 one two three 并非三个座位的固定住所 而实现盘子从 A 座调到 C 座是函数 hanoi 的功能 void hanoi 位置 1 位置 2 位置 3 位置 4 hanoi 函数实现了把位置 2 上的盘子调到位置 4 位置 3 是被借用的 这是编程者所赋予 hanoi 函数的属性 这个属性我们是可以更改的 现在我们指定 hanoi 函数实现把位置 4 的盘子 A 座 调到位置 1 C 座 借助位置 2 然后我们重新编一下程序 结果如下 include stdafx h include void main void hanoi char one char two int n char three int m printf input the number of diskes scanf d printf The step to move d diskes n m hanoi C B m A getchar getchar void hanoi char one char two int n char three void move char x char y if n 1 move three one else hanoi two one n 1 three move three one hanoi one three n 1 two void move char x char y printf c c n x y 读者也可以干脆把if语句该为如下 更便于理解 if n 1 hanoi two one n 1 three move three one hanoi one three n 1 two else move three one Comment A16 两个 move 函数中的 one three 是都是直接从 hanoi 函数 头中照搬过来的 这在 hanoi 函数头 变量的更新方法中谈及 hanoi 函数 头的变量直接映射到函数体中的变量 只不过在映射到 hanoi 中时 变量所 占位置 指位置 1 2 3 4 与此同 时改变了 以此满足对 A B C 的 要求 而 move 函数不存在这个问题 因而 move 函数总是相同的 从而 move 也就对应输出了 hanoi 函数的 功能性动作 6 再看一下运行结果 运行结果也完全吻合 两个 move three one 语句反映的是函数 hanoi 从位置 4 到位置 1 的调运功能 这里的 three one 对应的是函数头 void hanoi char one char two int n char three 中的 three one 即保证了函数功能与输出结果的一致性 同样地 在开头的程序中的 move one three 是函数 hanoi 从位置 2 到位置 4 的运调功 能 对应的是函数头 void hanoi int n char one char two char three 中的 one three 可以看到 递归函数与我们以前所学的 while 循环非常类似 同时仍然有很大区别 1 不同点 while 循环每运行一次便有一个确定的结果 而递归函数运行过程中没有确定的结果 并 沿着这个不确定性层层往下套 直到遇到一把终极钥匙 又返回去层层解开这些套 最终 一路解出我们所要的结果 2 相同点 两种函数都需要时时判断是否符合条件 当不符合时 或当符合时 循环 递归才被终止 到现在 可能有些读者仍未明白变量 one two three 的作用 我在这里再补充几点 一开始 one 在 hanoi 函数变量声明中的位置 1 three 在位置 4 它们正好落在了我们要 求 hanoi 函数的 功能特区 上 当函数执行 else 中的 hanoi 语句时 又按我们的想法 对 A B C 在下一个 hanoi 函数中的位置重新分配了一下 使 A B C 落在相应的 功能 特区 这时 one three 也在特区上 它们刚好承载了相应的字母 因此 此时的 one three 即两个 move 中的 one three 不仅承载了字母 还显示着 hanoi 函数的特 Comment A17 循环 是由递归函 数的特点提供的 对应 是通过定 期改变变量位置来实现的 7 定功能 当 A B C 再次进行分配时 one three 便不再显示函数功能 因为它失去了原 来的特定位置 如此循环 现在可以告诉你 上面所说的什么 hanoi 函数的 功能位置 是不存在的 是在我们 心中认定的 当你按自己的意志让变量在 hanoi 中改变着位置时 hanoi 函数的功能便 按你的