(設計對白) A:我知道這題要用遞迴，阿可是，不知道函式裡面要寫什麼耶... B:為什麼跑出 "回報此問題"，"不回報" 了 = _ = --------------------------------------------------------------- 如果你有上面的困擾，可以參考看看這個格式 這是一位B97的學長教我的，我覺得還蠻實用的，所以PO出來給大家參考 int Function( 1.參數區 ) { 2.條件判斷區 3.遞迴區 } 1.參數區: 通常會放與遞迴有關的參數，例如:座標、層數、index、必要資訊等等， 以判斷我遞迴到哪裡了，是否該停止會跟參數有很大的關係 2.條件判斷區: 這是非常重要的地方，這裡要放一些條件的判斷，判斷遞迴是否該停止，或者跳過某 些層數，或者已經跑到我要的層數，我要輸出了。 3.遞迴區: 真正自己呼叫自己的地方，通常這裡也會有一個或以上條件的判斷，以確定是否符合 題目要求，是否呼叫函式。 --------------------------------------------------------------------------- 舉例來說: The Dictionary (單班期中 雙班好像也有考) http://judgegirl.csie.org/~c2009/2009mid2/3.htm 首先把原字串照字典順序排序後 開始寫函式了 (L是題目要求輸出的長度，N是字串S長度，str是排序後字串，buf暫時存答案) char str[100]; char buf[10]; int L,N; void Findans(int layer) 參數區，這題因為只有一維，所以一個 { "層數"的參數就夠了 int i; if(layer==L){ 這裡就是條件判斷區了，當我layer跑到L， buf[layer]='0'; 就代表，我已經跑了第0,1,2..L-1層共L層 printf("%s\n",buf); 也就是任務完成，不用再遞迴，輸出唄! } else{ for(i=0;i<N;i++){ 這裡就是遞迴區，這題因為是全排列，每個都需 if(Check()==1){ 試試看，所以放了一個for loop。 buf[layer]=str[i]; 這裡Check()就是檢查有沒有符合題意，有的話 Findans(layer+1); 就進行下一層 } } } return ; } int main() { Findans(0); return 0; } 把其他該補上的程式碼補上這題就OK了 =) (#include main() Check() ) 當然，沒有一個方法是萬能的，題目變化多端，整個遞迴式還是要看題目而調整， 不過我覺得學長教了我這東西以後，我想遞迴真的有快了一點，也比較有方向， 不致於完全卡住不知道該寫什麼，所以可以參考看看。 ------------------------------------------------------------------------ 關於什麼時候該用遞迴，我會這樣想: 1.以上面的題目為例，其實如果L固定是3，我可以寫三層迴圈，檢查完，符合題意的 就輸出。 但是L是變動的，我們沒辦法告訴電腦我要跑幾層，而且萬一層數是100層， 或者是層數跟測資有關係，無法馬上確定，寫不出來。 那常常就可以想到"遞迴"。 我只要告訴電腦我哪時候該停止、哪時候進行下一層(呼叫自己)就可以了。 2.或者是像單班功課 Machine 這一題 http://groups.google.com.tw/group/ntucsie-c2009/web/homework-3?pli=1 我想要的答案是個大問題(大機器的成本)，而這個大問題需要好多小問題(較小機器的 成本)來回答我，我才能回答。而小問題又需要小小問題的答案....，這種形式的題目 常常就可以想到遞迴! 我設定function回傳的值是我想要的資訊、條件判斷區判斷多小的問題是直觀解決的， 直接回傳。 (這題是"" The cost of machine A, B, and C of size 1 are x, y, and z. "" 這句話告訴了我們 size 1的cost是多少) 把參數放好、遞迴區寫好，就可以解決這一題了 = ) 當然可能還有很多@@，不過我一時也想不到，(強者可以補上)。 不過也不是什麼題目都給他遞迴下去，能夠用while解決就用while 畢竟遞迴頗浪費空間、也容易發生沒注意到的情況而無限遞迴下去。 大家加油! -- A stoo a day keeps bad grades away Just keep it ! --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.241.197 ※ 編輯: barry800414 來自: 140.112.241.197 (11/17 12:19)