网站做短视频业务许可,郑州专业网站建设公司详情,企业查询天眼,网站店铺建设title: Strange Towers of Hanoi date: 2023-12-11 03:20:05 tags: 递推 categories: 算法进阶指南
题目大意 解出 n n n 个盒子 4 4 4 座塔的汉诺塔问题最少需要多少次#xff1f; 思路 首先考虑 n n n 个盒子 3 3 3 座塔的经典汉诺塔问题#xff0c;设 d [ n ] d[n] …
title: Strange Towers of Hanoi date: 2023-12-11 03:20:05 tags: 递推 categories: 算法进阶指南
题目大意 解出 n n n 个盒子 4 4 4 座塔的汉诺塔问题最少需要多少次 思路 首先考虑 n n n 个盒子 3 3 3 座塔的经典汉诺塔问题设 d [ n ] d[n] d[n] 表示求解该 n n n 题的最少步数即把 n − 1 n - 1 n−1 个盒子从 A A A 柱移动到 B B B 柱然后把第 n n n 个盒子从 A A A 柱移动到 C C C 柱然后把前 n − 1 n - 1 n−1 个盒子从 B B B 柱移动到 C C C 柱子。四塔模式下转化为三塔模式先移动 i i i 个移动到 B B B 柱子将 n − i n - i n−i 个盒子移动到 D D D 柱子然后再把 i i i 个盒子从 B B B 柱移动到 D D D 柱子。就是将四塔转化为三塔运用三塔的思维来进行解题 代码
#includebits/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;
}
