Re: [問題] 遞迴產生組合問題
※ 引述《Ebergies (火神)》之銘言：
: ※ 引述《yauhh (喲)》之銘言：
: : 這樣講就好玩了,現在這個題目是:
: : 請產生 {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);
: 這樣子有很不直覺嗎
#include<stdio.h>
#define size 4
char s[4]={'A','B','C','D'};
int main(void){
for(int i=1 ; i < (1<<size); i++){
for(int j=0 ; j < size; j++)
if(i&(1<<j))putchar(s[j]);
putchar('\n');
}
return 0;
}
這樣不是比較方便嗎？
....
用二進位來看
D | C | B | A set
1 0 0 0 1 A
2 0 0 1 0 B
3 0 0 1 1 AB
4 0 1 0 0 C
5 0 1 0 1 AC
6 0 1 1 0 BC
7 0 1 1 1 ABC
8 1 0 0 0 D
9 1 0 0 1 AD
10 1 0 1 0 BD
11 1 0 1 1 ABD
12 1 1 0 0 CD
13 1 1 0 1 ACD
14 1 1 1 0 BCD
15 1 1 1 1 ABCD
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 123.240.128.241
推
03/14 00:08, , 1F
03/14 00:08, 1F
推
03/14 00:19, , 2F
03/14 00:19, 2F
※ 編輯: firejox 來自: 210.60.107.233 (03/14 17:17)
推
03/14 17:36, , 3F
03/14 17:36, 3F
※ 編輯: firejox 來自: 210.60.107.233 (03/14 18:22)
推
03/14 23:47, , 4F
03/14 23:47, 4F
推
03/15 12:57, , 5F
03/15 12:57, 5F
推
03/15 13:28, , 6F
03/15 13:28, 6F
→
03/15 19:27, , 7F
03/15 19:27, 7F
討論串 (同標題文章)