目录
  1. 1. 问题描述
  2. 2. 思路
算法-河内塔问题

问题描述

河内之塔(Towers of Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的,河内为越战时北越的首都,即现在的胡志明市;1883年法国数学家 Edouard Lucas曾提及这个故事,据说创世纪时Benares有一座波罗教塔,是由三支钻石棒(Pag)所支撑,开始时神在第一根棒上放置64个由上至下依由小至大排列的金盘(Disc),并命令僧侣将所有的金盘从第一根石棒移至第三根石棒,且搬运过程中遵守大盘子在小盘子之下的原则,若每日仅搬一个盘子,则当盘子全数搬运完毕之时,此塔将毁损,而也就是世界末日来临之时。事实上,若有n个盘子,则移动完毕所需之次数为2^n - 1,所以当盘数为64时,则所需次数为:264- 1 = 18446744073709551615 为5.05390248594782e+16年,也就是约5000世纪,如果对这数字没什么概念,就假设每秒钟搬一个盘子好了,也要约5850亿年左右。

思路

三个塔,分别为A、B、C。

当只有一个盘子的时候,只需要从将A塔上的一个盘子移到C塔上。

当A塔上有两个盘子是,先将A塔上的1号盘子移动到B塔上,再将A塔上的2号盘子移动的C塔上,最后将B塔上的小盘子移动到C塔上。

当A塔上有3个盘子时,先将A塔上编号1至2的盘子(共2个)移动到B塔上(需借助C塔),然后将A塔上的3号最大的盘子移动到C塔,最后将B塔上的两个盘子借助A塔移动到C塔上。

所以:

当A塔上有n个盘子是,先将A塔上编号1至n-1的盘子(共n-1个)移动到B塔上(借助C塔),然后将A塔上最大的n号盘子移动到C塔上,最后将B塔上的n-1个盘子借助A塔移动到C塔上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class Main {
static int i = 1;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
char from = 'X', depend_on = 'Y', to = 'Z';
hanoi(n, from, depend_on, to);
}

public static void hanoi(int n, char from, char depend_on, char to) {
if (n == 1) {
move(n, from, to);
return;
} else {
hanoi(n - 1, from, to, depend_on);//X-----Y
move(n, from, to);//X-----Z
hanoi(n - 1, depend_on, from, to);//Y-----Z
}
}

public static void move(int n, char from, char to) {
System.out.println("第" + (i++) + "步:" + n + "号盘子" + from + "--------" + to);
}
}
文章作者: 李浩
文章链接: https://leehoward.cn/2019/10/17/算法-河内塔问题/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 leehoward
打赏
  • 微信
  • 支付宝

评论