文档章节

汉诺塔算法的理解

z_jordon
 z_jordon
发布于 2015/04/18 12:27
字数 501
阅读 970
收藏 11

当盘子数为两个时,移动图如下:

移动规律为:

步骤 盘子编号 源柱子 目标柱子
1 1
A B
2 2 A C
3 1 B C

当盘子数为3个时:

移动规律为:

步骤 盘子编号 源柱子 目标柱子
1 1 A C
2 2 A B
3 1 C B
4 3 A C
5 1 B A
6 2 B C
7 1 A C

从以上移动移动规律可以总结出,当步骤序号和盘子数目相同时,就是把最底下的盘子从A移动到C,其它的步骤都是对等的,规律如下:

  1. 中间以上动作是:源柱子(A)不变,目标柱子为C,辅助柱子为B进行移动,也就是

    源柱子->目标柱子

    源柱子->辅助柱子

    目标柱子->辅助柱子

  2. 中间动作:从A到C也就是从源柱子到目标柱子

  3. 中间以下动作:源柱子是B,目标柱子为C,辅助柱子为A进行移动,也就是

    源柱子->辅助柱子

    源柱子->目标柱子

    辅助柱子->目标柱子

按照以上规律,可以大概总结出实际上移动的主要动作实际上就是在重复三步动作,用java代码可以表示如下:

/**
 * @author lenovo
 *
 */
public class Hanoi {
    /**
    * 
    * @param n 盘子的数目
    * @param origin 源座
    * @param assist 辅助座
    * @param destination 目的座
    */
    public void hanoi(int n, char origin, char assist, char destination) {
    	if (n >= 1) {
    		hanoi(n - 1, origin, destination, assist);
    		System.out.println("Direction:" + origin + "--->" + destination);
    		hanoi(n - 1, assist, origin, destination);
    	}
    }
 
    public static void main(String[] args) {
        Hanoi hanoi = new Hanoi();
        hanoi.hanoi(3, 'A', 'B', 'C');
    }
}

一开始我理解这个算法的时候老是一直在分析程序的出栈,入栈动作,后面看了这篇文章汉诺塔的递归算法与解析才有点恍然大悟,这个算法实际上是考验对递归思想的理解:总结事物的规律,然后再用程序表达出来。

© 著作权归作者所有

z_jordon
粉丝 36
博文 251
码字总数 78212
作品 0
厦门
技术主管
私信 提问
加载中

评论(1)

wxie
wxie
至于吗?不是有公式?
递归——汉诺塔

文章作者:Tyan 博客:noahsnail.com | CSDN | 简书 1. 递归 一个函数调用其自身,就是递归。 2. 汉诺塔 问题描述 有一个梵塔,塔内有三个座A、B、C,A座上有诺干个盘子,盘子大小不等,大的...

Quincuntial
2017/12/28
0
0
汉诺塔算法和背后的数据结构

汉诺塔是有算法的。 很多问题都有解决办法,汉诺塔也不例外。如果汉诺塔的算法符合 Introduction to algorithms 这本书的观点:在计算机出现以前就有了算法,只不过计算机的出现带来了更多的...

刘思宁
2018/01/10
0
0
汉诺塔自动解题动画中的iOS开发技巧

引 前段时间做了一道题,要求实现汉诺塔游戏的自动解题动画: 汉诺塔游戏应该都了解规则: 1、将盘子全部移动到塔C 2、每次只能移动一个圆盘; 3、大盘不能叠在小盘上面。 要求由用户输入盘子...

cloudox_
2017/05/18
0
0
php 经典的算法题你懂的

有5个人偷了一堆苹果,准备在第二天分赃。晚上,有一人遛出来,把所有菜果分成5份,但是多了一个,顺手把这个扔给树上的猴了,自己先拿1/5藏了。没想到其他四人也都是这么想的,都如第一个人...

zchd
2013/06/17
0
0
堆栈的应用——用JavaScript描述数据结构

栈(stack)又名堆栈,它是一种运算受限的线性表。其限制是仅允许在表的一端进行插入和删除运算。这一端被称为栈顶,相对地,把另一端称为栈底。 一、实现一个栈类Stack 基于堆栈的特性,可以...

我是leon
2018/08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

OSChina 周日乱弹 —— 我,小小编辑,食人族酋长

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @宇辰OSC :分享娃娃的单曲《飘洋过海来看你》: #今日歌曲推荐# 《飘洋过海来看你》- 娃娃 手机党少年们想听歌,请使劲儿戳(这里) @宇辰OSC...

小小编辑
今天
546
10
MongoDB系列-- SpringBoot 中对 MongoDB 的 基本操作

SpringBoot 中对 MongoDB 的 基本操作 Database 库的创建 首先 在MongoDB 操作客户端 Robo 3T 中 创建数据库: 增加用户User: 创建 Collections 集合(类似mysql 中的 表): 后面我们大部分都...

TcWong
今天
31
0
spring cloud

一、从面试题入手 1.1、什么事微服务 1.2、微服务之间如何独立通讯的 1.3、springCloud和Dubbo有哪些区别 1.通信机制:DUbbo基于RPC远程过程调用;微服务cloud基于http restFUL API 1.4、spr...

榴莲黑芝麻糊
今天
17
0
Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
51
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
58
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部