河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。
解法
如果柱子标为ABC,要由A搬至C,在只有一个盘子时,就将它直接搬至C,当有两个盘子,就将B当作辅助柱。
如果盘数超过2个,将第三个以下的盘子遮起来,就很简单了,每次处理两个盘子,也就是:A->B、A ->C、B->C这三个步骤,而被遮住的部份,其实就是进入程式的递回处理。
事实上,若有n个盘子,则移动完毕所需之次数为2^n - 1,所以当盘数为64时,则所需次数为:
264- 1 = 18446744073709551615
为5.05390248594782e+16年,也就是约5000世纪,如果对这数字没什么概念,就假设每秒钟搬一个盘子好了,也要约5850亿年左右。
C语言实现
#include <stdio.h>
void hanoi(int n, char A, char B, char C)
{
if(n == 1)
{
printf("Move sheet %d from %c to %c\n", n, A, C);
}
else
{
hanoi(n-1, A, C, B);
printf("Move sheet %d from %c to %c\n", n, A, C);
hanoi(n-1, B, A, C);
}
}
int main()
{
int n;
printf("请输入盘数:");
scanf("%d", &n);
hanoi(n, 'A', 'B', 'C');
return 0;
}
- 大小: 2.9 KB
- 大小: 3.2 KB
- 大小: 3 KB
- 大小: 5.8 KB
分享到:
相关推荐
用C语言实现汉诺塔的递归算法,另外还有用栈来实现的方式:http://download.csdn.net/detail/jason19905/6419427
适应于大学生学习算法
汉诺塔递归算法: 问题抽象 3个塔,n个碟子 初始:所有碟子放在1号塔,大的在底下,小的在上面 任务:把碟子移动到2号塔,顺序不变, 可用3号塔辅助 限制 每次只能移动一个碟子 总是大碟子...
汉诺塔的实现程序(c语言)汉诺塔的实现程序(c语言)
c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序c语言实现的汉诺塔演示程序...
利用C++编写汉诺塔的非递归算法以及其运行程序(算法中包含注释)。
汉诺塔问题C语言实现
汉诺塔 C语言程序汉诺塔 C语言程序
这是个汉诺塔程序,在调试的时候,输入的数字最好不要大于15,因为每大一个数 所得的结果的步骤都会多一倍。如果你有耐心等待结果的话除外。汉诺塔是在欧洲 流行的一种游戏,有a,b,c三个竿。a竿上有若干个由大到小的...
非常短小的汉诺塔小程序 C语言撰写,方便C语言爱好者 使用,主要采用递归算法。
用栈来实现汉诺塔,要明白递归就是栈的重要应用之一,递归是系统自动调用栈来处理。
我用vc编了一个用栈实现汉诺塔的非递归程序。可以运行的,里面代码作了说明的!
汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码汉诺塔C语言源代码
一个用递归实现的汉诺塔代码,简单明了,易于理解
简单的汉诺塔源代码,输出结果非常直观,便于初学者学习该算法:)
运用C语言实现汉诺塔问题.可以实现对盘子的移动。
网上看来的,比较详细。包含了递归以及不用递归的代码。 C和C++版的都有。
用C++实现汉诺塔的递归算法,定义了类和方法。
//程序实现了mystack栈的声明和定义,并且通过函数 //move_stacks的递归调用和函数move_a_ring实现汉 //诺塔的算法,并用函数print_stacks和pr_chars实现汉诺 //塔的动画效果
汉诺塔源程序算法 汉诺塔源程序算法 汉诺塔源程序算法 汉诺塔源程序算法