鱼C论坛

 找回密码
 立即注册
查看: 2571|回复: 18

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

[复制链接]
发表于 2023-1-20 15:36:24 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
本帖最后由 zhangjinxuan 于 2023-4-2 09:33 编辑

上一关:表达式求值
梦想护卫舰 第十期 双层汉诺塔

你们来到了野人寨

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

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

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

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

                               
登录/注册后可看大图


现要将这些圆盘移到 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 原题,非原创,不过题解是个人原创


                               
登录/注册后可看大图


答案与解析
游客,如果您要查看本帖隐藏内容请回复
[/hide]

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


                               
登录/注册后可看大图


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

To be continue……

下一关: 数楼梯
最佳答案
2023-1-20 21:06:14
本帖最后由 元豪 于 2023-1-21 10:16 编辑

我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~
代码
u = 2
for i in range(int(input()) - 1):
    u *= 2
    u += 1
print(u)
@zhangjinxuan



评分

参与人数 1鱼币 +1 收起 理由
myd0313 + 1 请不要无意义灌水!

查看全部评分

本帖被以下淘专辑推荐:

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-20 16:39:37 | 显示全部楼层
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-20 17:35:45 | 显示全部楼层
看看
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2023-1-20 18:31:30 | 显示全部楼层
fun(n)=fun(n-1)+1+fun(n-1)
一样大的可以看成整体
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 0 反对 1

使用道具 举报

 楼主| 发表于 2023-1-20 19:24:44 | 显示全部楼层

没必要真的去一个一个去推,直接算就行了
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-20 19:50:40 | 显示全部楼层
zhangjinxuan 发表于 2023-1-20 19:24
没必要真的去一个一个去推,直接算就行了

H(k)=2^k-1
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-20 21:06:14 | 显示全部楼层    本楼为最佳答案   
本帖最后由 元豪 于 2023-1-21 10:16 编辑

我发现了规则
移动次数 = (上一层的次数 * 2 + 1) * 2
所以一个循环就搞定了~
代码
u = 2
for i in range(int(input()) - 1):
    u *= 2
    u += 1
print(u)
@zhangjinxuan



评分

参与人数 1荣誉 +5 鱼币 +5 收起 理由
zhangjinxuan + 5 + 5 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-20 22:03:13 From FishC Mobile | 显示全部楼层
元豪 发表于 2023-1-20 21:06
我发现了规则
移动次数 = 上一层的次数 * 2 + 1
所以一个循环就搞定了~

明天看哈
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-20 22:03:48 From FishC Mobile | 显示全部楼层
jhq999 发表于 2023-1-20 19:50
H(k)=2^k-1

双层还要乘以2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-20 22:07:54 | 显示全部楼层
无非就是多移一次。
#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;
}
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-20 22:11:40 From FishC Mobile | 显示全部楼层
ba21 发表于 2023-1-20 22:07
无非就是多移一次。

只是统计步数而已,而且注意哈,层数会有几百层哦
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 0 反对 1

使用道具 举报

发表于 2023-1-20 22:13:23 | 显示全部楼层
zhangjinxuan 发表于 2023-1-20 22:11
只是统计步数而已,而且注意哈,层数会有几百层哦

这没有注意了。那就是另一种题了。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

u 一开始应该是 2
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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

这明明就是一道高精度题,你tm用python,我真的服了你这个老六
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-21 10:14:39 | 显示全部楼层
zhangjinxuan 发表于 2023-1-21 10:04
这明明就是一道高精度题,你tm用python,我真的服了你这个老六

(这是在骂我吗?)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-21 10:16:12 | 显示全部楼层
元豪 发表于 2023-1-21 10:14
(这是在骂我吗?)

这道题本意是考高精度……你用了 python……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-1-21 10:18:33 | 显示全部楼层
zhangjinxuan 发表于 2023-1-21 10:16
这道题本意是考高精度……你用了 python……

所以呢
我的思路应该是对的
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2023-1-21 10:19:47 | 显示全部楼层
元豪 发表于 2023-1-21 10:18
所以呢
我的思路应该是对的

虽然你的思路是对的,不过,高精度题用 python 属于作弊行为了……
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2023-7-5 21:05:07 | 显示全部楼层
回顾一下~
#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;
}

评分

参与人数 1荣誉 +3 鱼币 +3 收起 理由
zhangjinxuan + 3 + 3 鱼C有你更精彩^_^

查看全部评分

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-12-24 08:59

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表