面试题：汉诺塔问题 · 递归

本文介绍: 这道题的名字还是很响的，基本上都能看出来使用递归解题，但是具体怎么实现还是需要细细想一想。

在这里插入图片描述

你好，我是安然无虞。

文章 目录

汉诺塔问题

在这里插入图片描述

汉诺塔 问题

问题 描述

在这里插入图片描述

解题思路

这道题的名字还是很响的，基本上都能看出来使用递归解题，但是具体怎么实现还是需要细细想一想。

我们一步一步来，请看：

在这里插入图片描述

代码详解

class Solution {
public:
    void hanota(vector&lt;int&gt;&amp; A, vector&lt;int&gt;&amp; B, vector&lt;int&gt;&amp; C) 
    {
        // 将 A 上的盘子借助 B 移动到 C 上
        _hanota(A, B, C, A.size());
    }

    void _hanota(vector<int&gt;&amp; A, vector<int>&amp; B, vector<int>&amp; C, int n)
    {
        // 递归出口
        if(n == 1)
        {
            C.push_back(A.back());
            A.pop_back();
            return;
        }

        // 首先将 A 中的 n - 1 个盘子通过 A C 移动到 B 上
        _hanota(A, C, B, n - 1);

        // 然后将 A 中最后一个大盘直接移动到 C 上
        C.push_back(A.back());
        A.pop_back();

        // 最后通过 A B 将 B 上的圆盘移动到C上
        _hanota(B, A, C, n - 1);
    }
};