【无标题】
2022/1/4 6:10:13
本文主要是介绍【无标题】,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
汉诺塔问题的Java实现(递归与非递归)
文章目录
- 汉诺塔问题的Java实现(递归与非递归)
- 一、汉诺塔问题描述
- 二、汉诺塔解题思路
- 三、递归
- 四、非递归
一、汉诺塔问题描述
汉诺塔问题就是有三张柱子A、B、C,然后初始化在A上放了N个圆盘,圆盘按照小压大的方式堆放,需要用最少的步骤从A柱子上挪到C柱子上。在整个移动的过程中,也必须保持小压大的规则。
如下图所示,需要把A上的四个圆盘挪到C上。
二、汉诺塔解题思路
假设A上面有N个圆盘,我们可以把每个圆盘的直径看作是N,那从最下面开始数:盘子直径是N,N-1,N-2,…,2,1
因为到目标柱子C后还需要维持小压大的规则,那第一个到达C柱子的圆盘肯定是最大的圆盘,也就是直径为N的圆盘,那剩下的圆盘(1到N-1)在哪里呢,都在过渡柱子B上。
按照这个逻辑,C上每次放一个除了C上面的圆盘外,最大的圆盘,然后其余的圆盘按照小压大的逻辑放在过度柱子上(有可能是A,也有可能是B)。
由上面可以看出,C上放一个除它外最大圆盘的逻辑是,先从堆满圆盘的柱子上转移圆盘,只剩下一个,然后把这一个圆盘挪到C上。
三、递归
递归思路很符合上面的思路,一共有三个柱子,from、to、temp,先从from move n-1个圆盘到temp,然后从from move第N个给 to,最后从temp上面把剩余圆盘转移给to。
public static void hanoi(int n) { if (n > 0) { func(n, "A", "C", "B"); } } private static void func(int n, String from, String to, String other) { if (n == 1) { System.out.println("move 1 from " + from + " to " + to); } else { func(n - 1, from, other, to); System.out.println("move " + n + " from " + from + " to " + to); func(n - 1, other, to, from); } }
四、非递归
static class HanoiRecord { int index;//代表盘子的序号 int n; String from; String to; String other; public HanoiRecord(int index, int n, String from, String to, String other) { this.index = index; this.n = n; this.from = from; this.to = to; this.other = other; } } public static void hanoi3(int n) { hanoiNonRecursion(n, "A", "C", "B"); } private static void hanoiNonRecursion(int n, String A, String C, String B) { if (n < 1) return; Stack<HanoiRecord> stack = new Stack<>(); stack.push(new HanoiRecord(n, n, A, C, B)); while (!stack.isEmpty()) { HanoiRecord pop = stack.pop(); if (pop.n == 1) { move(pop.index, pop.from, pop.to); } else { //栈是先进后出的,所以和递归的处理逻辑相反,先把temp到to进栈 stack.push(new HanoiRecord(pop.n - 1, pop.n - 1, pop.other, pop.to, pop.from)); stack.push(new HanoiRecord(pop.n, 1, pop.from, pop.to, pop.other)); stack.push(new HanoiRecord(pop.n - 1, pop.n - 1, pop.from, pop.other, pop.to)); } } } private static void move(int index, String from, String to) { System.out.println("move " + index + " from " + from + " to " + to); }
类HanoiRecord里面的index可以不要,只是用来打印的而已。
这篇关于【无标题】的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南