[POJ1958][Strange Tower of Hanoi]
2024-10-11 22:19:04
题目描述
求解 \(n\) 个盘子 \(4\) 座塔的 Hanoi 问题最少需要多少步
问题分析
考虑 \(3\) 座塔的 Hanoi 问题，记 \(f[i]\) 表示最少需要多少步， 则 \(f[i] = 2 * f[i - 1] + 1\) ， 即把前 \(n - 1\) 个盘子从 \(A\) 移动到 \(B\), 然后把最下面的盘子移动到 \(C\)， 最终把前面的 \(n - 1\) 个盘子移到 \(C\)
考虑把4个盘子的情况转移到三个的情况，则有 \[f[i] = \min_{1 \le i < n} \{2 * f[i] + d[n - i]\}\]
其中 \(f[1] = 1\).上式的意义是先把 \(i\) 个盘子在 \(4\) 她模式下移动到 \(B\) 柱，然后把 \(n-i\) 个盘子在 \(3\)塔模式下移到 \(D\) 柱。最后把 \(i\) 个盘子在 \(4\) 塔模式下移到 \(D\)柱，考虑所有可能的 \(I\) 取最小值，就是上述式子的意义。
推广
考虑 \(n\) 个盘子在 \(m\) 个塔下的最小值。式子与上述一样，增加一位表示第几种，复杂度 \(n^3\)
最新文章
- validate插件深入学习-04自定义验证方法
- 团队第二周：SRS文档
- Linux-TCP Queue的一些问题
- 你知不知道 Cookie正在泄露你的隐私！
- Objective-c归档的概念和用法
- web前端开发控件学习笔记之jqgrid+ztree+echarts
- php微信开发(1)：缓存access_token的方法
- this的分析
- BZOJ3687: 简单题
- win7(windows 7)系统下安装SQL2005(SQL Server 2005)图文教程——转载
- description方法的介绍及重写
- three.js 实现全景以及优化（2）
- RSA Encrypting/Decrypting、RSA+AES Encrypting/Decrypting
- K8s-Pod控制器
- pitch, yaw, roll
- Asp.net core 学习笔记 ( OData )
- 十问Android NFC手机上的卡模拟（转）
- 分布式文件系统之FastDFS
- Linux下jdk安装过程
- Restful Framework （二）