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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!