本文共 2504 字，大约阅读时间需要 8 分钟。

栈和递归教程

0. 栈的基本使用

栈是一种先进后出的数据结构，常用于解决计算机科学中的各种问题。通过简单的例子，我们可以快速理解栈的基本使用方法。

以下是一个使用栈的典型示例：

#include 
   
    #include 
    
     using namespace std;int main() {    stack
     
       s;    s.push(1);  // 进栈    s.push(2);    s.push(3);    s.pop();  // 出栈    cout << s.top() << endl;  // 输出栈顶元素    s.top();  // 查看栈顶元素}
     
    
   

在这个程序中，push 方法用于将元素推送到栈顶，pop 方法用于从栈顶取出元素，而 top() 方法用于查看栈顶元素。栈的操作非常简单，但在算法中却扮演着至关重要的角色。

1. 汉诺塔问题

汉诺塔问题是一个经典的递归问题，涉及三个垂直的柱子（通常用 A、B、C 表示），盘子从上到下依次编号为 1 到 n。目标是将盘子从 A 柱子移动到 C 柱子，中间只能通过 B 柱子进行暂存。

汉诺塔的递归解决方法

汉诺塔问题可以通过递归分解解决：

以下是实现汉诺塔的代码示例：

#include 
   
    #include 
    
     using namespace std;stack
     
       S[3];  // 三个柱子void move(int x, int y, int z) {    int temp = S[x].top();    S[x].pop();    S[y].push(temp);    cout << x << " --> " << y << endl;}void hanoi(int a, int b, int c, int n) {    if (n == 1) {        move(a, c, b);        return;    }    hanoi(a, c, b, n-1);  // 将 n-1 个盘子从 a 移动到 b    hanoi(b, a, c, n-1);  // 将 b 柱上的盘子从 b 移动到 c    move(a, c, b);  // 将 a 柱上的盘子移动到 c}int main() {    int n;    cin >> n;    for (int i = n; i > 0; --i) {        S[0].push(i);  // 初始化盘子    }    hanoi(0, 1, 2, n);  // 启动汉诺塔算法    while (!S[2].empty()) {        cout << S[2].top() << " ";        S[2].pop();    }    return 0;}
     
    
   

输出结果

输入 n=3 时，输出如下：

0 --> 21 --> 32 --> 13 --> 22 --> 31 --> 23 --> 1

2. 汉诺塔问题的变种

假设小明在玩汉诺塔，盘子从上到下依次编号为 1 到 n。每次移动盘子时，消耗的体力等于盘子的编号。我们需要计算小明移动盘子的总步数以及总消耗的体力。

汉诺塔的递归解决方法

汉诺塔的总移动次数与递归深度有关。对于 n 个盘子，总移动次数为 2^n - 1。每次移动盘子的体力消耗为盘子的编号，因此总消耗体力可以通过递推公式计算：

• f(1) = 1
• f(n) = 2 * f(n-1) + 1

总消耗体力为 f(n)。

总步数为 g(n)，递推公式为：

• g(1) = 1
• g(n) = 2 * g(n-1) + n

以下是实现代码：

#include 
   
    using namespace std;long long f[65], g[65];int main() {    int n;    cin >> n;    f[1] = 1;    for (int i = 2; i <= n; ++i) {        f[i] = 2 * f[i-1] + 1;    }    g[1] = 1;    for (int j = 2; j <= n; ++j) {        g[j] = 2 * g[j-1] + j;    }    cout << f[n] << " ";    return 0;}
   

输出结果

输入 n=3 时，输出如下：

10 21"

3. 辗转相除法

辗转相除法是一种计算最大公约数（GCD）的方法，基于以下递归关系：

GCD(x, y) = GCD(y, x % y) （当 y > 0 时）

递归终止条件是 y = 0，此时 GCD(x, y) = x。

以下是实现辗转相除法的代码示例：

#include 
   
    using namespace std;int f(int x, int y) {    if (y == 0) {        return x;    } else {        return f(y, x % y);    }}int main() {    int x, y;    cin >> x >> y;    cout << f(x, y) << endl;    return 0;}
   

输出结果

输入 x=48，y=18 时，输出如下：

6"

结论

通过上述内容，我们可以看出栈和递归在算法中具有重要的地位。无论是解决复杂问题还是优化计算效率，栈和递归都发挥着关键作用。希望这篇文章能帮助你更好地理解这些概念，并在实践中加以应用。