轉自：
http://www.tkk7.com/dengyin2000/archive/2006/03/12/34902.html大學的數據結構和算法根本就是混過來的，某天在某某論壇里有個關于數據結構和算法到底在日常的編程到底有多大的用處。對于我來說，我并不覺得我用上了那些講的數據結構和算法。Java Collection Framework已經跟我們做了這些。我已經能非常熟練的使用Collection里面的類庫。但是我們用的基本上都是那些線性集合（堆棧，隊列，列表，Set），非線性集合（樹，堆，散列和圖）我感覺比較少用到。我也主要是想對非線性集合做一些比較。線性集合比較簡單。
第一章到第九章都是講線性集合， 也比較容易理解， 在這里就忽略掉。第十章是講遞歸算法。我對這章比較感興趣，用遞歸實現某個算法真的感覺非常優雅，代碼短而少，許多非線性集合都是用遞歸來實現的。但也有他的缺點， 對方法的每次遞歸調用都會生成新的局部變量和局部參數。假如遞歸層次太多的話，就會消耗太多的stack。
任何遞歸定義都必須有一個非遞歸部分；這個非遞歸部分叫做基本情況，它使的遞歸跳出無窮循環遞歸。
Ex 1： 1~N的累加過程，數值1～N的累加可以看成是1～N－1的累加加上N。
public int sum(int num){
int result = 0;
if (num == 1){
return 1;
}
return result + num + sum(num - 1);
}
這里的基本情況就是但num＝＝1的時候。 當然這個可以不用遞歸來處理，用一個for就行了（而且比用遞歸更直觀）。我們必須能判斷什么時候使用遞歸，什么時候不使用遞歸，所有問題都可以使用迭代（for循環）解決問題。不過有些情況下，迭代方式過于復雜，對某些問題，遞歸可以寫出短小而優雅的代碼。
直接遞歸和間接遞歸，方法調用自己，這就是直接遞歸（如上個例子）。方法調用另一個方法，最終導致再調用原方法。這就是間接遞歸。
河內塔問題（Towers of Hanoi）（可以上網找找這個經典問題的描述）
規則：
l 一次只能移動一張圓盤
l 不能將大盤放在小盤的上方
l 除了那張在柱子之間搬動的圓盤之外，所有圓盤都必須在某根柱子上
策略：
l 將最上方的N－1張圓盤從最初的柱子移到那根多處的柱子上
l 將最大的圓盤從最初的柱子移動到最終的柱子上
l 再將那個多出柱子上的N－1張圓盤移到最終的柱子上
public class TowersOfHanoi{
private int totalDisks;
// ------------------------------------------------------
// Sets up the puzzle with the specified number of disks
// ------------------------------------------------------
public TowersOfHanoi(int disks){
this.totalDisks = disks;
}
// ----------------------------------------------------------
// Performs the initial call to moveTower to solve the puzzle.
// Moves the disks from tower 1 to tower 3 using tower 2
// ----------------------------------------------------------
public void solve(){
moveTower(totalDisks, 1, 3,2);
}
// -----------------------------------------------------------------
// Moves the specified number of disks from one tower to another by
// moving a subtower of n-1 disks out of the way, moving one disk,
// then moving the subtower back, Base case of 1 disk.
// -----------------------------------------------------------------
private void moveTower(int numDisks, int start, int end, int temp) {
if (numDisks == 1){
moveOneDisk(start, end);
}else{
moveTower(numDisks-1, start, temp, end);
moveOneDisk(start, end);
moveTower(numDisks-1, temp, end, start);
}
}
private void moveOneDisk(int start, int end) {
System.out.println("Move one disk from " + start + " to " + end);
}
}
posted on 2007-06-19 15:20
★yesjoy★ 閱讀(300)
評論(0) 編輯 收藏 所屬分類:
算法總結