汉诺塔详解(包看包会)
- 汉诺塔详解(包看包会) 推荐度:
- 相关推荐
汉诺塔详解(包看包会)
CSDN的大佬已经解释了很多了,由我这个菜鸟反复理解后得到的一些心得的分享
先看题:
汉诺塔: 汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
如图,我们移动两个盘子,分为三步,A-> B A->C B->C
那么三层呢?
三层看起来比较复杂,但是如果把圆圈内盘子当做一个呢?
这是不是就清晰了?
我们只需要重复只有“两个盘子”移动的步骤就可以得出这个解;
即:A->B A->C B->C
那么,上面两个盘子如何移动到B柱上呢?
移动方法:
分为三步:A ->C A->B C->B 这就把a和b的盘子移动到B柱子上了:
再次执行 A->C 那么这个最大的盘子就到C了。
那么B有两个盘子如何操作才能到C柱上呢?
我们看一下下面的图,对比一下上面的图:
C柱那个最大的盘子已经是最大的了,可以直接忽略不计,那么就会发现其实把上图A B柱交换就是下图了;
如此,发现规律了吗?
只有三步:
第一步:把n-1个盘子(最大盘子以上的盘子)移动到B上,
第二步:把第N个盘子(最大的盘子)移动C上
第三步:然后把n-1个盘子(最大盘子以上的盘子)移动C上;
递归在哪?
n-1就需要把n-2个盘子当做一个来弄,
n-2就需要把n-3当做一个来看,
一直递归直到只有一个的时候A->C
怎么移动?
把n-1个盘子移动到B柱上 需要借助C柱;
然后A柱最大的盘子放到C柱上;
把n-1个盘子从B柱移动到C柱上,需要借助B柱;
那么代码就特别好理解了:
import java.util.Scanner;
public class Hanota{
public static void main(String[] args){System.out.println("请输入汉诺塔圆盘数:");Scanner sc=new Scanner(System.in);int n=sc.nextInt();new Hanota().hm(n,'A','B','C'); //调用,输入柱子的名字和盘子的个数;}private void hm(int m,char a,char b,char c){if(m == 1){//当递归到最后一个盘子,直接把A盘的移动到C盘上;System.out.println(a+"-->"+c); }else{//把 m-1上面的盘子从A柱借助C柱放置B柱hm(m-1,a,c,b); System.out.println(a+"-->"+c); //把A柱上的盘子(最大那个)移动到C盘//把m-1个盘子从B柱借助A柱放置在C柱上hm(m-1,b,a,c); }}
}
如此理解,三步论,就是这样递归出来的,觉得写的不错的,请点个赞,觉得有什么不足的请指出。
- Java 接口+继承
- 第二关,KPM算法和next函数值
- KPM匹配算法
- matlab中求矩阵A的特征向量,matlab层次分析法求特征值及特征向量.doc
- js编码书写规范(自学习用)
- filter
- NFS服務器
- RabbitMQ
- JMeter怎么用
- 谱分析——傅里叶级数(离散谱)
- window安装Linux
- C#使用EmguCV库(图像读取、显示、保存)(二)
- python thinker
- 【Android开发】App消息中心构建
- 数组排序(升序)
- Centos安装janus
- Msfvenom使用指南
- 我的Hadoop安装流程
- 【结构体】 结构体引用、结构体数组指针、包含结构的结构体
- ROS——roscpp