网站优化优化怎么做,公司做网站需要给百度交钱吗,餐馆网站模板,门户网站建站要求分治算法
介绍
分治法是一种很重要的算法#xff0c;字面意思的解释是“分而治之”#xff0c;就是把一个复杂的问题分成两个或更多的相同或相似的子问题#xff0c;再把子问题分成更小的子问题…直到最后子问题可以简单的直接求解#xff0c;原问题的解即子问题解的合并…分治算法
介绍
分治法是一种很重要的算法字面意思的解释是“分而治之”就是把一个复杂的问题分成两个或更多的相同或相似的子问题再把子问题分成更小的子问题…直到最后子问题可以简单的直接求解原问题的解即子问题解的合并。这个技巧是很多高效算法的基础如排序算法快速排序、归并排序傅立叶变换快速傅立叶变换…分治算法可以求解一些经典问题
二分搜索大整数乘法棋盘覆盖合并排序快速排序线性时间选择最接近点对问题循环赛日程表汉诺塔
分治算法的基本步骤
分治算法在每一层递归上都有三个步骤
分解将原问题分解为若干个规模较小相互独立与原问题形式相同的子问题解决若子问题规模较小而容易被解决则直接解否则递归地解各个子问题合并将各个子问题的解合并为原问题的解
分治算法最佳实践 - 汉诺塔
思路分析
如果是只有一个盘A - c
如果我们有 n 2 的情况我们总是可以看做是两个盘1.最下面的盘2.上面的所有盘。
先把上面的盘 A - B把最下面的盘 A - C把 B 塔的所有盘 B - C
代码实现
/*** 分治算法** param num 盘的数量* param a a 塔* param b b 塔* param c c 塔*/
public static void hanoiTower(int num, char a, char b, char c) {// 如果只有一个塔if (num 1) {System.out.println(第 num 个盘从 a - c);} else {// 如果我们有 n 2 的情况我们总是可以看做是两个盘1.最下面的盘2.上面的所有盘。// 1. 先把上面的所有盘 a - b移动过程使用到 chanoiTower(num - 1, a, c, b);// 2. 把最下面的盘 a - cSystem.out.println(第 num 个盘从 a - c);// 3. 把 b 塔的所有盘从 b - c移动过程使用到 ahanoiTower(num - 1, b, a, c);}
}
