主页 > Java教程 > Java 汉诺塔

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

  • 更新时间:
  • 编辑:双弘致
  • 2498人关注

汉诺塔,传说神在创造世界的时候做了三根金刚石柱子,并在一个教塔里留下了三根金刚石棒,第一根上面从上到下套着64个按从小到大排列的金盘,神命令庙里的众僧将它们一个个地从这根金刚石棒搬到另一根金刚石棒上,大盘不能放在小盘上。最后64个金盘仍然要按从小到大排列,另外这篇文章主要知识点是关于Java、汉诺塔、Java、练习、Java 汉诺塔的内容,如果大家想对相关知识点有系统深入的学习,可以参阅以下电子资料:

参考资料
资料:
完整Java从小白到大牛 源码版
大小:
15.6MB
类别:
Java电子资源立即下载

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

今天在网上看到《Java手把手必会的实例汉诺塔讲解练习》,感觉很有用处,把程序员重写的代码发布到这里,觉得好就请收藏下。

最适合菜鸟的汉诺塔讲解

问题引入

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

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

让我们先从小事入手。

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

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

a 柱上面只有一个圆盘时

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

只有这一种走法

a柱上有两个圆盘时

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

a柱上有三个圆盘时

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

a柱上有四个圆盘时

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

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

第一部分为 第一个红框,用于将 前 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手把手必会的实例汉诺塔讲解练习的文章就介绍到这了,更多相关Java 汉诺塔 内容请搜索java学习网以前的文章或继续浏览下面的相关文章希望大家以后多多支持java学习网!

相关内容

知识点补充

小编:蒯嘉慕 23小时43分钟前编辑补充

兴业银行java笔试题精选

: 大家一定都听说过兴业银行,在银行工作待遇也是很不错的,想入职银行做java程序员也需要通过 java笔试题 才可以。“www.javaxue.com”java培训机构的小编为大家准备了兴业银行java笔试题精选,大家可以作为参考。 1、下面哪些是Thread类的方法() A start() B run() C exit() D getPriority() 答案:ABD 2、下面关于java.lang.Exception类的说法正确的是() A 继承自Throwable B Serialable CD 不记得,反正不正确 答案:A 3、下面程序的运行结果是() String str1 = hello; String str2 = he + new String(llo); System.err.println(str1 == str2); 答案:false 4、下列说法正确的有() A. class中的constructor不可省略 B. constructor必须与class同名,但方法不能与class同名 C. cons……

小编:赖靖琪 10小时28分钟前编辑补充

java使用this调用构造函数的实现方法示例

: 本文实例讲述了java使用this调用构造函数的实现方法。分享给大家供大家参考,具体如下: 一 点睛 如果在程序中想用某一个构造函数调用另一个构造函数,也可以用 this 来实现。 二 实战 1 代码 class Person{ String name; int age; public Person() { System.out.println("1. public Person()"); } public Person(String name, int age) { // 调用本类中无参构造方法 this(); this.name = name; this.age = age; System.out.println("2. public Person(String name,int age)"); }}public class ThisConstructor{ public static void main(String[] args) { new Person("张三", 25); }} 2 运行 1. public Person() 2. public Person(String name,int age) 3 说明 程序中先调用了Person中有两个参数的构造方法,但此构造方法中的 th……