推 yauhh:嗯,就事後而言是直覺. 但一開始分析問題時,不會直接套上迴圈 03/13 22:44
→ yauhh:的思路. 迴圈解是歸納完之後才會寫出對的程式. 03/13 22:45
→ yauhh:就我認知,迴圈只是用來處理資料的手段,而遞迴卻是能夠引用 03/13 22:52
→ yauhh:知識並理解問題的方法,同時也是整理解答的手段.二者相輔相成 03/13 22:53
※ 引述《yauhh (喲)》之銘言：
: : 推 Ebergies:列舉所有組合本來就是這樣, 每多一個 symbol 就多一倍 03/13 19:4
: : → Ebergies:這也是為何 x= 0~N, SUM( C( N, x))= 2^N 的原因 03/13 19:4
: : → Ebergies:而且這題目用迴圈會比用遞迴直覺很多 03/13 19:5
: 這樣講就好玩了,現在這個題目是:
: 請產生 {A,B,C,D} 的子集,使子集生成順序滿足以下條件:
: 1. A, B, C, D 依序生成.
: 2. 任一子集必須在其超集之前生成.
: 請說明使用迴圈有何直覺?
: 我認為在這題使用迴圈根本不直覺. 如果使用迴圈,你要先把產生的子集全都列出來
: 觀察一次,然後想辦法拼湊出各種參數,什麼 flag 或者 swap 規則之類的,想辦法
: 把答案拼湊出來. 但是 flag 和各種交換的規則都是除了這個問題本身之外額外添加的
: 資訊. 用迴圈做,是加油添醋去做出目前你要的答案; 等到將來題目稍微改變,
: 或者處理的輸入資料稍有改變,你還要設法加油添醋把程式改到保證能產生新的結果.
: 然而,使用遞迴解決則非常直覺: 對 {A,B,C,D} 我知道最後一個子集是 ABCD;
: 並且我知道一條遞迴規則是,因為 ABCD 的子集都必須在 ABCD 之前產生,而只要
: 把 ABC 的全部子集的每一個都加上 D 所得的集合加入 ABC 的全部子集,就會得到
: ABCD 的全部子集. 而 ABC 全部子集的產生可仿照 ABCD 子集的產生.
: 所以當我寫這個程式,我只思考子集的處理,至於子集的生成全都由程式做出來.
: 我不必特地把程式寫成某種特別的奇形怪狀去勉強做出答案.
string elements;
vector< string> sets;
vector< string> tempSets;
// 對所有元素
for( int i= 0; i< elements.size(); i++)
{
// 產生只有 elements[i] 的集合
tempSets.clear();
tempSets.push_back( elements[i]);
for( int j= 0; j< sets.size(); j++)
{
// 對所以已知集合, 增加擁有 elements[i] 的集合
// 因為此時 elements[i] 集合已產生, 已知集合亦已產生
// 因此符合新的集合其子集都已先產生的條件
tempSets.push_back( sets[j]+ elements[i]);
}
// 將新產生的集合加入已產生集合行列
sets.insert( sets.end(), tempSets.begin(), tempSets.end());
}
print( sets);
這樣子有很不直覺嗎
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 175.180.110.223
※ 編輯: Ebergies 來自: 175.180.110.223 (03/13 21:20)