[已解决]【C++板块提升计划】梦想护卫舰 第十期 双层汉诺塔

zhangjinxuan

上一关：表达式求值

梦想护卫舰 第十期 双层汉诺塔

你们来到了野人寨

你们听不懂野人说的 威哔吧卟，交流也就产生了困难……

你们只好离开找找这丛林中有没有翻译……

接着你们找到了翻译，不过您得帮他解决一个问题，解决对了就帮助你翻译

现在那个人有 A、B、C 三根足够长的细柱，在 A 柱上放有 2n 个中间有孔的圆盘，共有 n 个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的，例如当 n = 3:

                               
登录/注册后可看大图

现要将这些圆盘移到 C 柱上，在移动过程中可放在 B 柱上暂存。要求：

• 每次只能移动一个圆盘；
• A、B、C三根细柱上的圆盘都要保持上小下大的顺序；
  

任务：设 A_n 为 2n 个圆盘完成上述任务所需的最少移动次数，对于输入的 n，输出A_n。

输入格式

一个正整数 n，表示在 A 柱上放有 2n 个圆盘。

输出格式

一个正整数, 为完成上述任务所需的最少移动次数A_n。

输入样例1

1

输出样例1

2

输入样例2

2

输出样例2

6

数据范围
1 <= n <= 200

注，该题是上古 NOIP 原题，非原创，不过题解是个人原创

                               
登录/注册后可看大图

答案与解析

游客，如果您要查看本帖隐藏内容请回复

[/hide]

最佳战士
名字：元豪
得分：100
奖励：最佳答案+3鱼币3荣誉

                               
登录/注册后可看大图

在翻译的帮助下，你们听懂了野人说的话，野人说小甲鱼被困在了丛林中的一座神庙……

To be continue……

下一关: 数楼梯

最佳答案

月排行榜 / 总排行榜

元豪

2023-1-20 21:06:14

我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~
代码

u = 2
for i in range(int(input()) - 1):
    u *= 2
    u += 1
print(u)

@zhangjinxuan

跳转到最佳答案楼层

Mike_python小

sfqxx

看看

jhq999

fun(n)=fun(n-1)+1+fun(n-1)
一样大的可以看成整体

zhangjinxuan

jhq999 发表于 2023-1-20 18:31

没必要真的去一个一个去推，直接算就行了

jhq999

zhangjinxuan 发表于 2023-1-20 19:24
没必要真的去一个一个去推，直接算就行了

H（k）=2^k-1

元豪

我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~
代码

u = 2
for i in range(int(input()) - 1):
    u *= 2
    u += 1
print(u)

@zhangjinxuan

zhangjinxuan

元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = 上一层的次数 * 2 + 1
所以一个循环就搞定了~

明天看哈

zhangjinxuan

jhq999 发表于 2023-1-20 19:50
H（k）=2^k-1

双层还要乘以2

ba21

无非就是多移一次。

#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;
}

zhangjinxuan

ba21 发表于 2023-1-20 22:07
无非就是多移一次。

只是统计步数而已，而且注意哈，层数会有几百层哦

ba21

zhangjinxuan 发表于 2023-1-20 22:11
只是统计步数而已，而且注意哈，层数会有几百层哦

这没有注意了。那就是另一种题了。

zhangjinxuan

元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~

u 一开始应该是 2

zhangjinxuan

元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~

这明明就是一道高精度题，你tm用python，我真的服了你这个老六

元豪

zhangjinxuan 发表于 2023-1-21 10:04
这明明就是一道高精度题，你tm用python，我真的服了你这个老六

(这是在骂我吗?)

zhangjinxuan

元豪 发表于 2023-1-21 10:14
(这是在骂我吗?)

这道题本意是考高精度……你用了 python……

元豪

zhangjinxuan 发表于 2023-1-21 10:16
这道题本意是考高精度……你用了 python……

所以呢
我的思路应该是对的

zhangjinxuan

元豪 发表于 2023-1-21 10:18
所以呢
我的思路应该是对的

虽然你的思路是对的，不过，高精度题用 python 属于作弊行为了……

元豪

回顾一下~

#include <bits/stdc++.h>
using namespace std;

struct bint{
    int len;
    int t[5000];

    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[i] = s[len - 1 - i] - '0';
        }
    }

    void print(){
        for (int i = 0; i < len; i++){
            cout << t[len - 1 - i];
        }
        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[i] + b.t[i] + carry;
            c.t[i] = x % 10;
            carry = x / 10;
        }
        if (carry){
            c.t[c.len++] = 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[i] * b.t[j] + c.t[i + j] + carry;
                c.t[i + j] = x % 10;
                carry = x / 10;
            }
            if (carry){
                c.t[i + b.len] += carry;
            }
        }
        c.len = len + b.len;
        while (c.len > 1 && c.t[c.len - 1] == 0){
            c.len--;
        }
        return c;
    }
};
int n;

int main() {
        cin >> n;
        bint ans("2");
        while (n--){
                ans = ans * bint("2");
        }
        ans.t[ans.len - 1] = ans.t[ans.len - 1] - 2;
        ans.print();
        
        return 0;
}