递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归的突然好空是函数可以通过调用自身来进行递归。其中直接调用自己称为直接递归，而将调用b，b又调用a的递归叫做间接递归。
递归算法的效率比较低，时间和空间开销都很大，但逻辑关系清晰，程序简洁，增加了可读性。

一、汉诺塔问题简介

问题描述：
有三根柱子：A、B、C，A柱上从下到上按从大到小顺序叠放着若干圆盘（如图）。任务是将这些圆盘全部移动到C柱上，并且满足以下规则：

✅ 规则：

一次只能移动一个圆盘；
任何时候都不能将大圆盘放在小圆盘上面；
只能使用三根柱子进行操作。

例三：汉诺塔游戏

#include <iostream>
using namespace std;
void Move(int n, char A, char B, char C)
{
    if (n == 1)
    {
        //圆盘只有一个时，只需将其从A塔移到C塔
        cout << "move " << n << " from " << A << " to " << C << endl;
        }
        else
        {
            Move(n - 1, A, C, B);//递归，把A塔上编号1~n-1的圆盘移到B上，以C为辅助塔
            cout << "move " << n << " from " << A << " to " << C << endl;//把A塔上编号为n的圆盘移到C上
            Move(n - 1, B, A, C);//递归，把B塔上编号1~n-1的圆盘移到C上，以A为辅助塔
            }
}
int main() {
    int n;
    cin>>n;
    Move(n, 'A', 'B', 'C');
    return 0;
    
}

洛谷：P1242

Previous Topic

Back to Lesson

Next Topic