Java手把手必会的实例汉诺塔讲解练习

最适合菜鸟的汉诺塔讲解

问题引入

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

让我们先从小事入手。

标记汉诺塔的三根柱子分别为 a ，b ，c

标记汉诺塔上的圆盘分别为：1 ，2，3，4 …n

a 柱上面只有一个圆盘时

只有这一种走法

a柱上有两个圆盘时

a柱上有三个圆盘时

a柱上有四个圆盘时

如上图的实际操作过程可以很明显的找到汉诺塔的操作规律：即分出来三个部分：

第一部分为 第一个红框，用于将 前 n -1 个圆盘移到 b 柱

第二部分 用于将 最大的盘子移到 c 柱

第三部分为 第二个红框，用于将 前 n - 1 个圆盘移到 c 柱

我们之所以这样分为三个部分，是因为不管 a 柱上放了几个盘子让你移动 ，这三个部分是他们很明显的共性，这便是规律所在。

（这样的规律也是我们使用递归来解决汉诺塔问题的基础。正是因为他们有共性的地方，我们才可以将其共性的地方外包给下一级。）

记住，千万不要试图去纠结 红框 内部的圆盘具体移动方式，这是没有任何规律可循的，想到死也想不出来的。

用递归解决问题

上面我们已经强调过了他们共性的部分是可以外包给下一级的

由此一来我们便可以将 n 个盘子的红框部分 外包 给 下一级的 n-1

n-1 再将自己的红框部分 外包 给 下一级的 n-2

n-2 同样像上面那样外包下去 直至 要动的盘子数为 1，程序便可以执行了

执行完之后，返回上一级执行 ，上一级结束再去上上级 ， 如同多米诺骨牌一样，n == 1 是引起垮塌的关键牌

函数创建

根据我们分析出的汉诺塔特性就可以创建出我们需要的递归函数，我们发现，在外包的时候还是有一些细微的问题需要注意的

比如

将 “4 个盘从a移到c” 中的 “将 3 个盘从 a 移到 b” 的操作 外包 给 “将 3 个盘从 a 移到 c” 时，虽然这是两者共性

本质操作都是一样的，移的都是相同数量的盘子，但是 他们移的目的柱是不一样的，所以我们可以使柱子交换位置（注意这并不是真的交换，这是通过函数参数位置的改变来实现） 总而言之，就是一句话，将 “将 3 个盘从 a 移到 b” 中的 b 柱强行视为 c 柱，通过函数传参就可以实现这种效果。

落实到代码上就是

h(int n,char a,char b,char c) {
    if(n == 1){
        System.out.println(a+"-->"+c);
    }
    h(n-1,a,c,b);
    System.out.println(a+"-->"+c);
    h(n-1,b,a,c);
}

思维图

到此这篇关于Java手把手必会的实例汉诺塔讲解练习的文章就介绍到这了,更多相关Java 汉诺塔 内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • JAVA数据结构之汉诺塔代码实例

    本文实例为大家分享了JAVA数据结构之汉诺塔的具体代码,供大家参考,具体内容如下 package p02.动态链表; import p01.动态数组.Stack; public class LinkedStack<E> implements Stack<E> { private LinkedList<E> list; public LinkedStack(){ list=new LinkedList<>(); } @Override public void

  • Java编程用栈来求解汉诺塔问题的代码实例（非递归）

    [题目] 汉诺塔问题比较经典,这里修改一下游戏规则:现在限制不能从最左侧的塔直接移动到最右侧,也不能从最右侧直接移动到最左侧,而是必须经过中间.求当塔有N层的时候,打印最优移动过程和最优移动总步数. [解答] 上一篇用的是递归的方法解决这个问题,这里我们用栈来模拟汉诺塔的三个塔,也就是不用递归的方法 原理是这样的:修改后的汉诺塔问题不能让任何塔从左直接移动到右,也不能从右直接移动到左,而是要经过中间,也就是说,实际上能做的动作,只有四个:左->中,中->左,中->右,右->中 用栈

  • java 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码 实现效果图 打印的方法在 moveTheTopOne() 方法中被调用,调用该方法前打印出移动的方向--从X号塔往Y号塔 汉诺塔要求:将第一座塔上的所有盘子,借助第二座塔,全部搬运到第三座塔上. 规则:一次只能搬运一个盘子,不准将大盘子落在小盘子上.  汉诺塔实现代码: public class NewHanoi { public static int tiers = 4; // tiers 层数 private static List<String> pago

  • 手把手带你用java搞定汉诺塔

    手把手带你用java搞定汉诺塔

    目录 什么是汉诺塔 问题剖析 n=1 n=2 n=3 小结 Java代码实现 代码讲解 move函数 hanoiTower函数 附:C语言实现汉诺塔 总结 什么是汉诺塔 汉诺塔问题是一个经典的问题.汉诺塔(Hanoi Tower),又称河内塔,源于印度一个古老传说. 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,任何时候,在小圆盘上都不能放大圆盘,且在三根柱子之间一次只能移

  • Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

    Java基于栈方式解决汉诺塔问题实例【递归与非递归算法】

    本文实例讲述了Java基于栈方式解决汉诺塔问题.分享给大家供大家参考,具体如下: /** * 栈方式非递归汉诺塔 * @author zy * */ public class StackHanoi { /** * @param args */ public static void main(String[] args) { System.out.println("我们测试结果:"); System.out.println("递归方式:"); hanoiNormal(

  • Java手把手必会的实例汉诺塔讲解练习

    Java手把手必会的实例汉诺塔讲解练习

    最适合菜鸟的汉诺塔讲解 问题引入 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 让我们先从小事入手. 标记汉诺塔的三根柱子分别为 a ,b ,c 标记汉诺塔上的圆盘分别为:1 ,2,3,4 -n a 柱上面只有一个圆盘时 只有这一种走法 a柱上有两个圆盘时

  • Java 细致图解带你分析汉诺塔

    Java 细致图解带你分析汉诺塔

    目录 一.汉诺塔问题来源 二.问题分析 从简单问题开始 三.解决问题 整体思路 四.婆罗门能否完成大梵天的任务 移动 64 个盘子需要多长时间 计算机移动64个盘子需要多长时间 ? 一.汉诺塔问题来源 汉诺塔(Tower of Hanoi),又称河内塔,是一个源于印度古老传说的益智玩具.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只

  • Java通过递归算法解决迷宫与汉诺塔及八皇后问题

    Java通过递归算法解决迷宫与汉诺塔及八皇后问题

    目录 1.递归的重要规则 2.递归的三个案例 1.老鼠出迷宫 2.汉诺塔 3.八皇后 1.递归的重要规则 在执行一个方法时,就创建一个新的受保护的独立空间(栈空间). 方法的局部变量时独立的,不会相互影响. 如果方法中使用的是应用类型变量(比如数组,对象),就会共享该引用类型的数据. 递归必须向退出递归的条件逼近,否则就是无限递归. 当一个方法执行完毕,或者遇到return,就会返回,遵循谁调用,就将结果返回给谁,同时当方法执行完毕或者返回时,该方法也就执行完毕. 2.递归的三个案例 1.老鼠出

  • java数据结构和算法学习之汉诺塔示例

    复制代码 代码如下: package com.tiantian.algorithms;/** *    _|_1              |                | *   __|__2             |                | *  ___|___3            |                |            (1).把A上的4个木块移动到C上. * ____|____4           |                | *    

  • java基于递归算法实现汉诺塔问题实例

    本文实例讲述了java基于递归算法实现汉诺塔问题.分享给大家供大家参考,具体如下: package test; import java.util.List; import java.util.ArrayList; import java.util.Scanner; import sun.net.www.content.audio.x_aiff; /** * @author 年浩 * */ public class test { public static void move(char x,cha

  • Java数据结构及算法实例：汉诺塔问题 Hanoi

    /** * 汉诺塔大学的时候就学过,但是根本没搞明白,唯一知道的就是要用递归的方法来求解. * 问题描述: * 有三根杆子A,B,C.A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小. * 要求按下列规则将所有圆盘移至C杆: * 1.每次只能移动一个圆盘: * 2.大盘不能叠在小盘上面. * 提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆, * 但都必须尊循上述两条规则. * 问:如何移?最少要移动多少次? * 解决方法: * 假设只有2个盘子,柱子分别是A, B, C柱

随机推荐