汉诺塔：（Hanoi)是一种玩具，如图![这里写图片描述]() 从左到右 A B C 柱 大盘子在下, 小盘子在上, 借助B柱将所有盘子从A柱移动到C柱, 期间只有一个原则: 大盘子只能在小盘子的下面. 问题理解与描述： 1．问题的理解与描述 问题的形式化表示为： 输入：圆盘数n，3根细杆—— 源杆A、过渡杆B和目标杆C。 输出：圆盘从源杆移动到目标杆过程的最少步骤序列。 2.算法的伪代码：
HANOI(n, A, B, C)then print A,””, CHANOI(n-1,A, C, B)5 print A,””, C6 HANOI(n-1,B, A, C)
3.算法的运行时间： 对于盘数n，HANOI过程的运行时间
4 算法理解： 理解一：（参考：）
案例 1 – 假设只有一个盘子的时候, 盘子数量 N=1 只有一个步骤 将第1个盘子从A移动到C, 为了对比方便我这样来描述这个步骤： 步骤 盘子编号 从柱子移动 移动到柱子 11AC 案例 2 – 如果有两个盘子, 盘子数量 N = 2 步骤 盘子编号 从柱子移动 移动到柱子 11AB 22AC 31BC 案例 3 – 如果有三个盘子, 盘子数量 N = 3 步骤 盘子编号 从柱子移动 移动到柱子 11 AC 22 A B 31CB 43AC 51BA 62BC 71AC 如何找出盘子移动的规律 ？ 我们要做的最重要的一件事情就是永远要把最底下的一个盘子从 A 移动到 C 看看上面从1个盘子的移动到3个盘子的移动, 在移动记录中,当盘子的编号和盘子数量相同的时候他们的步骤都是从A移动到C (看加粗的部分),其它的步骤对等. 再观察第3个案例中的第 1-3 步 和 第 5-7步 第 1-3 步 目的是从 A 移动到 B 如果我们把 B 当作终点, 那么这里的第 1-3 步理解起来和 第2个案例的三个步骤完全相同, 都是通过一个柱子来移动,和第2个案例比起来在后面加括号来表示 11 AC( A -> B) 22 A B( A -> C) 31CB( B -> C) 总结：将盘子B变成C即可. 第 5-7 步 目的是从 B 移动到 C 如果我们把 C 当作终点, 那么这里的 5-7 步理解起来和上面也是一样的, 和第2个案例的三个步骤也完全相同.和第2个案例比起来就是: 51BA ( A -> B) 62BC ( A- > C) 71AC ( B -> C) 总结: 将盘子B变成A即可 根据这个演示可以明确几点规律: 1. 当盘子只有一个的时候,只有一个动作 从 A 移动到 C 即结束. 2. 当有N个盘子的时候, 中间的动作都是从 A 移动到 C, 那么表示最下面的第N个盘子移动完毕 3. 中间动作之上都可以认为是: 从 A 移动到 B 4. 中间动作之下都可以认为是: 从 B 移动到 C 2，3，4 可以表示为 11AB 22AC 31BC 理解二：（参考：） 美国的一位学者发现一种出人意料的简单的算法，只要轮流两步操作既可以实现：首先，把三张桌子按顺序首尾相接的排列，形成一个环，然后对A上的盘子开始移动，顺时针摆放成 A B C的顺序： 若n为奇数，圆盘的移动顺序是 A->C->B->A->C->B->A……… 即 间隔两个步长移动 。此处的n代表盘子位的层数，比如说 3 层汉诺塔就是从下往上数第1、3 个盘子移动的顺序。 若n为偶数，，圆盘移动的顺序为A->B->C->A->B->C->A……….即 间隔一个步长移动。对n的解释同上 第二个盘子移动 A->B->C。 5.代码实现（c）：
/*************hanoi.c********************/#include<stdlib.h>#include <stdio.h>#include “hanoi.h”/*************找x杆顶部盘的编号**********输入参数：current[i]记录第i号盘所在的杆号x;杆的编号输出参数：x杆顶部盘的编号****************************************/int pickTopDisk(char* current,char x){int i = 0;while (current[i] != x)i++;return i;}/*************汉诺塔**********输入参数：current[i]记录第i号盘所在的杆号n:盘的数量A,B,C:杆的编号****************************************/void hanoi(char* current, int n, char A, char B, char C){i = 0;if (n==1){i = pickTopDisk(current, A);current[i] = C;cout++;printf(“move %d disk %d: %c->%c\n”, cout, i + 1, A, C);return;}hanoi(current, n – 1, A, C, B);current[n- 1] = C;cout++;printf(“move %d disk %d: %c->%c\n”, cout, n, A, C);hanoi(current, n – 1, B, A, C);}extern “C” {#endif // __cplusplusint pickTopDisk(char* current, char x);void hanoi(char* current, int n, char A, char B, char C);#ifdef __cplusplus}#endif#endif/**************main.c************************/#include <stdlib.h>#include “hanoi.h”int main(int argc, char** argv){char current[] = { ‘A’, ‘A’, ‘A’, ‘A’ };char A = ‘A’, B = ‘B’, C = ‘C’;hanoi(current, 4, A, B, C);system(“pause”);return EXIT_SUCCESS;}
6运行结果：
参考：《算法设计、分析与实现：C、C++和Java》 徐子珊
却又小到连一粒嫉妒的沙石也不能容纳
