【ybt高效进阶1-1-2】奇怪汉诺塔
奇怪汉诺塔
题目链接:ybt高效进阶1-1-2
题目
就是四根柱子的汉诺塔,问你圆盘数量分别是 1 ∼ 12 1\sim 12 1∼12 个的时候,从一个挪到另一个至少要多少步。
思路
首先,我们要知道三根柱子怎么求。
那就是先把柱子除了最下面的那一个都挪到第二根柱子,然后最下面的那个盘子移到第三根柱子,然后把第二根柱子上的柱子移回第三根。
(这里说的挪是多个挪,挪完之后形状要不变)
那就是 g i = 2 × g i − 1 + 1 g_i=2\times g_{i-1}+1 gi=2×gi−1+1
接着我们看变成四根柱子怎么求。
三根柱子的时候我们把柱子分成两个部分,下面只能放一个,因为如果放了不止一个,要把下面的移到第三根的位置,就会改变形状。因为你只可以在第一根柱子和第三根柱子中动。
但是变成四根柱子后,移动上面的就是在四个柱子中间移动,移动下面的就是在三个柱子中间移动。
我们就可以枚举上面下面的大小。
那就是 f i = min 1 ≤ j < n { 2 × f j + g i − j } f_i=\min\limits_{1\leq j<n}\{2\times f_j+g_{i-j}\} fi=1≤j<nmin{2×fj+gi−j}。( g i g_i gi 就是前面定义的,三根柱子的那个)
不用开 long long,我一开始以为要开,就开了。后来发现不用,也懒得改了。
代码
#include<cstdio>
#include<iostream>
using namespace std;
long long f[13], g[13];
int main() {
g[1] = 1ll;//处理出三个柱子的汉诺塔
for (int i = 2; i <= 12; i++)
g[i] = 2 * g[i - 1] + 1;
f[1] = 1ll;//算四个柱子的
for (int i = 2; i <= 12; i++) {
f[i] = (1ll << 63) - 1;
for (int j = 1; j <= i - 1; j++)
f[i] = min(f[i], 2ll * f[j] + g[i - j]);
}
for (int i = 1; i <= 12; i++)
printf("%lld\n", f[i]);
return 0;
}
提供一下答案
1
3
5
9
13
17
25
33
41
49
65
81
\color{white}1\ 3\ 5\ 9\ 13\ 17\ 25\ 33\ 41\ 49\ 65\ 81
1 3 5 9 13 17 25 33 41 49 65 81
已调成白色,若需要则选中查看。
相关文章
- 看美剧学英语,怎样学最高效
- 有什么高效备考网络工程师的方法?
- 如何构建一个高效的数据科学部门
- 如何高效的阅读uni-app框架?(建议收藏)
- 高效程序员的七个习惯
- 《C++面向对象高效编程(第2版)》——1.5 什么可以作为类
- 《JavaScript高效图形编程(修订版)》——2.2 转为一个jQuery插件
- 《JavaScript高效图形编程(修订版)》——第6章 HTML5画布 6.1 画布的支持
- 广联达付永晖:大数据助力政府精准治理和高效监管
- 周生生签约8Manage 实现高效自动化采购管理
- Unity框架学习_ResManager,高效管理资源的加载和卸载
- 高效学习传感器|浅谈CCD的工作原理以及常用波
- 高效使用你的Xcode
- 高效SQL语句(SQL Server)
- Word高效指南 - 快速合并多个文档