MENU

奇怪的汉诺塔

February 19, 2019 • Read: 3206 • 算法阅读设置

首先打表出只有三根柱子时1~12个圆盘所需的次数,思路是这样的,对于三根柱子,首先将前i-1个圆盘移动到某一根柱子,然后将最后一个圆盘移动到一根柱子,最后再将剩下的i-1个圆盘移动到一根柱子,所以three[i] = three[i - 1] + 1 + three[i - 1]

对于四根柱子来说,枚举前j个圆盘,首先将前j个圆盘移动到四根柱子种的某一根,次数是four[j],然后将剩下的i-j个圆盘移动到剩下的三根柱子,次数是three[i-j](为什么是三根柱子,因为之前已经有一根柱子被占用了,所以这里即使有四根柱子,也只有三根能用),最后再将那j个圆盘移回来,次数是four[j],所以状态转移方程为four[i] = min{four[i], four[j] + three[i - j] + four[j]}

import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        int[] three = new int[13];
        for (int i = 1; i <= 12; i++)
            three[i] = three[i - 1] + 1 + three[i - 1];
        int[] four = new int[13];
        Arrays.fill(four, Integer.MAX_VALUE >> 1);
        four[0] = 0;
        for (int i = 1; i <= 12; i++)
            for (int j = 0; j < i; j++)
                four[i] = Math.min(four[i], four[j] + three[i - j] + four[j]);
        for (int i = 1; i <= 12; i++)
            System.out.println(four[i]);
    }
}
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment