递归求解汉诺塔游戏
type
status
date
slug
summary
tags
category
icon
password
😀
汉诺塔的介绍
游戏包括三个柱子和一些不同大小的圆盘，目标是将所有圆盘从一个柱子移动到另一个柱子，遵循以下规则：
  1. 每次只能移动一个圆盘。
  1. 大圆盘不能放在小圆盘上面。
进行的基本步骤
  1. 准备：将三个柱子标记为A、B和C。开始时，将所有圆盘按照从小到大的顺序堆叠在柱子A上，最大的圆盘在最底下。
  1. 移动：要移动圆盘，必须遵循以下规则：
      2. a. 每次只能移动一个圆盘。
      b. 只能从柱子的顶部移动圆盘。
      c. 只能将一个较小的圆盘放在较大的圆盘上面。
  1. 目标：将所有圆盘从柱子A移动到柱子C，可以使用柱子B作为辅助。
根据这些规则，你可以按照以下步骤玩汉诺塔：
  1. 将最上面的圆盘从柱子A移动到柱子C。
  1. 将第二大的圆盘从柱子A移动到柱子B。
  1. 将之前移动到柱子C的最大圆盘放在柱子C上。
  1. 将第二大的圆盘从柱子B移动到柱子C。
重复以上步骤，直到所有圆盘都从柱子A移动到柱子C。
需要注意的是，汉诺塔游戏的解法是递归的，可以通过递归算法来解决。对于n个圆盘，最少需要移动2^n - 1次。
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
备战技术面试？力扣提供海量技术面试资源，帮助你高效提升编程技能，轻松拿下世界 IT 名企 Dream Offer。
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
https://leetcode.cn/problems/hanota-lcci/
力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
class Solution {
    public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        move(A.size(), A, B, C);
        
    }
    
    public int move(int num, List<Integer> A, List<Integer> B, List<Integer> C) {
        if (num == 1) {
        int disk = A.remove(A.size() - 1);  // 移除起始柱子的顶部盘子
        C.add(disk);  // 将盘子放到目标柱子的顶部
        return 1;  // 返回移动的步数
    } else {
        int steps = 0;
        steps += move(num - 1, A, C, B);  // 将 num-1 个盘子从起始柱子移动到辅助柱子
        steps += move(1, A, B, C);  // 将最大的盘子从起始柱子移动到目标柱子
        steps += move(num - 1, B, A, C);  // 将 num-1 个盘子从辅助柱子移动到目标柱子
        return steps;  // 返回总的移动步数
    }
    }
}
问题描述：
求解内容： 给定三个栈A、B和C，初始时A包含N个从小到大的整数，B和C为空。要求通过合法的操作将A中的所有整数移动到C中，并保持相同的顺序。
输入格式：
  • A：一个包含N个从小到大的整数的列表。
  • B：一个空列表。
  • C：一个空列表。
输出格式： A、B和C的状态变化，直到A为空且C包含所有的整数。
解题思路： 使用递归方法解决此问题。基本思想是，如果只有一个盘子，直接将其从A移到C。如果有多于一个盘子，则先将N-1个盘子从A通过C移到B，然后将最大的盘子从A移到C，最后将N-1个盘子从B通过A移到C。
算法描述：
1. 判断盘子的数量num。
2. 如果num为1：
   a. 从A中取出顶部的盘子。
   b. 将该盘子放到C的顶部。
   c. 返回1表示移动了1步。
3. 如果num大于1：
   a. 递归地将num-1个盘子从A通过C移到B。
   b. 移动最大的盘子从A到C。
   c. 递归地将num-1个盘子从B通过A移到C。
   d. 返回总步数。
程序运行结果截图：
notion image
时间及空间复杂度分析：
  • 时间复杂度：O(2^N)。因为对于N个盘子，每次递归都会处理N-1个盘子，这导致了指数级的递归调用。
  • 空间复杂度：O(N)。这是由于递归的深度导致的调用栈的大小。
讨论与总结： 该汉诺塔算法使用递归解决了经典的汉诺塔问题。虽然其时间复杂度相对较高，但考虑到汉诺塔问题的特性，这是最优的解决方案。此算法清晰地展示了如何使用递归来解决问题，并为其他递归问题提供了有益的参考。
 

开往-友链接力