汉诺塔简介:

有三根杆子A，B，C。A杆上有N个(N>1)穿孔圆盘，盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆：

1. 每次只能移动一个圆盘；
2. 大盘不能叠在小盘上面。

提示：可将圆盘临时置于B杆，也可将从A杆移出的圆盘重新移回A杆，但都必须遵循上述两条规则。

汉诺塔移动分析:

定义汉诺塔移动函数:

void hanoi(int n, char from, char buffer, char to);

1) 参数 n 表示要移动的盘子数

2) 参数 from 表示盘子所在的柱子

3) 参数 buffer 表示盘子移动过程中借助的柱子

4) 产生 to表示盘子最终要移到的柱子

初始状态:

将A柱子的N个圆盘移至C柱子上, 其中可以借助B柱子

汉诺塔的3个中间状态:

以下内容需要理解函数调用, 栈的知识

栈的知识: 先进后出, 后进先出

1): 汉诺塔移动n-1个盘子从A借助C移到B

移动代码: hanoi(n-1, from, to, buffer);

为何可以移动n-1个盘子, 这是初学者最难理解的部分. 要想理解, 必须理解栈的知识, 递归是一种反向思维.

2): 汉诺塔移动盘子n从A到C

移动代码: printf(“%d A->C\n”, n);

3): 汉诺塔移动n-1个盘子从B借助A移到B

移动代码: hanoi(n-1, buffer, from, to);

这是移动n-1个盘子的情况, 这和初始状态时一样的, 区别在于位于不同的柱子.

移动n-2个盘子并重复1-3步骤

接下来是移动n-2个盘子的情况. 因为 盘子n和n-1已经不要移动了(从递归的思想来看)

直到剩下一个盘子

这是就需要移动最后一个盘子到C, 实际的运算过程中程序会不断压栈(从n, n-1, 直到1), 然后执行此步操作, 注意之后的每一步都是每次移动一个盘子(之前只是压栈操作, 不要移动操作), 然后释放内存, 执行盘子2的操作, 直到最后移动盘子n-1, n的操作
继续阅读 →