【分治算法】之汉诺塔问题

发布时间:2023年12月22日
汉诺塔问题

三根柱子 把A柱子上的盘子全部挪到C上,且每次挪动的时候 小的必须在大的上面

在这里插入图片描述

分治算法的思想;

分:把一个大问题拆成若干个小的子问题,每个子问题相互独立;

治:求解每个子问题的(递归);

并:把子问题的解合并起来就是大问题的解;

汉诺塔拆分:

我们每次把这些个盘子看成两部分;

- 第一部分:
		最下面的一个大的作为一部分,先把他放在C上;
- 第二部分
		除去最大的剩下的整体作为一部份,再把他放在c上;
### 步骤先把第二部分移动到B上;然后第一部分就可以取出来放到C上;然后再把第二部分移动到C上;

所以剩下的就是递归解决每次拆分的两个部分即可。

package 算法.分治算法.汉诺塔问题;
//递归求解子问题
public class HanuoTower {
    // A B C  三根柱子
    public static void main(String[] args) {
            move(3,'A','B','C');
    }
    /**
     * @param num 盘的数目
     * @param a   a、b、c三根柱子
     * @param b   初始时候盘子都在A上 要把全部盘子移动到C上
     * @param c  每次移动的都是:  相应柱子最上面的盘子
     */
    public static void move(int num, char a, char b, char c) {
        //一、如果只有一个盘 则从A—>C
        if (num==1){
            System.out.println(a+"—>"+c);
        }else {
        //二、盘子数目>=2,我们每次把盘子看成2部分,最下面的一个盘 1,和上面剩余的部分num-1
            //此时分三步走
            //1.先把A上面的所有盘子从A—>B 上面所有的盘子数量为num-1;
                //递归把盘子从A—>B  我们需要借助中间盘C盘 所以C放在中间
            move(num-1,a,c,b);
            //2.把最下面的盘子从A—>C
            System.out.println(a+"—>"+c);
            //3.把B上的盘子从B—>C
                //刚才把第一部分的num-1个盘子从A—>B,所以B->C也是num-1个 借助A盘,所以A放中间
            move(num-1,b,a,c);
        }
    }
}

**简化的思想:
//目的:把a上的盘子挪到c上
public class Main {
    public static void main(String[] args) {
        move(5, 'A', 'B', 'C');
    }
    public static void move(int n, char a, char b, char c) {
        //分两种情况 一只有一个盘子; 二很多盘子
        //一、n==1
        if (n == 1) {
            System.out.println(a + "->" + c);
        } else {
            //二、n>=2  三步走
            //①把上面的n-1个盘子,从a放到b上,c做媒介
            move(n - 1, a, c, b);
            //②把最下面的这个一个盘子从a直接放到c上
            System.out.println(a + "->" + c);
            //③再把b上的n-1个盘子,从b放到c上,a做媒介
            move(n - 1, b, a, c);
        }
    }
}

文章来源:https://blog.csdn.net/m0_48904153/article/details/135142358
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。