大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全家桶1年46,售后保障稳定
汉诺塔(Hanoi)
- 编程实现把 A 的 n 个盘子移动到 C(盘子编号是 [1, n] )
每次只能移动1个盘子
大盘子只能放在小盘子下面
1、汉诺塔 — 1个盘子
2、汉诺塔 — 2个盘子
3、汉诺塔 — 3个盘子
3、汉诺塔 — 思路
- 其实分 2 种情况讨论即可
(1)当 n == 1时,直接将盘子从 A 移动到C
(2)当 n > 1时,可以拆分成3大步骤
①将 n– 1 个盘子从 A 移动到B
② 将编号为 n 的盘子从 A 移动到C
③将 n– 1 个盘子从 B 移动到C
✓ 步骤①③ 明显是个递归调用
4、汉诺塔 — 实现
public class Hanoi {
public static void main(String[] args) {
new Hanoi().hanoi(3,"A","B","C");
}
/** * 将n个碟子从p1挪动到p3 * @param p2 中间的柱子 */
void hanoi(int n,String p1,String p2,String p3){
if (n == 1){
move(n,p1,p3);
return;
}
//将p3看作中间柱子,将n-1个碟子从p1移动到p2
hanoi(n-1,p1,p3,p2);
move(n,p1,p3);
//将p1看作中间柱子,将n-1个碟子从p2移动到p3
hanoi(n-1,p2,p1,p3);
}
/** * 将 no号盘子从 from 移动到 to * @param no 碟子 * @param from 开始移动的柱子 * @param to 移动到的柱子 */
void move(int no, String from,String to){
System.out.println("将"+no + "号盘子从" + from + "移动到"+to);
}
}
运行结果:
将1号盘子从A移动到C
将2号盘子从A移动到B
将1号盘子从C移动到B
将3号盘子从A移动到C
将1号盘子从B移动到A
将2号盘子从B移动到C
将1号盘子从A移动到C
- T(n) = 2 ∗ T(n) − 1 + O(1)
因此时间复杂度是:O(2n) - 空间复杂度:O(n)
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/206734.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...