汉诺塔简介:
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
- 每次只能移动一个圆盘;
- 大盘不能叠在小盘上面。
提示:可将圆盘临时置于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的操作
继续阅读