一．起源：
汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。有人造了三根柱子，在一根柱子上从下往上依照大小程序摞着64片黄金圆盘。让上司把圆盘从上面开始按大小程序从新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能挪动一个圆盘。
二．形象为数学问题：
如下图所示，从左到右有A、B、C三根柱子，其中A柱子下面有从小叠到大的n个圆盘，现要求将A柱子上的圆盘移到C柱子下来，期间只有一个准则：一次只能移到一个盘子且大盘子不能在小盘子下面，求挪动的步骤和挪动的次数
解：（1）n == 1
第1次 1号盘 A—->C sum = 1 次
(2) n == 2
第1次 1号盘 A—->B
第2次 2号盘 A—->C
第3次 1号盘 B—->C sum = 3 次
（3）n == 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 sum = 7 次
不难发现法则：1个圆盘的次数 2的1次方减1
2个圆盘的次数 2的2次方减1
3个圆盘的次数 2的3次方减1
。 。 。 。 。
n个圆盘的次数 2的n次方减1
故：挪动次数为：2^n – 1
三．调用办法的栈机制:（特点：先进后出）
从主线程开始调用办法（函数）进行不停的压栈和出栈操作，函数的调用就是将函数压如栈中，函数的完结就是函数出栈的过程，这样就保障了办法调用的程序流，即当函数呈现多层嵌套时，须要从外到内一层层把函数压入栈中，最初栈顶的函数先执行完结（最内层的函数先执行完结）后出栈，再倒数第二层的函数执行完结出栈，到最初，第一个进栈的函数调用完结后从栈中弹出回到主线程，并且完结。
四．算法剖析（递归算法）：
咱们在利用计算机求汉诺塔问题时，必不可少的一步是对整个实现求解进行算法剖析。到目前为止，求解汉诺塔问题最简略的算法还是同过递归来求，至于是什么是递归，递归实现的机制是什么，咱们说的简略点就是本人是一个办法或者说是函数，然而在本人这个函数里有调用本人这个函数的语句，而这个调用怎么能力调用完结呢？，这里还必须有一个完结点，或者具体的说是在调用到某一次后函数能返回一个确定的值，接着倒数第二个就能返回一个确定的值，始终到第一次调用的这个函数能返回一个确定的值。
实现这个算法能够简略分为三个步骤：
（1） 把n-1个盘子由A 移到 B；
（2） 把第n个盘子由 A移到 C；
（3） 把n-1个盘子由B 移到 C；
从这里动手，在加上下面数学问题解法的剖析，咱们不难发现，移到的步数必然为奇数步：
（1）两头的一步是把最大的一个盘子由A移到C下来；
（2）两头一步之上能够看成把A上n-1个盘子通过借助辅助塔（C塔）移到了B上，
（3）两头一步之下能够看成把B上n-1个盘子通过借助辅助塔（A塔）移到了C上；
五，java源代码：
package com.self;
import java.util.Scanner;
public class TowersOfHanoi {
/**
*标记挪动次数 */ static int m = 0;
/**
* 实现挪动的函数 * * @param disks 盘子编号
* @param from 挪移地位
* @param to 指标地位
*/ public static void move(int disks, char from, char to) {
System.out.println("第" + (++m) + " 次挪动 : " + " 把 " + disks + " 号圆盘从 " + from + " ->移到-> " + to);
}
/**
* 递归实现汉诺塔的函数 * * @param n
* @param A
* @param B
* @param C
*/
public static void hanoi(int n, char A, char B, char C) {
//圆盘只有一个时，只需将其从A塔移到C塔
if (n == 1) {
//将编b号为1的圆盘从A移到C
TowersOfHanoi.move(1, A, C);
}
//否则
else {
//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
hanoi(n - 1, A, C, B);
//把A塔上编号为n的圆盘移到C上
TowersOfHanoi.move(n, A, C);
//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
hanoi(n - 1, B, A, C);
}
}
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
char A = 'A';
char B = 'B';
char C = 'C';
System.out.println("******************************************************************************************");
System.out.println("这是汉诺塔问题（把A塔上编号从小号到大号的圆盘从A塔通过B辅助塔挪动到C塔下来");
System.out.println("******************************************************************************************");
System.out.print("请输出圆盘的个数：");
int disks = input.nextInt();
TowersOfHanoi.hanoi(disks, A, B, C);
System.out.println(">>挪动了" + m + "次，把A上的圆盘都挪动到了C上");
input.close();
}
}; “复制代码”)
六．图解程序运行流程：
（1）函数hanoi(int n,char A,char B,char C)的性能是把编号为n的圆盘借助B从A挪动到 C上。
（2）函数move(int n ,char N ,char M)的性能是把1编号为n的圆盘从N 移到M上
七．程序运行截图：
发表回复