分治算法
分治算法的基本步骤
@author:qyx 2013/6/3
分治法在每一层递归上都有三个步骤
1） 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
2） 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
3） 合并：将各个子问题地解合并为原问题地解
使用分治算法求解汉诺塔问题:
可以把求解过程分为三步:
1 如果有一个盘 A->C
2 如果盘子数超过两个,我们总是可以看做是两个盘，1最下边的盘，2 上面的盘
1） 先把最上面的盘A->B
2） 把最下边的盘A->C
3） 把B塔的所有盘从B->C
package com.qyx.dac; public class Hanoitower { public static void main(String[] args) { hanoitower(5, ‘A‘, ‘B‘, ‘C‘); } //汉诺塔的移动方法 //使用分治算法 public static void hanoitower(int num,char a,char b,char c) { //如果只有一个盘 if(num==1) { System.out.println("第一个盘从"+a+"->"+c); }else{ //如果盘的数量大于2，那么我可以看做是两个盘：1 最下边的盘 2 上面的盘 //1 先把最上面的盘A->B,移动过程中会使用到c hanoitower(num-1, a,c,b); //2 把最下边的盘A->C System.out.println("第"+num+"个盘从"+a+"->"+c ); //3 把B塔的所有盘从B->C,移动过程使用到a塔 hanoitower(num-1,b,a,c); } } }
原文：https://www.cnblogs.com/qyx66/p/12310259.html