Java十大经典算法——分治算法

2024-01-09 16:20:37

定义:

分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换)

基本步骤?

1) 分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
2) 解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 3) 合并:将各个子问题的解合并为原问题的解。

应用:

1.?汉诺塔问题

    public static void hanoiTower(int num ,char a,char b,char c){
        //如果只有一个盘
        if(num == 1){
            System.out.println("第一个从 " + a + " 移动到 " + c);
        }else {
            //如果num>=2,总是可以看成两个盘1.最下边的一个盘2.上面所有盘
            //1.把最上边的所有盘A,移动到B,使用C做辅助
            hanoiTower(num - 1, a, c, b);
            //2.把最下边的盘A,移动到C
            System.out.println("第 " + num + " 个从 " + a + " 移动到 " + c);
            //3.把B所有的盘,移动到C,使用A做辅助
            hanoiTower(num - 1, b, a, c);
        }

    }

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