题目描述
汉诺塔问题,条件如下:
1、这里有A、B、C和D四座塔。
2、这里有n个圆盘,n的数量是恒定的。
3、每个圆盘的尺寸都不相同。
4、所有的圆盘在开始时都堆叠在塔A上,且圆盘尺寸从塔顶到塔底逐渐增大。
5、我们需要将所有的圆盘都从塔A转移到塔D上。
6、每次可以移动一个圆盘,当塔为空塔或者塔顶圆盘尺寸大于被移动圆盘时,可将圆盘移至这座塔上。
请你求出将所有圆盘从塔A移动到塔D,所需的最小移动次数是多少。
题目分析
从经典汉诺塔进行分析 及3个塔 : A经过B移动到C,分为三步:第一.通过C将A上的n-1个圆盘移动到B,A->C->B;第二.将A上剩下的一个圆盘移动到C,A->C;第三.通过A将B上的n-1个圆盘移回C B->A->C。递推方程:p3[j] = p3[j-1]+1;
奇怪的汉诺塔:
同样三步走,第一.A通过C,D将j个圆盘移动到B;第二.通过C将i – j个圆盘移动到D(注意这时B上所有的圆盘都是很小的,不能再放其他圆盘在B上了;第三,B通过A,C将j个圆盘移动到D。递推方程:p4[n] = min(f[n],2 * p4[j] + p3[i-j])。
(递推)
算法竞赛进阶指南 (参考文献)
Java 代码
import java.awt.*;
import java.util.Arrays;
public class Main{
static int i , j;
static int[] p3 =new int[15];
static int[] p4 =new int[15];
public static void main(String[] args) {
fun();
}
public static void fun() {
p3[0] = 0;
for(int i = 1 ;i <= 12 ; i++){
p3[i] = p3[i-1]*2 + 1;
}
Arrays.fill(p4,Integer.MAX_VALUE/2); //初始化数组为最大值
p4[0] = 0;
for(int i = 1 ; i <= 12 ;i++){
for(int j = 0 ;j < i ; j++){
p4[i] = Math.min(p4[i],p4[j]*2+p3[i-j]);
}
}
for (int i = 1 ; i<= 12;i++){
System.out.println(p4[i]);
}
}
}