Re: [問題] 遞迴產生組合問題

看板C_and_CPP (C/C++)作者Ebergies (火神)時間15年前 (2011/03/13 21:19)推噓1(1推 0噓 3→)

留言4則, 1人參與討論串6/9 (看更多)

※ 引述《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)