漢諾塔問題,條件如下:
1、這裏有A、B、C和D四座塔。
2、這裏有n個圓盤,n的數量是恆定的。
3、每個圓盤的尺寸都不相同。
4、所有的圓盤在開始時都堆疊在塔A上,且圓盤尺寸從塔頂到塔底逐漸增大。
5、我們需要將所有的圓盤都從塔A轉移到塔D上。
6、每次可以移動一個圓盤,當塔爲空塔或者塔頂圓盤尺寸大於被移動圓盤時,可將圓盤移至這座塔上。
請你求出將所有圓盤從塔A移動到塔D,所需的最小移動次數是多少。
*首先我們先分析3個塔的情況,加入現在我們有i個盤,我們要把i個盤移動到C槽中,就要把i-1個盤子移動到b盤,在移動到a盤,這樣的步驟就是
d[i]=d[i-1]2+1;,四個塔的情況類似,就是先移動j個盤子,然後在將剩餘的盤子在三個塔中移動,這樣就是d[i]的情況了,我們可以先求出d[i]再求四個盤子的情況
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int d[21],f[21];
int main()
{
for(int i=1;i<=12;i++)
d[i]=d[i-1]*2+1;
memset(f,0x3f,sizeof(f));
f[0]=0;
for (int i=1;i<=12;i++)
for (int j=0;j<i;j++)
f[i]=min(f[i],f[j]+f[j]+d[i-j]);
for (int i=1;i<=12;i++)
cout<<f[i]<<endl;
}