【C++板块提升计划】梦想护卫舰 第十期 双层汉诺塔
本帖最后由 zhangjinxuan 于 2023-4-2 09:33 编辑上一关：表达式求值
梦想护卫舰 第十期 双层汉诺塔
你们来到了野人寨
你们听不懂野人说的 威哔吧卟，交流也就产生了困难……
你们只好离开找找这丛林中有没有翻译……
接着你们找到了翻译，不过您得帮他解决一个问题，解决对了就帮助你翻译
现在那个人有 A、B、C 三根足够长的细柱，在 A 柱上放有 2n 个中间有孔的圆盘，共有 n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的，例如当 n = 3:
https://cdn.luogu.com.cn/upload/pic/33.png
现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：
[*]每次只能移动一个圆盘；
[*]A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
任务：设 An 为 2n 个圆盘完成上述任务所需的最少移动次数，对于输入的 n，输出An。
输入格式
一个正整数 n，表示在 A 柱上放有 2n 个圆盘。
输出格式
一个正整数, 为完成上述任务所需的最少移动次数An。
输入样例1
1
输出样例1
2
输入样例2
2
输出样例2
6
数据范围
1 <= n <= 200
注，该题是上古 NOIP 原题，非原创，不过题解是个人原创
static/image/hrline/1.gif
答案与解析
**** Hidden Message *****
最佳战士
名字：元豪
得分：100
奖励：最佳答案+3鱼币3荣誉
static/image/hrline/1.gif
在翻译的帮助下，你们听懂了野人说的话，野人说小甲鱼被困在了丛林中的一座神庙……
To be continue……
下一关: 数楼梯 看看 fun(n)=fun(n-1)+1+fun(n-1)
一样大的可以看成整体 jhq999 发表于 2023-1-20 18:31
没必要真的去一个一个去推，直接算就行了 zhangjinxuan 发表于 2023-1-20 19:24
没必要真的去一个一个去推，直接算就行了
H（k）=2^k-1 本帖最后由 元豪 于 2023-1-21 10:16 编辑
我发现了规则{:10_279:}
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~{:10_256:}
代码
u = 2
for i in range(int(input()) - 1):
u *= 2
u += 1
print(u)
@zhangjinxuan
元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = 上一层的次数 * 2 + 1
所以一个循环就搞定了~
明天看哈 jhq999 发表于 2023-1-20 19:50
H（k）=2^k-1
双层还要乘以2 无非就是多移一次。
#include<stdio.h>
void move(char A, char C, int n)
{
printf("把第%d个圆盘从 %c -> %c\n", n, A, C);
}
void HanoiTower(char A, char B, char C, int n)
{
if(n==2)
{
move(A, C, n-1);
move(A, C, n);
}
else
{
HanoiTower(A, C, B, n-2);
move(A, C, n-1);
move(A, C, n);
HanoiTower(B, A, C, n-2);
}
}
int main()
{
int n=0;
printf("输入A柱子上的圆盘个数：");
scanf("%d", &n);
HanoiTower('A', 'B', 'C', 2*n);
return 0;
}
ba21 发表于 2023-1-20 22:07
无非就是多移一次。
只是统计步数而已，而且注意哈，层数会有几百层哦 zhangjinxuan 发表于 2023-1-20 22:11
只是统计步数而已，而且注意哈，层数会有几百层哦
这没有注意了。那就是另一种题了。 元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~
u 一开始应该是 2 {:10_256:} 元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~
这明明就是一道高精度题，你tm用python，我真的服了你这个老六{:10_282:} zhangjinxuan 发表于 2023-1-21 10:04
这明明就是一道高精度题，你tm用python，我真的服了你这个老六
(这是在骂我吗?{:10_277:}) 元豪 发表于 2023-1-21 10:14
(这是在骂我吗?)
这道题本意是考高精度……你用了 python…… zhangjinxuan 发表于 2023-1-21 10:16
这道题本意是考高精度……你用了 python……
所以呢{:10_282:}
我的思路应该是对的 元豪 发表于 2023-1-21 10:18
所以呢
我的思路应该是对的
虽然你的思路是对的，不过，高精度题用 python 属于作弊行为了…… 回顾一下~
#include <bits/stdc++.h>
using namespace std;
struct bint{
int len;
int t;
bint(){
memset(t, 0, sizeof(t));
len = 0;
}
bint(const string &s){
memset(t, 0, sizeof(t));
len = s.length();
for (int i = 0; i < len; i++){
t = s - '0';
}
}
void print(){
for (int i = 0; i < len; i++){
cout << t;
}
cout << endl;
}
bint operator=(const bint &b){
len = b.len;
memcpy(t, b.t, len * sizeof(int));
return *this;
}
bint operator+(const bint &b) const{
bint c;
c.len = max(len, b.len);
int carry = 0;
for (int i = 0; i < c.len; i++){
int x = t + b.t + carry;
c.t = x % 10;
carry = x / 10;
}
if (carry){
c.t = carry;
}
return c;
}
bint operator*(const bint &b) const{
bint c;
for (int i = 0; i < len; i++){
int carry = 0;
for (int j = 0; j < b.len; j++){
int x = t * b.t + c.t + carry;
c.t = x % 10;
carry = x / 10;
}
if (carry){
c.t += carry;
}
}
c.len = len + b.len;
while (c.len > 1 && c.t == 0){
c.len--;
}
return c;
}
};
int n;
int main() {
cin >> n;
bint ans("2");
while (n--){
ans = ans * bint("2");
}
ans.t = ans.t - 2;
ans.print();
return 0;
}
页:
[1]