---

title: Strange Towers of Hanoi
date: 2023-12-11 03:20:05
tags: 遞推
categories: 算法進階指南

題目大意

解出 $n$ 個盒子 $4$ 座塔的漢諾塔問題最少需要多少次？

思路

首先考慮 $n$ 個盒子 $3$ 座塔的經典漢諾塔問題，設 $d[n]$ 表示求解該 $n$ 題的最少步數，即把 $n?1$ 個盒子從 $A$ 柱移動到 $B$ 柱，然后把第 $n$ 個盒子從 $A$ 柱移動到 $C$ 柱，然后把前 $n?1$ 個盒子從 $B$ 柱移動到 $C$ 柱子。四塔模式下，轉化為三塔模式，先移動 $i$ 個，移動到 $B$ 柱子，將 $n?i$ 個盒子移動到 $D$ 柱子，然后再把 $i$ 個盒子從 $B$ 柱移動到 $D$ 柱子。就是將四塔轉化為三塔，運用三塔的思維來進行解題

代碼

#include<bits/stdc++.h>
using namespace std;typedef long long LL;const int N = 22;int d[N],f[N];//三層和四層漢諾塔
//三層漢諾塔 d[n] = 2 * d[n - 1] + 1;
//四層漢諾塔，轉化為三層漢諾塔問題
int main()
{memset(f,0x3f,sizeof f);d[1] = f[1] = 1;for(int i = 2;i <= 12; i ++){d[i] = 2 * d[i - 1] + 1;}cout << 1 << endl;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]);}cout << f[i] << endl;}return 0;
}