推 zxm20243:睡醒第一推！教學好文XD 11/17 13:41
(設計對白)
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)