目录
1. 汉诺塔游戏简介
2.算法原理
3.循环汉诺塔
1. 汉诺塔游戏简介
汉诺塔游戏是一个经典的数学智力游戏，其目标是将塔上不同大小的圆盘全部移动到另一个塔上，且在移动过程中必须遵守以下规则：
- 每次只能移动一个圆盘
- 较大的圆盘不能放在较小的圆盘之上
2.算法原理
假设是三个塔ABC，A塔上有n个圆盘，求最少需要移动多少次可以将A塔的圆盘全部移到C塔上
设最少移动次数的函数为f（n）
（1）n=1时，只需要一步，直接将A塔上的圆盘移到C塔 即 f（1）= 1
（2）n=2时，，看下图可知 f（2）= 3
（3）n=3时，看下图可知 f（3）= 7
找规律可发现：思路简要如下：将移动步骤分为三步，
a）将最上面的n-1个盘子从A塔移动到B塔上
b）将最大的盘子移动到C塔上
c）再将B塔上的n-1个盘子移动到C塔上
当n=3时：将上面两个圆盘一同移到B塔其实就是n=2时的整个步骤，因为都是将2个圆盘一起移到另一个塔上，那么n=3就可以这样看
a）第1-3步：将上面2个盘放到B塔上，即f（2）步
b）第4步：将最大的盘子移动到C塔上，就+1步
c）第5-7步：将B塔上的2个盘移到C塔上，也是f（2）步
由此推导：n=3时最少移动次数：f（3) = f（2）+1+f（2）=2*f（2）+1
n继续变化推导出：f（n）=2*f（n-1）+1
/**** @param n 代表汉诺塔阶数* @return 返回最少移动次数*/public int getHanoi(int n) {if(n == 1) {return 1;}int[] data = new int[n];data[0] = 1;for(int i = 1; i < n; i++){data[i] = data[i-1] + 1 + data[i-1];}return data[n-1];}3.循环汉诺塔
这题有两问：
（1）把A塔上的所有圆盘都移到B塔所需的最小步数
（2） 把A塔上的所有圆盘都移到C塔所需的最小步数
区别：只能从A->B,B->C,C->A不能随意挪动圆盘
算法原理同上
上图左：f（2） 图右：g（2）
| 移到B塔所需的最小步数：f（n） | 移到C塔所需的最小步数：g（n） | |
| n=1 | 1 | 2 |
| n=2 | 2+1+2=5 | 2+1+1+1+2=7 |
| n=3 | g(2)+1+g(2)=15 | g(2)+1+f(2)+1+g(2)=21 |
此处来分析n=3：怎么找重复子问题
（1）移到B塔所需的最小步数：f（3）
a）将上面2个盘移动C塔：A->B,B->C这个过程其实就是g（2）
b）将最大的盘子移动到B塔上：+1步
c）将C塔上2个盘移动到B塔上：C->A，A->B其实也就是g（2）
（2）移到C塔所需的最小步数：g（3）
a）将上面2个盘移动C塔：A->B,B->C这个过程其实就是g（2）
b）将最大的盘子移动到B塔上：+1步
c）将C塔上面2个盘移动A塔：C->A这个过程其就是f（2）
d）将最大的盘子移动到C塔上：+1步
e）将A塔上面2个盘移动C塔：A->B,B->C这个过程其实就是g（2）
综上进一步推导：
f（n）= 2*g（n-1）+1
g（n）=2*g（n-1）+f（n-1）+2
代码如下：
import java.util.Scanner;// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int mod = 1000000007;int x =1,y = 2;for(int i=2;i<=n;i++) {int xx = x,yy=y;x= (2*yy+1) % mod;y = ((2*yy)%mod+2+xx)%mod;}System.out.print(x+" "+y);}
}
