题目大意:
求出n盘四柱Hanoi的最优解
原题面参考:牛客网
思路:
三柱Hanoi问题中,递推公式为的d[n]=2d[n-1]+1; 原因: 1、将n-1个盘放在B柱(利用C柱)上需要d[n-1]步 2、将最后一个放在C上需要一步 3、将B柱上的n-1个移到C上(利用A)需要d[n-1]步 共需要2d[n-1]+1步,其中d[1]=1;
四柱Hanoi问题中,递推公式为f[n]=min(f[n],f[i]*2+d[n-i]);
原因:
1、将i个盘放在B上需要f[i]步,剩下A、C、D即可变成三柱Hanoi问题
2、将A上剩下的盘子移到D需要d[n-i]步(三柱递推公式得)
3、将B柱上的盘移到D需要f[i]步
共需要2f[i]+d[n-i]步,其中f[1]=1;
此题为求最优解,所以应该枚举放在B柱上的盘的可能性,求得最小的步数f[n]
AC Code:
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 0x3f3f3f3f
int f[15], d[15];
int main()
{
memset(f, INF, sizeof(f));
f[1] = 1, d[1] = 1;
for (int i = 2; i <= 12; i++) //三柱Hanoi
d[i] = d[i - 1] * 2 + 1;
for (int i = 1; i <= 12; i++)
{
for (int j = 1; j < i; j++) //求得最小的步数
f[i] = min(f[i], f[j] * 2 + d[i - j]);
cout << f[i] << endl;
}
return 0;
}
Comments | NOTHING