VOJ 汉诺塔 题解 递推

汉诺塔

题目描述

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 6464 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。
现在小明开始玩汉诺塔游戏， 他放了 n 片黄金圆盘在第一根柱子上，从上到下依次编号为 1~n， 1 号圆盘最小，n 号圆盘最大。小明移动第 i 号圆盘的时候需要花费 i 点体力。现在小明想把圆盘全部移动到第二根柱子上，移动过程中小明必须准守游戏规则。
现在小明想知道他完成游戏的最小移动次数和最少消耗的体力。

输入描述

输入一个正整数 n(1≤n≤60) 表示黄金圆盘的个数。

输出描述

一行输出 2 个数，表示最小移动次数和最小消耗的体力，中间用一个空格隔开。

样例1

样例输入1

2
1

样例输出 1

3 4
1

样例2

样例输入 2

3
1

样例输出 2

7 11
1

思路

介绍一下用汉诺塔递推公式解决本道题目：
1.最小移动次数：$f(i)=f(i-1)\ast 2+1$
2.最少消耗体力：$f(i)=f(i-1)\ast 2+i$
最小移动次数递推公式的相关证明如有需要可直接搜索。而最少消耗体力可以这样理解：每一次移动都要消耗一次体力，而消耗多少体力取决于 $i$ 的值。那不妨在考虑最小移动次数的时候将其理解为每一次移动都要消耗 $1$，而考虑最少消耗体力的时候将其理解为每一次移动都要消耗 $i$，这样的话只需在递推公式中用 $i$ 替换 $1$ 即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[66], b[66]; // 黄金圆盘个数为i时，a[i]为最小移动次数，b[i]为最少消耗的体力
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    a[0] = 0;
    b[0] = 0;
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        a[i] = 2 * a[i - 1] + 1; // 递推
    cout << a[n] << " ";
    for (int i = 1; i <= n; i++)
        b[i] = 2 * b[i - 1] + i; // 递推
    cout << b[n];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21