这个笔记主要是写两个移动方法的汉诺塔问题。
问题1：Problem - 2064
思路分析：
汉诺塔的模型如上图所示
我们可以把规模为n的问题分解为规模为n-1的问题来分析：
假设a[n]是按照题意从A到C的移动步数。具体移动过程如下：
（以下分析都是将n-1个模块看成一个整体）
（1）将n-1个模块从A移动到C，移动步数为a[n-1]；
（2）将第n个模块从A移动到B，移动步数为1；
（3）将n-1个模块从C移动到A，移动步数为a[n-1];
（4）将第n个模块从B移动到C，移动步数为1；
（5）将n-1个模块从A移动到C，移动步数为a[n-1]
综上可以推导出，移动步数a[n]的公式为：
具体实现：
import java.util.Scanner;
public class Test_2064 {
public static void main (String args[]) {
Scanner in = new Scanner(System.in);
while(in.hasNextInt()) {
int n = in.nextInt();
long a[] = new long[36];
a[0] = 0;
for(int i=1;i<=n;i++) {
a[i] = 3 * a[i-1] + 2;
}
System.out.println(a[n]);
}
}
}
问题2：Problem - 2077
思路分析：
这道题可以按照上一道题（汉诺塔3）的思路继续做下去。
根据上一道题的分析，a[n]的推导公式为
但是，这道题的题意允许最大的模块放在n-1个模块上面，因此，移动过程如下：
（以下分析都是将n-1个模块看成一个整体）
（1）将n-1个模块从A移动到B；
（2）将第n个模块从A移动到B；
（3）将第n个模块从B移动到C；
（4）将n-1个模块从B移动到C
而“将n-1个模块从A移动到B”、“将n-1个模块从B移动到C”这两步可以看做“将n-1个模块从A移动到C”，那么移动步数还是a[n-1]；
综合以上的分析，这道题的移动步数f[n]就是在a[n-1]的基础上移动两步，
具体实现：
import java.util.Scanner;
public class Test_2077 {
public static void main (String args[]) {
Scanner in = new Scanner(System.in);
int m = in.nextInt();
while(m-- > 0) {
int n = in.nextInt();
long a[] = new long[21];
a[0] = 0;
for(int i=1;i<=n;i++) {
a[i] = 3*a[i-1]+2;
}
System.out.println(a[n-1]+2);
}
}
}
