Hanoi Tower 汉诺塔问题 /c /python
2018-06-18 04:16:43来源:未知 阅读 ()
问题描述:
有一个梵塔,塔内有三个座A、B、C,A座上有诺干个盘子,盘子大小不等,大的在下,小的在上(如图)。
把这些个盘子从A座移到C座,中间可以借用B座但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘
子始终保持大盘在下,小盘在上。
描述简化:把A柱上的n个盘子移动到C柱,其中可以借用B柱。
我们假设有n个盘子,编号为:1,2,3,4……n。
(请问:把大象装冰箱里一共分几步? 三步。) prefect!
接下来我们分三步走:
初始状态是A柱上有n个盘子,B、C两个柱子空。要想将盘子移到C柱上,首先要把第n个盘子移到C柱上,而要移动第n个盘子就要先把前n-1个盘子移动到B柱上。所以
第一步:将前n-1个盘子移动到B柱上(先不用管怎么移动),将第n个盘子移动到C柱上。
移动后的状态是A柱空,B柱上有n-1个盘子,C柱空(因为第n个盘子最大,其他所有盘子都可以放,所以C柱上相当于空。)
第二步:将B柱上的n-2个盘子移动到A柱上(先不用管怎么移动),将第n-1个盘子移动到C柱上。
移动后的状态和初始状态相同只是规模小了一点(前两步就已经实现了一次递归)
第三步:利用递归直至n=1.
我一再强调的:当要把最大盘子上面的所有盘子移动到另一个空柱上时,不要关心具体如何移动,只用把它看做一个函数可以完成即可,不用关心函数的具体实现。如果你的思路纠结在这里,就很难继续深入了。
给出c代码:
#include <stdio.h> #include <stdlib.h> void hanoi(char src, char mid, char dst, int n)
//注意hanoi函数传递的变量(顺序)的意义:把n个盘子从src通过mid移动到dst上 { if (n == 1) { printf("Move disk %d from %c to %c\n", n, src, dst); } else { hanoi(src, dst, mid, n - 1); //第一步:先把n-1个盘子从src通过dst移动到mid printf("Move disk %d from %c to %c\n", n, src, dst);//把最下面的一个盘子从src直接移动到dst hanoi(mid, src, dst, n - 1); //第二步:把n-1个盘子从mid通过src移动到dst } } int main(void) { int n; while (scanf("%d", &n) != EOF) { hanoi('A', 'B', 'C', n); } return 0; }
python代码:
def hanoi(n, a, b, c): if n == 1: print('move %d from %s to %s' % (n, a, c)) else: hanoi(n - 1, a, c, b)//把n-1个盘子从a经c移动到b print('move %d from %s to %s' % (n, a, c))//把最下面的一个盘子从a移动到c hanoi(n - 1, b, a, c)//把剩下的n-1个盘子从b经a移动到c
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C语言 汉诺塔问题 2018-06-18
- Hanoi塔问题 2018-06-18
- 3145 汉诺塔游戏 2018-06-17
- 6261:汉诺塔问题 2018-06-17
- C++基础算法学习——汉洛塔问题 2018-06-17
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash