目录1. 汉诺塔游戏简介2.算法原理3.循环汉诺塔1. 汉诺塔游戏简介汉诺塔游戏是一个经典的数学智力游戏其目标是将塔上不同大小的圆盘全部移动到另一个塔上且在移动过程中必须遵守以下规则每次只能移动一个圆盘较大的圆盘不能放在较小的圆盘之上2.算法原理假设是三个塔ABCA塔上有n个圆盘求最少需要移动多少次可以将A塔的圆盘全部移到C塔上设最少移动次数的函数为fn1n1时只需要一步直接将A塔上的圆盘移到C塔 即 f1 12n2时看下图可知 f2 33n3时看下图可知 f3 7找规律可发现思路简要如下将移动步骤分为三步a将最上面的n-1个盘子从A塔移动到B塔上b将最大的盘子移动到C塔上c再将B塔上的n-1个盘子移动到C塔上当n3时将上面两个圆盘一同移到B塔其实就是n2时的整个步骤因为都是将2个圆盘一起移到另一个塔上那么n3就可以这样看a第1-3步将上面2个盘放到B塔上即f2步b第4步将最大的盘子移动到C塔上就1步c第5-7步将B塔上的2个盘移到C塔上也是f2步由此推导n3时最少移动次数f3) f21f22*f21n继续变化推导出fn2*fn-11那么动态规划算法的代码/** * * 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不能随意挪动圆盘算法原理同上上图左f2 图右g2移到B塔所需的最小步数fn移到C塔所需的最小步数gnn112n22125211127n3g(2)1g(2)15g(2)1f(2)1g(2)21此处来分析n3怎么找重复子问题1移到B塔所需的最小步数f3a将上面2个盘移动C塔A-B,B-C这个过程其实就是g2b将最大的盘子移动到B塔上1步c将C塔上2个盘移动到B塔上C-AA-B其实也就是g22移到C塔所需的最小步数g3a将上面2个盘移动C塔A-B,B-C这个过程其实就是g2b将最大的盘子移动到B塔上1步c将C塔上面2个盘移动A塔C-A这个过程其就是f2d将最大的盘子移动到C塔上1步e将A塔上面2个盘移动C塔A-B,B-C这个过程其实就是g2综上进一步推导fn 2*gn-11gn2*gn-1fn-12代码如下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 i2;in;i) { int xx x,yyy; x (2*yy1) % mod; y ((2*yy)%mod2xx)%mod; } System.out.print(x y); } }