梵塔问题
据说在东方的古国──印度土地上，有一座印度教的神庙，这庙有一块黄铜板，板上插著三根细细的、镶上宝石的细针，细针像菜叶般粗，而高就像成人由手腕到肘关节的长。
当印度教的主神梵天在创造地球这个世界时，就在其中的一根针上从下到上放了半径由大到小的六十四片圆金片环，这就是有名的「梵塔」或称「汉内塔」（Towers of Hanoi）。
天神梵天要这庙的僧侣，把这些金片全部由一根针移到另外一根指定的针上，一次只能移一片，不管在什么情况下，金片环的大小次序不能变更，小金片环永远只能放在大金片环上面。
只要有一天这六十四片的金环能从指定的针上完全转移到另外指定的针上，世界末日就来到，芸芸众生、神庙一切都将消灭，万物尽入极乐世界去。
n阶梵塔移动次数:设金片数为n，则移动次数=2的n次方-1
解决算法(C语言) /* Copyrighter by SS7E */
#include<stdio.h> /* Copyrighter by SS7E */
void hanoi(int n,char A,char B,char C) /* Copyrighter by SS7E */
{
if(n==1)
{
printf("Move disk %d from %c to %c
",n,A,C);
}
else
{
hanoi(n-1,A,C,B); /* Copyrighter by SS7E */
printf("Move disk %d from %c to %c
",n,A,C);
hanoi(n-1,B,A,C); /* Copyrighter by SS7E */
}
}
main() /* Copyrighter by SS7E */
{
int n;
printf("请输入数字n以解决n阶汉诺塔问题：
");
scanf("%d",&n);
hanoi(n,'A','B','C');
}/* Copyrighter by SS7E */
用Java算法
class HanoiTower
{
static void moves(char a,char c)
{
System.ou.println("From"+a+"To"+c);
}
static viod hanoi(int n,char a,char b,char c)
{
if(n==)
moves(a,c);
else
{
hanoi(n-1,a,c,b);
moves(a,c);
hanoi(n-1,b,a,c);
}
}
public static void main(String[] args)
{
int n;
n=Ingeter.parseInt(args[2]);
hanoi(n,'A','B','C');
}
}
2.3典型例题
例3 梵塔问题
如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子
从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
program fanta;
var
n:integer;
procedure move(n,a,b,c:integer);
begin
if n=1 then writeln(a,'--->',c)
else begin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Enter n=');
read(n);
move(n,1,2,3);
end.
用差分方程求解梵塔问题：
设按上小下大的次序，把依次排列好的t个金盘从一根柱子上移到另一根柱子上需要移动的次数为Y(t)次，同理，移动t+1个盘子的次数为Y(t+1)次。
建立Y(t)与Y(t+1)的关系式：Y(t+1)=2Y(t)+1
求递推，利用差分方程：Y(t)‘=2Y(t)+1
解得：Y(t)=c*(2^t)-1
因为Y(1)=2c-1=1,所以c=1.
则Y(t)=2^t-1
因此，梵塔问题常见的金盘片数为64片，经过计算机的运算，移动的次数需18,446,744,073,709,551,615。
假设1秒钟移动1片金盘，1年中共365×24×60×60＝31536000秒，完成64片金盘的时间 为18,446,744,073,709,551,615/31536000,大约需要5849亿年。