递归的分解思维：汉诺塔与斐波那契

// 汉诺塔 —— 递归版
//
// 输入：一个整数 n（盘子数）
// 输出：把 n 个盘子从 A 柱借助 B 柱全部搬到 C 柱的每一步，最后一行是总步数
//
// 规则：一次只能搬一个盘子，任何时候大盘子都不能压在小盘子上面。
//
// 递归三要素（第 1 章那三条，一条都没变）：
//   1. 职责 —— hanoi(k, from, to, via) 负责「把 from 柱最上面的 k 个盘子搬到 to 柱，
//      中途可以借用 via 柱」。注意它不关心底下还压着什么，也不该关心。
//   2. 边界 —— k == 0：一个盘子都没有，什么都不用做。
//   3. 递推 —— 想把 k 个搬过去，只有一条路：
//        先把上面 k-1 个挪开（挪到 via），
//        再把露出来的第 k 个（最大的那个）搬到 to，
//        最后把那 k-1 个从 via 搬到 to。
//
// 中间那一步是「真正搬了一个盘子」，前后两步都是「同一个问题，只是小了一号」。
// 这就是分解：大问题 = 小问题 + 一步真活 + 小问题。
//
// 请不要试图在脑子里模拟它怎么跑 —— n = 5 就有 31 步，谁也模拟不动。
// 你要做的是检查上面那三行的「说法」对不对；说法对，代码就对。

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

long long steps = 0;

void hanoi(int k, char from, char to, char via) {
    if (k == 0) return;                       // 出口：没有盘子要搬

    hanoi(k - 1, from, via, to);              // 1. 上面 k-1 个：from -> via（借 to）
    steps++;
    cout << "盘 " << k << ": " << from << " -> " << to << "\n";   // 2. 第 k 个：真正搬一次
    hanoi(k - 1, via, to, from);              // 3. 那 k-1 个：via -> to（借 from）
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    hanoi(n, 'A', 'C', 'B');
    cout << "共 " << steps << " 步\n";
    return 0;
}

// 汉诺塔 —— 带打印的递归，用来「看见」它是怎么分解的
//
// 和 hanoi.cpp 算的是同一件事，只是在每次进入 / 返回时打印一行，缩进表示层数。
//
// 跑一遍 n = 3，然后盯住输出里的这个形状：
//   每个 hanoi(k, ...) 都会立刻变成三行：
//     一个 hanoi(k-1, ...)  ← 同样形状的小问题
//     一次真正的搬盘子
//     又一个 hanoi(k-1, ...) ← 同样形状的小问题
//
// 「大问题 = 小问题 + 一步真活 + 小问题」这句话，在输出里是看得见的。

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

int depth = 0;
long long steps = 0;

void indent() {
    for (int i = 0; i < depth; i++) cout << "|   ";
}

void hanoi(int k, char from, char to, char via) {
    indent();
    cout << "-> hanoi(" << k << ", " << from << " -> " << to << ", 借 " << via << ")\n";
    depth++;

    if (k == 0) {
        indent();
        cout << "   没有盘子，直接回去\n";
    } else {
        hanoi(k - 1, from, via, to);

        steps++;
        indent();
        cout << "★ 第 " << steps << " 步：把盘 " << k << " 从 " << from << " 搬到 " << to << "\n";

        hanoi(k - 1, via, to, from);
    }

    depth--;
    indent();
    cout << "<- hanoi(" << k << ", " << from << " -> " << to << ") 完成\n";
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    cout << "把 " << n << " 个盘子从 A 搬到 C\n\n";
    hanoi(n, 'A', 'C', 'B');
    cout << "\n一共 " << steps << " 步\n";
    return 0;
}

// 汉诺塔 —— 递归版
//
// 输入：一个整数 n（盘子数）
// 输出：把 n 个盘子从 A 柱借助 B 柱全部搬到 C 柱的每一步，最后一行是总步数
//
// 规则：一次只能搬一个盘子，任何时候大盘子都不能压在小盘子上面。
//
// 递归三要素（第 1 章那三条，一条都没变）：
//   1. 职责 —— hanoi(k, from, to, via) 负责「把 from 柱最上面的 k 个盘子搬到 to 柱，
//      中途可以借用 via 柱」。注意它不关心底下还压着什么，也不该关心。
//   2. 边界 —— k == 0：一个盘子都没有，什么都不用做。
//   3. 递推 —— 想把 k 个搬过去，只有一条路：
//        先把上面 k-1 个挪开（挪到 via），
//        再把露出来的第 k 个（最大的那个）搬到 to，
//        最后把那 k-1 个从 via 搬到 to。
//
// 中间那一步是「真正搬了一个盘子」，前后两步都是「同一个问题，只是小了一号」。
// 这就是分解：大问题 = 小问题 + 一步真活 + 小问题。
//
// 请不要试图在脑子里模拟它怎么跑 —— n = 5 就有 31 步，谁也模拟不动。
// 你要做的是检查上面那三行的「说法」对不对；说法对，代码就对。

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

long long steps = 0;

void hanoi(int k, char from, char to, char via) {
    if (k == 0) return;                       // 出口：没有盘子要搬

    hanoi(k - 1, from, via, to);              // 1. 上面 k-1 个：from -> via（借 to）
    steps++;
    cout << "盘 " << k << ": " << from << " -> " << to << "\n";   // 2. 第 k 个：真正搬一次
    hanoi(k - 1, via, to, from);              // 3. 那 k-1 个：via -> to（借 from）
}

int main() {
    int n;
    if (!(cin >> n)) return 0;

    hanoi(n, 'A', 'C', 'B');
    cout << "共 " << steps << " 步\n";
    return 0;
}

// 汉诺塔要多少步 —— 以及这些步要搬多久
//
// 输入：n
// 输出：2^n - 1 步，以及按「一秒搬一个盘子」算需要多长时间
//
// 这份代码没有任何算法，它只是把一个数字算出来给你看。
// 但请一定跑一次 n = 64（传说里那个版本），看看那个时间。
//
// 它要说明的事情是：汉诺塔慢，不是因为我们的程序写得笨，
// 而是因为**答案本身就有那么多步**。2^n - 1 步是这道题的下界，一步都省不掉：
//   要把最大的盘子搬走，必须先把上面 n-1 个全挪开（至少 f(n-1) 步），
//   搬完之后还得把它们全搬回来（又至少 f(n-1) 步），
//   所以 f(n) >= 2 * f(n-1) + 1。
//
// 这一点和下面斐波那契那半章形成鲜明对比：
// 斐波那契的递归也是 2^n 级别，但那个 2^n 是**浪费**，可以被消掉（第 17 章）。

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

int main() {
    int n;
    if (!(cin >> n)) return 0;
    if (n < 1 || n > 64) { cout << "请输入 1 到 64 之间的 n\n"; return 0; }

    // n = 64 时 2^64 - 1 会溢出 long long，用无符号
    unsigned long long steps = (n == 64)
        ? ~0ULL
        : ((1ULL << n) - 1);

    cout << n << " 个盘子需要 " << steps << " 步\n";

    long double sec = (long double)steps;
    cout << fixed << setprecision(1);
    if (sec < 60)                 cout << "按一秒一步算：" << (double)sec << " 秒\n";
    else if (sec < 3600)          cout << "按一秒一步算：" << (double)(sec / 60) << " 分钟\n";
    else if (sec < 86400)         cout << "按一秒一步算：" << (double)(sec / 3600) << " 小时\n";
    else if (sec < 86400.0L * 365)cout << "按一秒一步算：" << (double)(sec / 86400) << " 天\n";
    else                          cout << "按一秒一步算：" << (double)(sec / (86400.0L * 365)) << " 年\n";

    return 0;
}

// 斐波那契 —— 数一数每个 fib(k) 到底被算了几遍
//
// 输入：n（建议 10 ~ 25，别太大）
// 输出：每个 k 对应的调用次数，以及总调用次数、白算的比例
//
// 不要猜「大概重复了一些」，直接数出来。数完你会看到两件事：
//   1. fib(k) 被调用的次数本身也是一串斐波那契数（很漂亮，也很吓人）
//   2. 明明只有 n+1 个不同的值要算，实际却算了几十万、几百万次
//
// 这就是第 17 章记忆化搜索要解决的问题：把「算过的记下来」，
// 于是 O(2^n) 一步变成 O(n)。这一章先把病灶看清楚，不急着治。

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

vector<long long> calls;    // calls[k] = fib(k) 被调用了多少次
long long total = 0;

long long fib(int n) {
    calls[n]++;
    total++;
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    if (n < 0 || n > 40) { cout << "请输入 0 到 40 之间的 n\n"; return 0; }

    calls.assign(n + 1, 0);
    long long ans = fib(n);

    cout << "fib(" << n << ") = " << ans << "\n\n";
    cout << "  k    被调用次数\n";
    cout << "-----  ----------\n";
    for (int k = n; k >= 0; k--) {
        cout << setw(3) << k << "    " << setw(10) << calls[k] << "\n";
    }

    cout << "\n不同的 k 一共 " << (n + 1) << " 个 —— 也就是说只有 " << (n + 1) << " 个值需要算。\n";
    cout << "实际调用了 " << total << " 次。\n";
    if (total > 0) {
        double waste = 100.0 * (total - (n + 1)) / (double)total;
        cout << fixed << setprecision(4);
        cout << "其中 " << waste << "% 是在重复计算已经算过的东西。\n";
    }
    return 0;
}

// 斐波那契 —— 递归版（照着定义直接翻译）
//
// 输入：n（0 <= n <= 50）
// 输出：第 n 项。约定 f(0) = 0, f(1) = 1, f(n) = f(n-1) + f(n-2)
//
// 这份代码和汉诺塔是同一个套路：大问题拆成同形状的小问题。
// 三要素也齐了：职责（返回第 n 项）、边界（n < 2 时就是 n）、递推（前两项之和）。
//
// 它是**完全正确**的，n 小的时候还快得看不出来。
// 但把 n 调到 44 以上再跑一次 —— 那个卡顿就是这半章要讲的东西。

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

long long fib(int n) {
    if (n < 2) return n;                 // 出口：f(0)=0, f(1)=1
    return fib(n - 1) + fib(n - 2);      // 递推：拆成两个更小的同类问题
}

int main() {
    int n;
    if (!(cin >> n)) return 0;
    cout << fib(n) << "\n";
    return 0;
}