题目描述

汉诺塔问题，条件如下：

  1. 这里有A、B、C和D四座塔。
  2. 这里有n个圆盘，n的数量是恒定的。
  3. 每个圆盘的尺寸都不相同。
  4. 所有的圆盘在开始时都堆叠在塔A上，且圆盘尺寸从塔顶到塔底逐渐增大。
  5. 我们需要将所有的圆盘都从塔A转移到塔D上。

请你求出将所有圆盘从塔A移动到塔D，所需的最小移动次数是多少。

输入格式

没有输入

输出格式

对于每一个整数n(1≤n≤12),输出一个满足条件的最小移动次数，每个结果占一行。

输入样例

没有输入

输出样例

参考输出格式

思路

我们首先以三个盘的汉诺塔问题为基础。设d[n]表示求解n盘3塔问题的最小步数。
就可以得到递推式:

d[n]=2*d[n-1]+1

即把前n-1个盘子从A柱移到B柱，然后把A柱上剩的那一个盘子移动到C柱，最后把B柱上的那n-1个盘子移动到C柱上

接下来我们讨论四个盘的汉诺塔问题。设f[n]表示求解n盘4塔问题的最小步数
可以得到递推式:

f[n]=min(f[i],f[i]*2+d[n-i])

初始化：f[1] = 1(一个盘子在4塔模式下移动到D柱需要1步)
先把i个盘子在4塔模式下移动到B柱，
然后把n-i个盘子在3塔模式下移动到D柱（因为不能覆盖到B柱上，就等于只剩下A、C、D柱可以用）
最后把i个盘子在4塔模式下移动到D柱
考虑所有可能的i取最小值，即得到上述递推公式

C++ 代码

#include<iostream>
#include<cstring>
using namespace std;
int d[15], f[15];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	d[1] = 1;
	for (int i = 2;i <= 12;i++)
		d[i] = 2 * d[i - 1] + 1;
	memset(f, 0x3f, sizeof(f));
	f[0] = 0,f[1]=1;
	for (int i = 2;i <= 12;i++)
		for (int j = 1;j <= i;j++)
			f[i] = min(f[i], 2 * f[j] + d[i - j]);
	for (int i = 1;i <= 12;i++)
		cout << f[i] << endl;
	return 0;
}

Java代码

import java.io.OutputStreamWriter;
import java.io.PrintWriter;
public class Main {
    static int[] d=new int[15];
    static int[] f=new int[15];
    static PrintWriter out = new PrintWriter(System.out);
	public static void main(String[] args) {
		// TODO 自动生成的方法存根
        d[1] = 1;
	    for (int i = 2;i <= 12;i++)
		   d[i] = 2 * d[i - 1] + 1;
		for(int i=2;i<=12;i++)
		   f[i]=0x3f3f;
		f[1]=1;
		for (int i = 2;i <= 12;i++)
		   for (int j = 1;j <= i;j++)
			   f[i] = Math.min(f[i], 2 * f[j] + d[i - j]);
	    for(int i=1;i<=12;i++)
	           out.println(f[i]);
        out.flush();
	}
}