汉诺塔问题java代码_汉诺塔java实现结果

汉诺塔问题java代码_汉诺塔java实现结果Java基础语法(汉罗塔)1起源2需求3分析3.11个碟子3.22个碟子3.33个碟子3.44个碟子3.5规律4代码实现:直接算法5代码实现封装:栈的思想1起源汉罗塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。2需求将汉罗塔问题抽象到数学:

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE稳定放心使用

1 起源

汉罗塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。

2 需求

将汉罗塔问题抽象到数学:

  • 1.有三根杆子 A,B,C;
  • 2.A 杆上有若干大小不同的碟子,从上往下越来越大;
  • 3.每次移动一块碟子,小的只能叠在大的上面;
  • 4.把所有碟子从 A 杆全部移到 C 杆上。

在这里插入图片描述

3 分析

  • 确定 A 柱子上的初始碟子:int disks = 3;
  • 确定三个容器 char ‘A’、char ‘B’、char ‘C’;
  • 初始确定移动方法,从 from –> to:hanrotaMove(int disks, char from, char index, char to)。

3.1 1个碟子

A 柱子上只有一个碟子时,直接移动到 C:

num from index to mv
1 A B C A–>C

3.2 2个碟子

num from index to mv
1 A C B A–>B
2 A B C A–>C
1 B A C B–>C

3.3 3个碟子

num from index to mv
1 A B C A–>C
2 A C B A–>B
1 C A B C–>B
3 A B C A–>C
1 B C A B–>A
2 B A C B–>C
1 A B C A–>C

3.4 4个碟子

num from index to mv
1 A C B A–>B
2 A B C A–>C
1 B A C B–>C
3 A C B A–>B
1 C B A C–>A
2 C A B C–>B
1 A C B A–>B
4 A B C A–>C
1 B A C B–>C
2 B C A B–>A
1 C B A C–>A
3 B A C B–>C
1 A C B A–>B
2 A B C A–>C
1 B A C B–>C

3.5 规律

在上述前 4个下不难发现有规律存在:
A 柱子上有 n 个碟子,移动步骤便以 n 分为上下两部分,且上部分移动的数与下部分移动的数相同,此处便有递归分治的思想,解析 4 个碟子:
hanrotaMove(int disks, char from, char index, char to)
在初始入参:from ‘A’ – index ‘B’ – to ‘C’ 下,每一级都做为下一级分支的入参,且每个分支的上部都有相同的步骤“换”:from-to-index,每个分支的下部也都有相同的步骤“换”:index-from-to,可将此图看为完全二叉树。

4 代码实现:直接算法

代码常规实现:Hanrota.java

/** * @author zc * @date 2021/10/29 9:30 * 汉罗塔 * 1.有三根杆子 A,B,C; * 2.A 杆上有若干大小不同的碟子,从上往下越来越大; * 2.每次移动一块碟子,小的只能叠在大的上面; * 3.把所有碟子从 A 杆全部移到 C 杆上。 * * main(String[] args):主方法,主程序入口; * hanrotaMove(int disks, char from, char index, char to):方法,汉罗塔移动 */
public class Hanrota { 
   
    /** * 主程序入口 * @param args 系统参数 */
    public static void main(String[] args) { 
   
        // 初始化一个 A 柱子上碟子数
        int disks = 4;
        hanrotaMove(disks, 'A', 'B', 'C');
    }

    /** * 汉罗塔移动 * @param disks 待移动碟子数量 * @param from 起始点 * @param index 过渡点 * @param to 目标点 */
    public static void hanrotaMove(int disks, char from, char index, char to){ 
   
        if (disks <= 0){ 
   
            System.out.println("碟子数量不足");
        } else if (disks == 1) { 
   
            System.out.println("Disk " + disks + " from " + from + " to " + to);
        } else { 
   
            // 递归上部分
            hanrotaMove(disks - 1, from, to, index);
            // 中间分隔点
            System.out.println("Disk " + disks + " from " + from + " to " + to);
            // 递归下部分
            hanrotaMove(disks - 1, index, from, to);
        }
    }
}

运行结果:

Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C
Disk 3 from A to B
Disk 1 from C to A
Disk 2 from C to B
Disk 1 from A to B
Disk 4 from A to C
Disk 1 from B to C
Disk 2 from B to A
Disk 1 from C to A
Disk 3 from B to C
Disk 1 from A to B
Disk 2 from A to C
Disk 1 from B to C

5 代码实现封装:栈的思想

汉罗塔的移动存储很像栈的思想:先进后出

就是在上一步的代码实现:直接算法上封装一下。

首先要 java 实现一个栈,再递归分治解决汉罗塔移动:MyStack.java

package com;
/** * @author zc * @date 2021/10/29 11:13 * 栈:MyStack * * main(String[] args):主方法,主程序入口 * MyStack(int s):有参构造,初始化栈容器的大小 * push(long j):方法,入栈 * pop():方法,出栈 * peek():方法,获取栈顶值 * isEmpty():方法,判断栈是否为空 * isFull():方法,判断栈是否存储满 * size():方法,获取当前栈中元数存储个数 * hanrotaMove(int disks, MyStack A, MyStack B, MyStack C):方法,汉罗塔移动 */
public class MyStack { 

/** * 属性 maxSize:初始化栈的容器大小 */
private int maxSize;
/** * 属性 stackArray:栈中数据存储 */
private long[] stackArray;
/** * 属性 top:标志栈中最上一个元素值 */
private int top;
/** * 有参构造,初始化栈容器的大小 * @param s 栈容器大小 */
public MyStack(int s) { 

maxSize = s;
stackArray = new long[maxSize];
top = -1;
}
/** * 入栈 * @param j 入栈的元素 */
public void push(long j) { 

stackArray[++top] = j;
}
/** * 出栈 * @return 返回出栈的元素 */
public long pop() { 

return stackArray[top--];
}
/** * 获取栈中最上一个值 * @return 返回栈顶值 */
public long peek() { 

return stackArray[top];
}
/** * 判断栈是否为空 * @return 返回状态为空 true,否则 false */
public boolean isEmpty() { 

return (top == -1);
}
/** * 判断栈是否存储满 * @return 返回状态已满 true,否则 false */
public boolean isFull() { 

return (top == maxSize - 1);
}
/** * 求栈中当前存储元数个数 * @return 返回当前存储元数个数 */
public int size(){ 

return top + 1;
}
/** * 主程序入口 * @param args 系统参数 */
public static void main(String[] args) { 

// 初始化栈空间
int topN = 3;
// 初始化 A 栈空间
MyStack A = new MyStack(topN);
// 初始化 B 栈空间
MyStack B = new MyStack(topN);
// 初始化 C 栈空间
MyStack C = new MyStack(topN);
// 给 A 栈添加汉罗塔数
A.push(13);
A.push(9);
A.push(4);
// 汉罗塔移动
hanrotaMove(A.size(),A,B,C);
// 打印 C 栈元素
while (!C.isEmpty()){ 

System.out.print(C.pop() + " ");
}
}
/** * 汉罗塔移动 * @param A A 柱子 * @param B B 柱子 * @param C C 柱子 */
public static void hanrotaMove(int disks, MyStack A, MyStack B, MyStack C){ 

if (disks <= 0){ 

System.out.println("A 柱子上没有数据");
} else if (disks == 1) { 

// A 中出栈
long value = A.pop();
System.out.println("Disk " + value + " from " + A + " to " + C);
// C 中入栈
C.push(value);
} else { 

// 递归上部
hanrotaMove(disks - 1, A, C, B);
// A 中出栈
long value = A.pop();
System.out.println("Disk " + value + " from " + A + " to " + C);
// C 中入栈
C.push(value);
// 递归下部
hanrotaMove(disks - 1, B, A, C);
}
}
}

运行结果:

Disk 4 from com.MyStack@74a14482 to com.MyStack@1540e19d
Disk 9 from com.MyStack@74a14482 to com.MyStack@677327b6
Disk 4 from com.MyStack@1540e19d to com.MyStack@677327b6
Disk 13 from com.MyStack@74a14482 to com.MyStack@1540e19d
Disk 4 from com.MyStack@677327b6 to com.MyStack@74a14482
Disk 9 from com.MyStack@677327b6 to com.MyStack@1540e19d
Disk 4 from com.MyStack@74a14482 to com.MyStack@1540e19d
4 9 13 
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/182972.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • java redis 没密码配置_jeeplus设置Redis密码

    java redis 没密码配置_jeeplus设置Redis密码接手过来的jeeplus系统原本没有设置redis密码,近期要上线,为保证redis安全性,运维要求添加redis密码,且在线上环境为redis设置了密码。接下来我需要修改程序内容来迎合运维此项修改,方式如下:设置Redis密码涉及到以下三个文件,分别是:jeeplus.properties、spring-context-jedis.xml和JedisUtils.java。以上三个文件的含义为如下…

  • pyqt退出窗口_win10电脑软件闪退

    pyqt退出窗口_win10电脑软件闪退1.使用qtdesigner创建窗口界面这个都很熟悉了,就不重复说明了。(自行百度)2.pyqt将.ui文件转成python代码cd到.ui文件的目录,使用指令即可完成。得到一个py文件(一个类)红色部分是我自己加上去的,只是为了更好看懂代码,调试代码。3.运行pyqt生成的python代码,生成界面这里,需要添加几行代码!直接在Ui_Dialog类的py文件尾部添加如下代码:if__name__==”__main__”:app=QApplication(

  • pycharm如何设置快捷键「建议收藏」

    pycharm如何设置快捷键「建议收藏」pycharm中默认ctrl+d是复制一行,这和jupyter完全不一样,我比较喜欢的是:ctrl+d:删除一行ctrl+c:复制一行所以想要将pycharm进行修改。我们以ctrl+d:删除一行为例。找到如下:点击那一行。然后弹出如下对话框:我们不需要删除,直接按快捷键ctrl+d,自动更换为ctrl+d。此时会说和其他快捷键冲突了,没事,删除其他快捷键即可,那些都是一些不常用的。然后,我们可以删除以前的那个快捷键。完成…

  • hibernate sql查询_sql server查询命令

    hibernate sql查询_sql server查询命令一.SQLQuery简介SQLQuery接口用于接受一个sql语句进行查询,然后调用list()或uniqueResult()进行查询。但是sql语句不会直接封装到实体对象里,需要手写代码才可以封装到实体中。二.SQLQuery常用接口方法addEntity()方法:该方法用于将查询到的结果集转换为你设置的实体类setter()方法:Query接口中提供了一系列的setter方法用于设置…

  • IDEA的基本使用:让你的IDEA有飞一般的感觉[通俗易懂]

    IDEA的基本使用:让你的IDEA有飞一般的感觉[通俗易懂]1.设置maven在File->settings->搜索maven Mavanhomedirectory–设置maven安装包的bin文件夹所在的位置 Usersettingsfile–设置setting文件所在的位置 Localrepository–设置本地仓库的2.IDEA设置代码行宽度在File->settings->E…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号