先來看一下題目:
有三根柱子A,B,C。A柱上有n個盤子,最大的盤子在底下,其餘的圓盤一個比一個小,依次疊上去。每次隻移動一塊圓盤,規定小盤的隻能疊放在大盤的上面,而大盤子不能疊放在小盤子的上面。目標是把n個圓盤從A移動到B上去。
圖1:漢諾塔遊戲過程
那麼如何用遞歸的思想來解這道漢諾塔的題呢?
圖1是漢諾塔的圖解,顯然,用瞪眼法看盤子挪來挪去很容易,如何用代碼來演示出來?
首先說一下這道題的難點:
1. 我們先隻看1號盤子的移動路徑,先B再C然後A最後摞在2號盤子上面,這段怎麼用代碼實現?
2. 如果我們要用遞歸思想的話,我們都知道遞歸的思想是自己先處理一部分,然後把剩下的部分交給別人處理。那麼我們該從何用這個思想寫遞歸函數?
那我們就帶著這些難點去研究這道題。
要將n個圓盤從A移動到B上去,我們可以分成這幾個步驟:
1. 先將1至n-1個盤子從A挪到一個輔助盤上
2. 再把n號盤子從A挪到目標盤子B上
3. 最後將n-1個盤子從輔助盤上挪到目標盤B上(n-1個盤子摞在n號盤子上)
圖2:圖解步驟
下面開始來寫代碼:
創建一個printHanoiTower()方法:
public static void printHanoiTower(int n,String original,String target,String help){
}
函數4個形參分別是盤子號、原空間、目標空間、輔助空間
1.先將1至n-1個盤子從A挪到一個輔助盤上:
public static void printHanoiTower(int n,String original,String target,String help){
printHanoiTower(n-1,original,help,target); // 先把n-1個盤子挪到輔助空間(C)上
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
}
我們來看這個函數,輸出語句中寫兩個變量一個是original另一個是target,這行代碼是用來輸出盤子的移動路徑,現在我們要把“n-1個盤子從原空間(A)挪到輔助空間(C)上”。那我們不妨在這個函數中調用自己(遞歸),然後再考慮實參是什麼,還是和形參一樣n, original, target, help這個順序嗎?不是吧,我們現在想從A到C,是不是應該把目標空間換成輔助空間啊?意思就是把實參help賦值給形參target,讓目標空間變成輔助空間。所以這個遞歸函數的實參順序就是把輔助空間和目標空間換一下位置,即printHanoiTower(n-1,original,help,target);
2.再把n號盤子從A挪到目標盤子B上:
public static void printHanoiTower(int n,String original,String target,String help){
printHanoiTower(n-1,original,help,target); // 先把n-1個盤子挪到輔助空間(C)上
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
}
這個沒有什麼變化,”再把n號盤子從A挪到目標盤子B上”,這句話的代碼體現在System.out.println("把 "+n+" 從 "+original+" 挪到 "+target); 這條輸出語句上。也就是上面的幾層遞歸結束後進行這條語句,把最後一個最長的盤子放到目標空間上。同時這條語句也代表1號盤子摞在其它盤子上。
3. 最後將n-1個盤子從輔助盤上挪到目標盤B上(n-1個盤子摞在n號盤子上)
public static void printHanoiTower(int n,String original,String target,String help){
printHanoiTower(n-1,original,help,target); // 先把n-1個盤子挪到輔助空間(C)上
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
printHanoiTower(n-1,help,target,original); // 讓n-1從輔助空間(C)挪到目標空間(B)上
}
同理,我們現在要把盤子從輔助空間挪到目標空間就把原來original的位置換成help,這倆變量位置互換。
為瞭更快的互換位置,我們在輸出語句上面寫上“把”、“從”、“挪到”的字樣,便於更快的互換。
記住,我們在互換變量的時候隻需要看從哪到哪就可以,剩下那個變量就是沒用到的那個變量。
這道題的主要思想就是,寫好遞歸函數,形參的順序是固定的,之後在調用自己的時候把實參改一下就可以瞭,因為original永遠都是當前位置,target永遠都是你想移動到的那個位置,help永遠都是輔助位置。所以說我們可以把實參寫成original賦給original,實參寫成help賦值給target,這樣就是把n-1個盤子從原空間(A)挪到輔助空間(C)上。
這題代碼基本上就寫完瞭,但是我們還需註意一點,就是當n=1的時候怎麼辦,不能n-1是0啊?對吧?所以我們加一個限制條件if然後return一下結束這個調用,否則的話就往下走接著調用函數,會出現0和負數的情況:
public static void printHanoiTower(int n,String original,String target,String help){
if(n==1){
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
return;
}
printHanoiTower(n-1,original,help,target); // 先把n-1個盤子挪到輔助空間(C)上
// n挪到目標空間(B)上或1摞在大的盤子上面
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
printHanoiTower(n-1,help,target,original); // 讓n-1從輔助空間(C)挪到目標空間(B)上
}
最後把主函數寫上來運行一下代碼看看效果:
public static void main(String[] args) {
printHanoiTower(3,"A","B","C");
}
下面是這題的全部代碼:
public class TowerOfHanoi {
public static void printHanoiTower(int n,String original,String target,String help){
if(n==1){
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
return;
}
printHanoiTower(n-1,original,help,target); // 先把n-1個盤子挪到輔助空間(C)上
// n挪到目標空間(B)上或1摞在大的盤子上面
System.out.println("把 "+n+" 從 "+original+" 挪到 "+target);
printHanoiTower(n-1,help,target,original); // 讓n-1從輔助空間(C)挪到目標空間(B)上
}
public static void main(String[] args) {
printHanoiTower(3,"A","B","C");
}
}
-
扫码下载安卓APP
-
微信扫一扫关注我们微信扫一扫打开小程序手Q扫一扫打开小程序
-
返回顶部