這是一道很經(jīng)典的問(wèn)題。

先看3個(gè)塔的情況
需要注意的是，這里的漢諾塔移動(dòng)并無(wú)只可以移動(dòng)到相鄰塔的需求。即可以直接從A移到C。
設(shè)d[i]表示將i個(gè)盤子從這里移到其他除它之外塔的步數(shù) ,總塔的數(shù)量為3
故d[i]=d[i-1]+d[i-1]+1 即將i-1個(gè)盤子移到B,將i號(hào)盤子移動(dòng)C,再將i-1個(gè)盤子從B移到C

接下來(lái)分析4個(gè)塔的情況
設(shè)f[i]表示將i個(gè)盤子從這里移到其他除它之外塔的步數(shù),總塔的數(shù)量為4
f[i]=min(f[i],f[j]+f[j]+d[i-j]) 將j個(gè)盤子移到一個(gè)柱子，此時(shí)的j個(gè)盤子已經(jīng)占了一個(gè)柱子，故剩余的i-j個(gè)盤子按照三個(gè)盤子的套路移動(dòng)到D，再將j個(gè)盤子弄到D
這里都是f[j]是因?yàn)?移開(kāi)的時(shí)候好分析，有三個(gè)柱子可以用，回來(lái)的時(shí)候因?yàn)槲覀兣藕玫谋P子在D柱子已經(jīng)是大的盤子，故不影響還是f[j]

#include<bits/stdc++.h> using namespace std; const int N=15; int f[N],d[N]; int main(void) {d[1]=1;for(int i=2;i<=12;i++) d[i]=d[i-1]*2+1;memset(f,0x3f,sizeof f);f[1]=1;for(int i=2;i<=12;i++)for(int j=1;j<i;j++) f[i]=min(f[i],f[j]*2+d[i-j]);for(int i=1;i<=12;i++) cout<<f[i]<<endl;return 0; } 《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的96. 奇怪的汉诺塔【递推】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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