1.應用
分治法是一種很重要的演算法，字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題…直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并，
這個技巧是很多高效演算法的基礎，如排序演算法(快速排序，歸并排序)，二分查找，傅立葉變換(快速傅立葉變換)，漢諾塔問題
2.漢諾塔問題
public static void main(String[] args) {
int[] arr = {1,1,2,2,33};
hanoiTower(3,'A','B','C');
}
public static void hanoiTower(int num,char a,char b,char c){
if (num == 1){
System.out.println("將第1個盤從"+ a +"移動到" + c);
}else {
//將上面的盤從a移動到c，移動程序中會經過b
hanoiTower(num - 1,a,c,b);
//將最下面的盤從a移動到c
System.out.println("將第"+ num +"個盤從" + a + "移動到" + c);
//將B塔的所有盤從b移動到c 移動程序會用到a
hanoiTower(num - 1,b,a,c);
}
}
結果
將第1個盤從A移動到C
將第2個盤從A移動到B
將第1個盤從C移動到B
將第3個盤從A移動到C
將第1個盤從B移動到A
將第2個盤從B移動到C
將第1個盤從A移動到C
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/302453.html
標籤：其他