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，当然，也可以借助C将2个盘子从A移动到B。
  • 如果有3个盘子，那么根据2个盘子的结论，可以借助c将盘子1上的两个盘子从A移动到B；将盘子1从A移动到C，A变成空座；借助A座，将B上的两个盘子移动到C。这说明：可以借助一个空座，将3个盘子从一个座移动到另一个。
  • 如果有4个盘子，那么首先借助空座C，将盘子1上的三个盘子从A移动到B；将盘子1移动到C，A变成空座；借助空座A，将B座上的三个盘子移动到C。

Java代码如下：

public class Hanoi { 

 public static void main(String[] args) {
  int disk = 3; //盘子
  move(disk, 'A', 'B', 'C');
 } 

 /*
  * 根据题意，从上向下编号 => 1 ~ n
  */
 /**
  *
  * @param topN 源塔顶的盘子编号
  * @param from 从哪个塔移动
  * @param inter 中介，过渡的塔
  * @param to 目的塔
  */
 private static void move(int topN, char from, char inter, char to) {
  if (topN == 1) {
   System.out.println("Disk 1 from " + from + " to " + to);
  } else {
   move(topN - 1, from, to, inter);
   System.out.println("Disk " + topN + " from " + from + " to " + to);
   move(topN - 1, inter, from, to);
  }
 } 

}

out

Disk 1 from A to C
Disk 2 from A to B
Disk 1 from C to B
Disk 3 from A to C
Disk 1 from B to A
Disk 2 from B to C
Disk 1 from A to C
赞 (0)

相关推荐

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

    Java基于循环递归回溯实现八皇后问题算法示例

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

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

    java 汉诺塔详解及实现代码

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

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

    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求解汉诺塔问题示例

    思路如下: 要实现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基于递归算法实现汉诺塔问题实例

    本文实例讲述了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柱

  • Java递归算法经典实例（经典兔子问题）

    Java递归算法经典实例（经典兔子问题）

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

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

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

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

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

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

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

随机推荐