文章目錄

• • • 題目解答
    • 題目鏈接

題目解答

來源：acwing

分析：

本題的漢諾塔問題是n個(gè)盤子4個(gè)塔，最基本的漢諾塔是n個(gè)盤子3個(gè)塔。本題是要在后者的基礎(chǔ)上來做。

設(shè)d[i]表示i盤3塔問題的最小移動步數(shù)
遞推公式是：$d[i]=2\times d[i?1]+1$
解釋：共有A、B、C3個(gè)塔，把前i-1個(gè)盤子從A塔移動到B塔，然后A塔剩余的最后一個(gè)盤子移到C塔，最后把B塔的i-1個(gè)盤子移到C盤。

對于本題呢？

設(shè)f[i]表示i盤4塔問題的最小移動步數(shù)
遞推公式是：$f[i]=min(f[i],2\times f[j]+d[i?j])$

解釋：共有A、B、C、D4個(gè)塔， 初始化f[1] = 1, 表示 1個(gè)盤子從A移到D只需要1步。
具體過程：先把j個(gè)盤子從A塔移到B塔（這是在4塔問題），然后把 i - j個(gè)盤子移到D塔（這是在3塔問題，因?yàn)锽塔被用了），然后再把B塔上的j個(gè)盤子移到D塔（這是在4塔問題）。當(dāng)然，所有情況取最小值。

ac代碼

#include<bits/stdc++.h> using namespace std; const int N = 15 ; int d[N],f[N]; int main(){// 先處理 只有3個(gè)塔的情況d[1] = 1; //初始化:1個(gè)盤子移到終點(diǎn)for(int i = 2; i <= 12; i ++){d[i] = 2* d[i -1] + 1;}// 處理4個(gè)塔的情況memset(f, 0x3f, sizeof f);f[1] = 1; // 1個(gè)盤子移到終點(diǎn)// 把j個(gè)盤子放到一邊// 把剩余的 i -j個(gè)盤子放到終點(diǎn)// 再把j個(gè)盤子放到終點(diǎn)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; }

題目鏈接

https://www.acwing.com/problem/content/98/

參考題解
https://www.acwing.com/solution/content/2473/

總結(jié)

以上是生活随笔為你收集整理的《算法竞赛进阶指南》打卡-基本算法-AcWing 96. 奇怪的汉诺塔：递推的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。