【Leetcode每日一题】 递归 - 面试题 08.06. 汉诺塔问题（难度⭐）（33）

1. 题目解析

题目链接：面试题 08.06. 汉诺塔问题

这个问题的理解其实相当简单，只需看一下示例，基本就能明白其含义了。

2.算法原理

这是一道关于递归算法的经典问题——汉诺塔。我们可以通过分析不同规模的情况来深入理解其解决思路：

1. 基础情况：
   • 当n = 1时，即只有一个盘子，我们直接将这个盘子从A柱移动到C柱。
2. 简单情况：
   • 当n = 2时，需要借助B柱来移动。具体步骤为：
     • 将A柱最上面的盘子移动到B柱；
     • 将A柱剩下的盘子（即最大的那个）移动到C柱；
     • 最后将B柱的盘子移动到C柱。
3. 一般情况：
   • 当n > 2时，我们可以采用递归的思想来解决问题。将A柱上的n个盘子移动到C柱的步骤为：
     • 递归地将A柱上最上面的n-1个盘子移动到B柱；
     • 将A柱剩下的最大盘子移动到C柱；
     • 递归地将B柱上的n-1个盘子移动到C柱。

算法设计：

递归函数hanota(A, B, C, n)用于解决汉诺塔问题，其中A、B、C分别表示三个柱子上的盘子，n表示当前需要处理的盘子个数。

• 返回值：无返回值（void）。
• 参数：
  • vector<int>& A：A柱子上的盘子序列（从上到下）。
  • vector<int>& B：B柱子上的盘子序列（从上到下）。
  • vector<int>& C：C柱子上的盘子序列（从上到下）。
  • int n：当前需要处理的盘子个数。

递归函数流程：

1. 基本情况处理：
   • 如果n == 1，直接将A柱子的最上面一个盘子移动到C柱子。
2. 递归处理：
   • 递归调用hanota(A, C, B, n-1)，将A柱子上的n-1个盘子移动到B柱子。
   • 将A柱子的最上面一个盘子（即最大的那个）移动到C柱子。
   • 递归调用hanota(B, A, C, n-1)，将B柱子上的n-1个盘子移动到C柱子。

通过以上递归函数的设计，我们可以解决任意规模的汉诺塔问题。递归的核心思想是将问题分解为更小的子问题，直到子问题变得足够简单，可以直接解决。在汉诺塔问题中，我们通过递归将n个盘子的移动问题分解为n-1个盘子的移动问题，从而逐步简化问题直至解决。

3.代码编写

class Solution 
{
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C) 
    {
        dfs(A, B, C, A.size());
    }
    void dfs(vector<int>& a, vector<int>& b, vector<int>& c, int n)
    {
        if(n == 1)
        {
            c.push_back(a.back());
            a.pop_back();
            return;
        }
        dfs(a, c, b, n - 1);
        c.push_back(a.back());
        a.pop_back();
        dfs(b, a, c, n - 1);
    }
};

The Last

嗯，就是这样啦，文章到这里就结束啦，真心感谢你花时间来读。

觉得有点收获的话，不妨给我点个赞吧！

如果发现文章有啥漏洞或错误的地方，欢迎私信我或者在评论里提醒一声~