Java递归来实现汉诺塔游戏,注释详细

我们很容易能想到，可以用递归来实现汉诺塔游戏。因为要将n（n>1)个盘子从“源”柱子移到“目标”柱子，我们要先把n-1个盘子从“源”柱子移到“辅助”柱子上，然后把最底下那一个盘子移到目标柱子上，最后把“辅助柱”上的n-1个盘子移动到目标柱子上。n==1时直接移到目标柱上，也是递归的出口。

有了以上思路的铺垫，就可以开始实现代码了。

public class HanoiDemo {
    public static int hanoiCalledCount = 0;//成员变量记录操作次数

    //汉诺塔游戏是一种二路递归
    public static void main(String[] args) {
        hanoi(3,"A","B","C");
        System.out.println("执行"+hanoiCalledCount+"步");
    }

    public static void hanoi(int n,String source,String target,String assist){
        if(n<=0){
            System.out.println("n要大于零");
        }
        if(n==1){//递归的出口，n==1时直接移到目标柱上
            System.out.printf("把一个盘子从%s柱子上移动到%s柱子上\n",source,target);
            hanoiCalledCount++;//计数器加一
        }else{
            //先把n-1个盘子从“源”柱子移到“辅助”柱子上
            hanoi(n-1,source,assist,target);
            //把最底下那一个盘子移到目标柱子上
            System.out.printf("把一个盘子从%s柱子上移动到%s柱子上\n",source,target);
            hanoiCalledCount++;//计数器加一
            //把“辅助柱”上的n-1个盘子移动到目标柱子上
            hanoi(n-1,assist,target,source);
        }
    }
}

运行结果如下，大家可以尝试验证一下是否正确。

当n==2时，要操作3次

当n==3时，要操作7次

当n==4时，要操作15次

相信大家已经猜出规律了，操作次数==n^2-1

可见，随着盘子个数n的增加，操作次数以n^2增加，所以，自己玩汉诺塔游戏的是时候建议数字不要超过20。

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持我们。

赞 (0)

相关推荐

  • Java 实现一个汉诺塔实战练习

    Java 实现一个汉诺塔实战练习

    汉诺塔简介: 我们想要实现的是 让 A柱上的盘子,移动到C柱上 1层汉诺塔 2层汉诺塔 3层汉诺塔详解图 第一步 第二步 第三步 第四步 第五步 第六步 第七步 经过上面的图解,相比大家一定在一定程度了解到汉诺塔的游戏规则,以及怎么去玩. 总之 最终C柱上第一个盘子,是最大,最顶的是最小的,而且在操作过程中,前几步就是为了让三个柱子中最大的盘子移动到C柱上, 然后不断,将它两个柱子中最大盘子往上累加,(盘子从大到小,从下往上摆放) 而且盘子一多,你就会发现过程中间,除了最大的盘子,其余的盘子都会

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

    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,当然,

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

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

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

  • 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 汉诺塔详解及实现代码

    java 汉诺塔详解及实现代码

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

  • Java递归来实现汉诺塔游戏,注释详细

    Java递归来实现汉诺塔游戏,注释详细

    我们很容易能想到,可以用递归来实现汉诺塔游戏.因为要将n(n>1)个盘子从"源"柱子移到"目标"柱子,我们要先把n-1个盘子从"源"柱子移到"辅助"柱子上,然后把最底下那一个盘子移到目标柱子上,最后把"辅助柱"上的n-1个盘子移动到目标柱子上.n==1时直接移到目标柱上,也是递归的出口. 有了以上思路的铺垫,就可以开始实现代码了. public class HanoiDemo { public sta

  • c# 实现汉诺塔游戏

    汉诺塔游戏一旦掌握了规律,其实是有点单调和无聊的,不过却是学习递归的一个绝佳例子,想当初学习老谭C的时候,就卡在这儿好长时间. 对初学编程的人来说,递归本身就不易理解,如果使用C语言没有好的调试环境就更难去理解了.在这方面,VS调试输出是真方便,一目了然. 但要想理解递归求解汉诺塔,还是得先玩一玩游戏本身,有点感受.另外,设计一下这个游戏也可以加深对它的理解,同时还可以对数据结构中的栈有一个简单的认识. 因为汉诺塔的游戏规则本身就是一个栈,只能从平台最上面取走碟子,然后放在另一个平台最上面,这明

  • python 实现汉诺塔游戏

    一.汉诺塔问题 1. 问题来源 问题源于印度的一个古老传说,大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘.大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 2. 问题阐述 塔内有三个座A.B.C,A座上有64个盘子,盘子从上到下逐渐变大,最下面的盘子最大.目前要把A座的64个盘子从A座移到C座,并且每次只能移动一个盘子,移动过程中三个座保持大盘子在下,小盘子在上,

  • python求解汉诺塔游戏

    本文实例为大家分享了python求解汉诺塔游戏的具体代码,供大家参考,具体内容如下 一.问题定义 百度百科定义:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具.据说大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照从小到大顺序摞着64片黄金圆盘.大梵天命令婆罗门借助其中一根柱子,把64片黄金圆盘重新摆放到第三个根柱子上.并且规定,在小黄金圆盘上不能放大的黄金圆盘,在三根柱子之间一次只能移动一个圆盘. 例如,如果黄金圆盘只有3片,则为了满足游戏规则,那么必须按照如下图所示的

  • 利用python实现汉诺塔游戏

    利用python实现汉诺塔游戏

    本文实例为大家分享了python实现汉诺塔游戏的具体代码,供大家参考,具体内容如下 一.汉诺塔 汉诺塔问题是一个经典的递归问题,对于这个问题,我们可以把它简单的去看成是如何用n-1去表示n. 在A,B,C三个柱子上,我们先假设A柱上只有两个盘子,那么很简单,只需要把最上面的那个盘子移到B柱上,再把A柱上最下面的盘子移到C柱上,最后把B柱的盘子移到C柱就可以了. 假设我们有n个盘子,那么可以把最下面的盘子看成是第n个盘子,而我们要做的是把上面n-1个盘子移到B柱上,再把第n个盘子移到C柱.我们可以

  • Java用递归方法解决汉诺塔问题详解

    Java用递归方法解决汉诺塔问题详解

    目录 前言 一.问题描述 二.问题分析 三.解决方案 四.示例 前言 博主之前有写过关于递归问题的思维模式: 递归的思路 下面将用这种思维模式来求解经典汉诺塔问题. 一.问题描述 汉诺塔(又称河内塔)问题是源于印度一个古老传说.大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘. 大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上. 并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘. 问应该如何操作? 玩法如下: 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

  • C语言递归思想实现汉诺塔详解

    C语言递归思想实现汉诺塔详解

    目录 1.递归思想简介 2.汉诺塔问题 3.汉诺塔递归的c语言实现 总结 1.递归思想简介 在c语言中,程序调用自身的编程技巧称为递归( recursion). 递归的定义看上去似乎很抽象,使用代码描述能够让人容易理解,下面是一个函数递归的例子. /* 递归求n的阶乘 */ int factorial(int n) //定义一个求阶乘的函数叫做factorial(),需要一个整形参数,返回一个整形值 { if (n <= 1) //递归结束的条件 { return 1; } else { ret

  • C语言编写汉诺塔游戏

    C语言编写汉诺塔游戏

    目录 汉诺塔的游戏规则: 当A只有一个环的时候: 当A只有两个环的时候: 当A只有三个环的时候: 思路: 当n=1时: 当n=2时: 当n=3时: 当n=4时: 见代码 运行截图总结 汉诺塔的游戏规则:   有三根金刚石柱子A.B.C,在A柱子上从下往上按照大小依次减小的顺序摞着64片黄金环.大梵天命令婆罗门把环从下面开始按大小顺序重新摆放在另一根柱子上.并且规定,在任何一个柱子上,小环上不能放大环,在三根柱子之间一次只能移动一个环. 即将A柱子上全部的环通过C柱子(C柱子作为中介)移动到B柱子

  • C语言实现汉诺塔游戏

    C语言实现汉诺塔游戏

    操作就是:A B 号码A的塔顶一层放在号码B的塔顶.如1(空格) 3 回车. 话说有人能把我这C的代码添加到QT界面框架上去么?  代码写的不好 ,维护性不够,只能玩8层的,写完以后发现很难拓展,软件工程,设计模式有待提高.... 里面提示输入等级的装B用了,没有实现,大家随便输入个个位数就可以玩了. stackfunc.c #include"STACK.h" #include<stdio.h> extern ceng CENG[SIZE]; //数据入栈 void pus

随机推荐