分治法在每一层递归上都有三个步骤:
if |P|≤n0 then return(ADHOC(P)) //将P分解为较小的子问题 P1 ,P2 ,…,Pk for i←1 to k do yi ← Divide-and-Conquer(Pi) 递归解决Pi T ← MERGE(y1,y2,…,yk) 合并子问题 return(T)
其中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC§是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时直接用算法ADHOC§求解。算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法,用于将P的子问题P1 ,P2 ,…,Pk的相应的解y1,y2,…,yk合并为P的解。
汉诺塔的传说
汉诺塔:汉诺塔(又称河内塔)问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子,在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定,在小圆盘上不能放大圆盘,在三根柱子之间一次只能移动一个圆盘。
思路:
如果我们有 n >= 2 情况,我们总是可以看做是两个盘 1.最下边的盘 2. 上面的其余盘
/*** * @description: 哈诺塔实现 * @param: num 盘的数量 * @param: a 塔a * @param: b 塔b * @param: c 塔c * @return: void * @author ZhangJiaHao * @date: 2022/1/17 11:39 */ public static void hanoiTower(int num, char a, char b, char c) { // 如果只有一个盘 if (num == 1) { System.out.println("第一个盘从" + a + "->" + c); } else { // 多个盘 我们看作两个部分,1.最下面的一个盘 2.上面的其余盘 // 先把上面的其余盘 a->b hanoiTower(num - 1, a, c, b); // 把最下面的盘 a->c System.out.println("第" + num + "个盘从" + a + "->" + c); // 把b盘的所有盘移动到c b->c hanoiTower(num-1,b,a,c); } }
分治算法最主要的是: