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

汉诺塔递归算法流程图_汉诺塔算法递归表达式(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账号...

(0)
blank

相关推荐

  • 设计模式奠基石——UML关系转化为代码

    设计模式奠基石——UML关系转化为代码

    2021年11月16日
  • sendip linux发包工具

    sendip linux发包工具第一步:安装sendip工具sudoapt-getupdatesudoapt-getinstallsendipmansendip//可以查看sendip的使用方法第二步:使用开启两台虚拟机,在其中一台执行sendip命令,在另一台抓包分析sendip命令格式:sendip网络层传输层数据domainsendip-v-p***-is***-id***-p***-f/-d***

  • typora 免费版, 最后一个beta版本下载[通俗易懂]

    typora 免费版, 最后一个beta版本下载[通俗易懂]连接为官方下载链接,直接复制MD5可迅雷下载亲测可用,和付费版使用体验无差别.1.Windows64bithttps://download.typora.io/windows/typora-setup-x64-0.11.18.exeMD5:12F96372BEE2951ACF5627EA28F8A389**2.Window32bit**https://download.typora.io/windows/typora-setup-ia32-0.11.18.exeMD5:F5036

    2022年10月12日
  • jvm-08.jvm调优工具Arthas[通俗易懂]

    jvm-08.jvm调优工具Arthas[通俗易懂]jvm调优工具Arthas阿尔萨斯官方文档https://arthas.aliyun.com/doc/下载curl-Ohttps://arthas.aliyun.com/arthas-boot.jar启动java-jararthas-boot.jarFullGC_Problem01是我们刚启动的java进程importjava.math.BigDecimal;importjava.util.ArrayList;importjava.util.Date;import

  • eclipse中文乱码解决

    eclipse中文乱码解决1.修改项目的编码格式,或者工作空间的编码格式无法作用到项目里面的java文件的编码格式。2.项目中修改编码格式只有选中Inheritedfromcontainer,该项目的编码格式才会随着工作空间编码格式的改变而改变。3.只要改动了所有文件的编码格式,那么单个java文件的编码格式也会跟着修改。4.别人eclipse的所有java文件的编码格式设置为UTF-8,他用这个编码格式打…

  • 自动生成签名在线_签名生成

    自动生成签名在线_签名生成签名设计地址:www.mgs2s.com(复制到浏览器打开)工具集成签名设计免费版下载,签名设计免费版在线立即生成,简单简体签名设计免费版。最新方便设计公文签名设计颜色保存分享免费版 1、个别字体样式文字不完整,请换一种字体继续转换!增加个性签名图片尺寸,更改文件格式的同时缩小了文件大小,生成速度更快,下载更方便。兼顾使用手机上网的朋友们!    2、朋友们大家早上好,今天有空来给大家分享一下关于…

发表回复

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

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