汉诺塔递归算法流程图_汉诺塔算法递归表达式

汉诺塔递归算法流程图_汉诺塔算法递归表达式(5)练习3—汉诺塔(Hanoi)编程实现把A的n个盘子移动到C(盘子编号是[1,n])每次只能移动1个盘子大盘子只能放在小盘子下面1、汉诺塔—1个盘子2、汉诺塔—2个盘子3、汉诺塔—3个盘子3、汉诺塔—思路其实分2种情况讨论即可(1)当n==1时,直接将盘子从A移动到C(2)当n>1时,可以拆分成3大步骤①将n–1个盘子从A移动到B②将编号为n的盘子从A移动到C③将n–1个盘子从B移动到C

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

汉诺塔(Hanoi)

  • 编程实现把 A 的 n 个盘子移动到 C(盘子编号是 [1, n] )
    每次只能移动1个盘子
    大盘子只能放在小盘子下面
    在这里插入图片描述

1、汉诺塔 — 1个盘子

在这里插入图片描述

2、汉诺塔 — 2个盘子

在这里插入图片描述

3、汉诺塔 — 3个盘子

在这里插入图片描述
在这里插入图片描述

3、汉诺塔 — 思路

  • 其实分 2 种情况讨论即可
    (1)当 n == 1时,直接将盘子从 A 移动到C
    (2)当 n > 1时,可以拆分成3大步骤

    ①将 n– 1 个盘子从 A 移动到B
    在这里插入图片描述
    ② 将编号为 n 的盘子从 A 移动到C
    在这里插入图片描述
    ③将 n– 1 个盘子从 B 移动到C
    在这里插入图片描述
    ✓ 步骤①③ 明显是个递归调用

4、汉诺塔 — 实现

public class Hanoi { 
   
    public static void main(String[] args) { 
   
        new Hanoi().hanoi(3,"A","B","C");
    }

    /** * 将n个碟子从p1挪动到p3 * @param p2 中间的柱子 */
    void hanoi(int n,String p1,String p2,String p3){ 
   
        if (n == 1){ 
   
            move(n,p1,p3);
            return;
        }

        //将p3看作中间柱子,将n-1个碟子从p1移动到p2
        hanoi(n-1,p1,p3,p2);
        move(n,p1,p3);
        //将p1看作中间柱子,将n-1个碟子从p2移动到p3
        hanoi(n-1,p2,p1,p3);
    }

    /** * 将 no号盘子从 from 移动到 to * @param no 碟子 * @param from 开始移动的柱子 * @param to 移动到的柱子 */
    void move(int no, String from,String to){ 
   
        System.out.println("将"+no + "号盘子从" + from + "移动到"+to);
    }
}
运行结果:
将1号盘子从A移动到C
将2号盘子从A移动到B
将1号盘子从C移动到B
将3号盘子从A移动到C
将1号盘子从B移动到A
将2号盘子从B移动到C
将1号盘子从A移动到C

Jetbrains全家桶1年46,售后保障稳定

  • T(n) = 2 ∗ T(n) − 1 + O(1)
    因此时间复杂度是:O(2n)
  • 空间复杂度:O(n)
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/206734.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(1)


相关推荐

  • python进阶(3)json文件与python字典的转化[通俗易懂]

    python进阶(3)json文件与python字典的转化[通俗易懂]序列化与反序列化按照某种规则,把内存中的数据保存到文件中,文件是一个字节序列,所以必须要把内存数据转换成为字节序列,输出到文件,这就是序列化;反之,从文件的字节恢复到内存,就是反序列化;pytho

  • 数仓分层(ODS、DWD、DWS、DWT、ADS)和数仓建模

    数仓分层(ODS、DWD、DWS、DWT、ADS)和数仓建模文章目录一、数仓分层数仓概念ODS(原始数据层)做了哪些事DWD(明细数据层)做了哪些事DWS(服务数据层)做了哪些事DWT(主题数据层)做了哪些事ADS(应用数据层)做了哪些事二、数仓建模常用的建模工具ODS层DWD层DWS层DWT层ADS层一、数仓分层数仓概念什么是数仓:数据仓库是为企业所有决策制定过程,提供所有系统数据支持的战略集合。通过对数据仓库中数据的分析,可以帮助企业改进业务流程、控制成本、提高产品质量等。数据仓库并不是数据的最终目的地,而是为数据最终的目的地做好准备。这些准

  • 转:谷歌离线地图基础[通俗易懂]

    转:谷歌离线地图基础[通俗易懂]一.需要文件gapi3文件夹:存放接口等tilemap文件夹:存放图片gapi.js文件maptool.js文件二.html配置<scripttype="text/javascript"src="gapi.js"></script><scripttype="text/javascript"src="maptool.js">&lt

  • nextline函数_Java中的nextline()函数与next()问题

    nextline函数_Java中的nextline()函数与next()问题【写在前面】importJava.util.*;Scannerin=newScanner(http://System.in);【出现的问题】在循环中相连的nextLine();会出现第一个nextLine();跳过的问题.就像这个样子://部分代码for(inti=0;iSystem.out.println();Stringname=in.nextLine();System.o…

  • java中main方法的作用

    java中main方法的作用main方法是我们学习Java语言学习的第一个方法,也是每个java使用者最熟悉的方法,每个Java应用程序都必须有且仅有一个main方法。在eclipse里可以使用输入main,在按住Alt+/的方式快速创建main方法。可以说main方法是最简单的方法,因为main方法几乎是固定不变得,除了String[]args可以写成Stringargs[],以及args的名称可以改变外,其它所有均不…

  • linux系统移植的一般过程_内核移植的基本步骤

    linux系统移植的一般过程_内核移植的基本步骤在众多嵌入式操作系统中,Linux目前发展最快、应用最为广泛。性能优良、源码开放的Linux具有体积小、内核可裁减、网络功能完善、可移植性强等诸多优点,非常适合作为嵌入式操作系统。一个最基本的Linux操作系统应该包括:引导程序、内核与根文件系统三部分。  嵌入式Linux系统移植主要由四大部分组成:  一、搭建交叉开发环境  二、bootloader的选择和移植  三、kernel的配置、编译、…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号