【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

复制代码

输出样例1

1. 2

复制代码

输入样例2

1. 2

复制代码

输出样例2

1. 6

复制代码

数据范围
1 <= n <= 200

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

                               
登录/注册后可看大图

答案与解析

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

[/hide]

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

                               
登录/注册后可看大图

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

To be continue……

下一关: 数楼梯

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
所以一个循环就搞定了~
代码

1. u = 2
   
2. for i in range(int(input()) - 1):
   
3.     u *= 2
   
4.     u += 1
   
5. 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

无非就是多移一次。

1. #include<stdio.h>
   
2. 
   
3. void move(char A, char C, int n)
   
4. {
   
5.         printf("把第%d个圆盘从 %c -> %c\n", n, A, C);
   
6. }
   
7. 
   
8. void HanoiTower(char A, char B, char C, int n)
   
9. {
   
10.         if(n==2)
    
11.         {
    
12.                 move(A, C, n-1);
    
13.                 move(A, C, n);
    
14.         }
    
15.         else
    
16.         {
    
17.                 HanoiTower(A, C, B, n-2);
    
18.                 move(A, C, n-1);
    
19.                 move(A, C, n);
    
20.                 HanoiTower(B, A, C, n-2);
    
21.         }
    
22. }
    
23. 
    
24. int main()
    
25. {
    
26.         int n=0;
    
27.         printf("输入A柱子上的圆盘个数：");
    
28.         scanf("%d", &n);
    
29.         HanoiTower('A', 'B', 'C', 2*n);
    
30. 
    
31.     return 0;
    
32. }
    

复制代码

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 属于作弊行为了……

元豪

回顾一下~

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. 
   
4. struct bint{
   
5.     int len;
   
6.     int t[5000];
   
7. 
   
8.     bint(){
   
9.         memset(t, 0, sizeof(t));
   
10.         len = 0;
    
11.     }
    
12. 
    
13.     bint(const string &s){
    
14.         memset(t, 0, sizeof(t));
    
15.         len = s.length();
    
16.         for (int i = 0; i < len; i++){
    
17.             t[i] = s[len - 1 - i] - '0';
    
18.         }
    
19.     }
    
20. 
    
21.     void print(){
    
22.         for (int i = 0; i < len; i++){
    
23.             cout << t[len - 1 - i];
    
24.         }
    
25.         cout << endl;
    
26.     }
    
27. 
    
28.     bint operator=(const bint &b){
    
29.         len = b.len;
    
30.         memcpy(t, b.t, len * sizeof(int));
    
31.         return *this;
    
32.     }
    
33. 
    
34.     bint operator+(const bint &b) const{
    
35.         bint c;
    
36.         c.len = max(len, b.len);
    
37.         int carry = 0;
    
38.         for (int i = 0; i < c.len; i++){
    
39.             int x = t[i] + b.t[i] + carry;
    
40.             c.t[i] = x % 10;
    
41.             carry = x / 10;
    
42.         }
    
43.         if (carry){
    
44.             c.t[c.len++] = carry;
    
45.         }
    
46.         return c;
    
47.     }
    
48. 
    
49.     bint operator*(const bint &b) const{
    
50.         bint c;
    
51.         for (int i = 0; i < len; i++){
    
52.             int carry = 0;
    
53.             for (int j = 0; j < b.len; j++){
    
54.                 int x = t[i] * b.t[j] + c.t[i + j] + carry;
    
55.                 c.t[i + j] = x % 10;
    
56.                 carry = x / 10;
    
57.             }
    
58.             if (carry){
    
59.                 c.t[i + b.len] += carry;
    
60.             }
    
61.         }
    
62.         c.len = len + b.len;
    
63.         while (c.len > 1 && c.t[c.len - 1] == 0){
    
64.             c.len--;
    
65.         }
    
66.         return c;
    
67.     }
    
68. };
    
69. int n;
    
70. 
    
71. int main() {
    
72.         cin >> n;
    
73.         bint ans("2");
    
74.         while (n--){
    
75.                 ans = ans * bint("2");
    
76.         }
    
77.         ans.t[ans.len - 1] = ans.t[ans.len - 1] - 2;
    
78.         ans.print();
    
79.        
    
80.         return 0;
    
81. }
    

复制代码