分治法求解汉诺塔问题

叁歲伎倆 2023-07-15 09:15 106阅读 0赞

汉诺塔问题简介：  
**汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。**

A             B                C

![在这里插入图片描述][20200316132235900.png]

**思路：**  
\*\*\*1.只有一个盘的时候：直接将盘从A->C;

2.当盘数大于如果n>=2时  
1） 将盘看成两部分，最下面一个盘为下部分，第1到第n-1个盘为上面部分  
2） 将上面部分的盘全部A-B,借助C

3） 然后将最下面那个盘从A->c

4） 最后借助A将B->C

Java代码：

package com.yg.algorithm;/*
    分治算法的代表汉诺塔问题
    */
    
    public class HanoiTowers {
        public static void main(String[] args) {
        hanoiTowers(3,'A','B','C');
        }
    
        public static void hanoiTowers(int num, char a, char b, char c) {
            if (num == 1) {
                System.out.println("第一个盘从" + a + "->" + c);
            } else {
                //如果n>=2时
                //将盘看成两部分，最下面一个盘为下部分，第1到第n-1个盘为上面部分
                //将上面部分的盘全部A-B,借助C
                hanoiTowers(num - 1, a, c, b);
                //然后将最下面那个盘从A->c
                System.out.println("第"+num+"个盘从" + a + "->" + c);
                //最后借助A将B->C
                hanoiTowers(num - 1, b, a, c);
            }
        }
    }

[20200316132235900.png]: /images/20230528/1345642948954d92968df22770926e30.png

发表评论取消回复

表情：

评论列表（有 0 条评论，106人围观）

还没有评论，来说两句吧...

相关阅读

相关递归求解汉诺塔问题

前言博主之前有写过关于递归问题的思维模式： [递归的思路][Link 1] 下面将用这种思维模式来求解经典汉诺塔问题。一、问题描述汉诺塔（又称河内塔

本是古典何须时尚/ 2023年09月29日 09:54/ 0 赞/ 103 阅读

相关分治法求解汉诺塔问题

汉诺塔问题简介：汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵

叁歲伎倆/ 2023年07月15日 09:15/ 0 赞/ 107 阅读

相关分治算法与汉诺塔问题

分治算法 1. 分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问

不念不忘少年蓝@/ 2023年07月12日 14:24/ 0 赞/ 83 阅读

相关汉诺塔问题求解办法

汉诺塔问题古老的历史，我们在实际中就不去纠结了，直接看大致描述：有三个柱子，分别为A,B,C，在A柱子上，有n个从大到小堆在一起的盘子，现在要借助B柱子，把A上面的盘子

妖狐艹你老母/ 2023年05月22日 06:38/ 0 赞/ 59 阅读

相关分治法基本思想（汉诺塔问题 Tower of Hanoi）

文章目录前言基本思想适用的问题求解步骤分治法要点

古城微笑少年丶/ 2023年03月13日 05:24/ 0 赞/ 63 阅读

相关分治算法：汉诺塔问题

1，基本介绍分治算法是一种重要的算法。基本思想就是“分而治之”，将一个复杂的问题分为多个相似的子问题，然后再把子问题分为更小的子问题，直到最后子问题可以以一种最简

水深无声/ 2023年02月28日 01:27/ 0 赞/ 92 阅读

相关分治法思想递归解决汉诺塔问题

分治思想当我们求解某些问题时，由于这些问题要处理的数据相当多，或求解过程相当复杂，使得直接求解法在时间上相当长，或者根本无法直接求出。对于这类问题，我们往往先把它

妖狐艹你老母/ 2023年02月16日 06:03/ 0 赞/ 85 阅读

相关汉诺塔问题求解

汉诺塔问题的描述如下：有3根柱子A、B和C，在A上从下往上按照从小到大的顺序放着64个圆盘，以B为中介，把盘子全部移动到C上。移动过程中，要求任意盘子的下面要么没有盘子，要

本是古典何须时尚/ 2022年09月29日 14:55/ 0 赞/ 197 阅读

相关求解汉诺塔问题

汉诺塔是经典问题。具体表述为：由很多放置在三个塔座上的盘子组成的一个古老难题，所有盘子直径都是不同的，盘子中央都有一个洞使他们刚好可以放在塔座上。所有的盘子刚开始放在塔座A上

你的名字/ 2022年09月25日 12:14/ 0 赞/ 205 阅读

相关汉诺塔问题求解

汉诺塔问题的描述如下：有3根柱子A、B和C，在A上从下往上按照从小到大的顺序放着64个圆盘，以B为中介，把盘子全部移动到C上。移动过程中，要求任意盘子的下面要么没有盘子，要么只

r囧r小猫/ 2022年04月08日 09:20/ 0 赞/ 483 阅读