java 汉诺塔详解及实现代码

java 汉诺塔详解及实现代码

实现效果图

打印的方法在 moveTheTopOne() 方法中被调用,调用该方法前打印出移动的方向--从X号塔往Y号塔

汉诺塔要求:将第一座塔上的所有盘子,借助第二座塔,全部搬运到第三座塔上。

规则:一次只能搬运一个盘子,不准将大盘子落在小盘子上。

 汉诺塔实现代码:

public class NewHanoi {
  public static int tiers = 4; // tiers 层数
  private static List<String> pagoda1 = new ArrayList<String>(); // 静态指针
  private static List<String> pagoda2 = new ArrayList<String>();

  private static List<String> pagoda3 = new ArrayList<String>(); 

  // 映射,用来确定并打印塔的序号(使用角标),也可以使用 Map

  private static List[] mapping = {pagoda1, pagoda2, pagoda3};

  public static void main(String[] args) {
    preparePagoda(pagoda1, tiers);
    System.out.println("初始状态:");
    printPagodas();
    hanoi(tiers, pagoda1, pagoda2, pagoda3);
    System.out.println("最后结果:");
    printPagodas();
  }
  // --准备盘子(添加-字符串) (源塔)上
  private static void preparePagoda(List<String> srcPagoda, int tiers) {

    // 用于拼装塔层的容器
    StringBuilder builder = new StringBuilder();

    // 源塔的每一层加盘子,从底层开始, i ‘代表'盘子的直径大小,等于组成盘子的"^"个数
    for(int i = tiers; i > 0; i--){      

      // 每一层由 2*tiers-1 个格子组成,代表盘子大小的"^"格子由空格隔开
      for(int k = 0; k < tiers - i; k++) builder.append(" "); // 盘子左边的空格,数量为 [2*tiers-1-(2*i-1)]/2 = tiers-i, 右边相同
      for(int j = 1; j <= 2*i-1; j++){    // 盘子所占格数
        if(j % 2 == 1) builder.append("^"); // 间隔摆放

        else builder.append(" ");
      }
      for(int k = 0; k < tiers - i; k++) builder.append(" "); // 盘子右边的空格

      srcPagoda.add(builder.toString());  // 添加到塔上
      builder.delete(0, builder.length()); // 下一循环前清空容器
    }
  }
  // --打印塔的现状

  private static void printPagodas(){

     // 打印层数为三座塔-现状的最大高度
    int len = Math.max(pagoda1.size(), Math.max(pagoda2.size(), pagoda3.size()));
    // 用于-塔的空层显示

    StringBuilder spaces = new StringBuilder();
    spaces.append("-");  // --添加塔的左外框
    for(int i = 0; i < 2*tiers-1; i++) spaces.append(" "); // 空层显示用空格
    spaces.append("-\t"); // --添加塔的右外框和塔间间隔    

    for(int i = len - 1; i >= 0; i--){ // 从顶层开始      

      // 三座塔同一水平面的塔层放在同一行显示
      // 当某个塔不存在此层时,List.get(index)会抛角标越界异常,使用try-catch处理:此层显示一层空格
      try { System.out.print("-" + pagoda1.get(i) + "-\t");
      } catch (Exception e1) { System.out.print(spaces);
      }
      try { System.out.print("-" + pagoda2.get(i) + "-\t");
      } catch (Exception e) { System.out.print(spaces);
      }
      try { System.out.print("-" + pagoda3.get(i) + "-\t");
      } catch (Exception e) { System.out.print(spaces);
      }
      System.out.print("\r\n");
    }
  }
  // 这个方法(递归的核心方法)从指定的源塔上移动-指定数量的盘子-到指定的目标塔上

  public static void hanoi(int moveNum, List<String> from, List<String> middle, List<String> to) {
    if(moveNum == 1){ // 递归到移动一个盘子时,使用 move 方法
      moveTheTopOne(from, to);
      return;
    }

    // 将实现分为三步,一,将源塔底盘上方的所有盘子移至中间塔(递归);二,将底盘移到目标塔;三,将中间塔上的所有盘子移到目标塔上(递归)。
    hanoi(moveNum - 1, from, to, middle);
    moveTheTopOne(from, to);
    hanoi(moveNum - 1, middle, from, to);
  }
  // 方法的名字就是他的作用
  private static void moveTheTopOne(List<String> from, List<String> to) {
    String theTopOne = from.remove(from.size() - 1);
    to.add(theTopOne);

    // 打印图形,每移动一下,打印图形显示
    System.out.println("********** print ***********\r\n");
    // 确定塔的序号
    int fromNum = 0, toNum = 0;
    for (int i = 0; i < mapping.length; i++) { // 遍历塔的数组

      if (mapping[i] == from) {
         fromNum = i+1;
      }
      if (mapping[i] == to) {
         toNum = i+1;
      }
    }
    System.out.println("从 " + fromNum + " 号塔往 " + toNum + " 号塔\r\n");

    printPagodas(); // 打印图形
  }
}

感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • Java算法之递归算法计算阶乘

    本文为大家分享的java算法计算阶乘,在学习Java课程时经常会遇到求阶乘问题,今天接跟大家一起探讨一下 代码如下: package com.xu.main; import java.util.Scanner; public class P9 { static long fact(int n) { if(n <= 1) { return 1; } else { return n * fact(n - 1); } } public static void main(String[] args) {

  • java 汉诺塔Hanoi递归、非递归(仿系统递归)和非递归规律 实现代码

    程序如下: 复制代码 代码如下: View Code  /*  * Hanoi塔游戏 问题描述:  * 汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.  * 大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照  * 大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小  * 顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在  * 三根柱子之间一次只能移动一个圆盘.  *   * fuction:实现 hanoi塔  *       

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

    java 实现汉诺塔详解及实现代码 汉诺塔问题:有三根柱子A,B,C,其中A上面有n个圆盘,从上至下圆盘逐渐增大,每次只能移动一个圆盘,并且规定大的圆盘不能叠放在小的圆盘上面,现在想要把A上面的n个圆盘全部都移动到C上面,输出移动的总步数以及移动的过程 分析: //先求出移动的总步数 1,假设g(n)表示n个圆盘时的移动总的步数,当n=1时,g(1)=1; 2.现在可以把g(n)进行细分为三步: 1>先将n-1个圆盘从A通过C移动到B上面,相当于将n-1个圆盘从A移动到C,因此需要g(n-1)步

  • java求解汉诺塔问题示例

    思路如下: 要实现3阶汉诺塔的求解步骤,也就是说初始状态时,A上从上到下有三个盘子,分别为1号盘.2号盘和3号盘,其中1号盘最小,3号盘最大:判断剩余盘子个数,如果只有一个盘子就退出迭代,如果有大于一个盘子就继续迭代.代码如下: 复制代码 代码如下: public class HanoiTower {    public static void moveDish(int level, char from, char inter, char to) {        if (level == 1)

  • 快速排序算法原理及java递归实现

    快速排序 对冒泡排序的一种改进,若初始记录序列按关键字有序或基本有序,蜕化为冒泡排序.使用的是递归原理,在所有同数量级O(n longn) 的排序方法中,其平均性能最好.就平均时间而言,是目前被认为最好的一种内部排序方法 基本思想是:通过一躺排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列. 三个指针: 第一个指针称为pivotkey指针(枢轴),第二个指

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

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

  • 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基于循环递归回溯实现八皇后问题算法示例

    本文实例讲述了Java基于循环递归回溯实现八皇后问题.分享给大家供大家参考,具体如下: 运行效果图如下: 棋盘接口 /** * 棋盘接口 * @author Administrator * */ public interface Piece { abstract boolean isRow(int line); abstract boolean isCol(int line,int col); } 棋盘类: /** * 棋盘 * @author Administrator * */ public

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

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

  • Java递归算法经典实例(经典兔子问题)

    题目:古典问题:3个月起每个月都生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少? 分析:首先我们要明白题目的意思指的是每个月的兔子总对数:假设将兔子分为小中大三种,兔子从出生后三个月后每个月就会生出一对兔子, 那么我们假定第一个月的兔子为小兔子,第二个月为中兔子,第三个月之后就为大兔子,那么第一个月分别有1.0.0,第二个月分别为0.1.0, 第三个月分别为1.0.1,第四个月分别为,1.1.1,第五个月分别为2.1.2,第六个月分别为3.2.3,第

  • Java使用递归法解决汉诺塔问题的代码示例

    汉诺(Hanoi)塔问题:古代有一个梵塔,塔内有三个座A.B.C,A座上有n个盘子,盘子大小不等,大的在下,小的在上(如图). 有一个和尚想把这n个盘子从A座移到B座,但每次只能允许移动一个盘子,并且在移动过程中,3个座上的盘子始终保持大盘在下,小盘在上.在移动过程中可以利用B座,要求打印移动的步骤.如果只有一个盘子,则不需要利用B座,直接将盘子从A移动到C. 如果有2个盘子,可以先将盘子1上的盘子2移动到B:将盘子1移动到c:将盘子2移动到c.这说明了:可以借助B将2个盘子从A移动到C,当然,

随机推荐