暴力递归——汉诺塔问题

简介: 暴力递归——汉诺塔问题

打印n层汉诺塔从最左边移动到最右边的全部过程

暴力递归就是尝试

1)把问题转化为规模缩小了的同类问题的子问题

2)有明确的不需要继续进行递归的条件(base case)

3)有当得到了子问题的结果之后的决策过程

4)不记录每一个子问题的解

补充一点,如果记录每一个子问题的解就是动态规划,后续文章会讲到。

递归方法

假设有3跟柱子,左、中、右,我们细分为如下三个步骤:

1)将1~N-1层圆盘从左 -> 中(大问题,需要继续划分为小问题)

2)将第N层圆盘从左 -> 右(base case)

3)将1~N-1层圆盘从中 -> 右(大问题,需要继续划分为小问题)

递归方法改进版

如果我们忘记柱子的左中右,将三根柱子标记为from、to、other。我们实现的是,将所有的圆盘(一共N层)从from -> to,同样细分为3个步骤:

1)将1~N-1层圆盘从from -> other(大问题,需要继续划分为小问题)

2)将第N层圆盘从from -> to(base case,可以直接打印)

3)将1~N-1层圆盘从other -> to(大问题,需要继续划分为小问题)

貌似没什么改进,因为还是细分这三步,同样要递归,但关键在于忘掉柱子的左中右顺序,只需要三个变量,代码可以少很多。

总结

汉诺塔问题还有非递归的解法,因为任何递归都可以改成非递归,只需要自己设计压栈。但是博主个人认为汉诺塔的递归方法比非递归更好容易理解和实现,非递归自己去设计压栈还比较麻烦,博主目前也还没弄懂,所以就只附上代码了。后面如果搞懂了在补充吧,😄

附上完整代码

package com.harrison.class12;
import java.util.Stack;
public class Code01_Hanoi {
  public static void leftToRight(int n) {
    if(n==1) {
      System.out.println("move 1 from left to right");
      return ;
    }
    leftToMid(n-1);
    System.out.println("move "+ n +" from left to right");
    midToRight(n-1);
  }
  public static void leftToMid(int n) {
    if(n==1) {
      System.out.println("move 1 from left to mid");
      return ;
    }
    leftToRight(n-1);
    System.out.println("move "+ n +" from left to mid");
    rightToMid(n-1);
  }
  public static void midToRight(int n) {
    if(n==1) {
      System.out.println("move 1 from mid to right");
      return ;
    }
    midToLeft(n-1);
    System.out.println("move "+ n +" from mid to right");
    leftToRight(n-1);
  }
  public static void midToLeft(int n) {
    if(n==1) {
      System.out.println("move 1 from mid to left");
      return ;
    }
    midToRight(n-1);
    System.out.println("move "+ n +" from mid to left");
    rightToLeft(n-1);
  }
  public static void rightToLeft(int n) {
    if(n==1) {
      System.out.println("move 1 from right to left");
      return ;
    }
    rightToMid(n-1);
    System.out.println("move "+ n +" from right to left");
    midToLeft(n);
  }
  public static void rightToMid(int n) {
    if(n==1) {
      System.out.println("move 1 from right to mid");
      return ;
    }
    rightToLeft(n-1);
    System.out.println("move "+ n +" from right to mid");
    leftToMid(n-1);
  }
  public static void hanoi1(int n) {
    leftToRight(n);
  }
  public static void f(int n,String from,String to,String other) {
    if(n==1) {
      System.out.println("move 1 from "+ from + " to " + to);
    }else {
      f(n-1, from, other, to);
      System.out.println("move " + n + " from " +from +" to "+to);
      f(n-1, other,to,from);
    }
  }
  public static void hanoi2(int n) {
    if(n>0) {
      f(n, "left", "right", "mid");
    }
  }
  public static class Record {
    public boolean finish1;
    public int base;
    public String from;
    public String to;
    public String other;
    public Record(boolean f1, int b, String f, String t, String o) {
      finish1 = false;
      base = b;
      from = f;
      to = t;
      other = o;
    }
  }
  public static void hanoi3(int N) {
    if (N < 1) {
      return;
    }
    Stack<Record> stack = new Stack<>();
    stack.add(new Record(false, N, "left", "right", "mid"));
    while (!stack.isEmpty()) {
      Record cur = stack.pop();
      if (cur.base == 1) {
        System.out.println("Move 1 from " + cur.from + " to " + cur.to);
        if (!stack.isEmpty()) {
          stack.peek().finish1 = true;
        }
      } else {
        if (!cur.finish1) {
          stack.push(cur);
          stack.push(new Record(false, cur.base - 1, cur.from, cur.other, cur.to));
        } else {
          System.out.println("Move " + cur.base + " from " + cur.from + " to " + cur.to);
          stack.push(new Record(false, cur.base - 1, cur.other, cur.to, cur.from));
        }
      }
    }
  }
  public static void main(String[] args) {
    int n=3;
    hanoi1(n);
    System.out.println("=======================");
    hanoi2(n);
    System.out.println("=======================");
    hanoi3(n);
    System.out.println("=======================");
  }
}


目录
打赏
0
0
0
0
3
分享
相关文章
20161208理解enq TX - row lock contention
[20161208]理解enq TX - row lock contention.txt >SELECT * FROM v$event_name WHERE name = 'enq: TX - row lock contention'; EVENT#   EVEN...
1111 0
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
本文详细介绍了Maven的项目管理工具特性、安装步骤和配置方法。主要内容包括: Maven概述:解释Maven作为基于POM的构建工具,具备依赖管理、构建生命周期和仓库管理等功能。 安装步骤: 从官网下载最新版本 解压到指定目录 创建本地仓库文件夹 关键配置: 修改settings.xml文件 配置阿里云和清华大学镜像仓库以加速依赖下载 设置本地仓库路径 附加说明:包含详细的配置示例和截图指导,适用于各种操作系统环境。 本文提供了完整的Maven安装和配置
2025年最新版最细致Maven安装与配置指南(任何版本都可以依据本文章配置)
Go语言实战指南 —— Go中的反射机制:reflect 包使用
Go语言中的反射机制通过`reflect`包实现,允许程序在运行时动态检查变量类型、获取或设置值、调用方法等。它适用于初中级开发者深入理解Go的动态能力,帮助构建通用工具、中间件和ORM系统等。
135 62
电脑没有有效IP配置,连不上网怎么办?,解决办法
当电脑出现“本地连接没有有效的IP配置”错误时,通常表示无法正常获取或配置IP地址,导致无法上网。本文介绍了常见原因及解决方法,包括重启路由器和电脑、手动设置IP地址、更新或重新安装网卡驱动、检查DHCP服务是否开启等步骤,帮助你快速恢复网络连接。
161 59
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问