サブセット生成の2つの方法(インクリメンタル構造法とビットベクトル法)
1690 ワード
このアルゴリズムは--劉汝佳のアルゴリズムコンテストの入門経典から来た.本の中で2種類のアルゴリズムの核心コードを紹介して、しかし過程ごとに詳しく解説していないで、また初心者は文字を読む時とても分かりにくいです
問題に直面したら、まず問題の細部を直接研究するのか、それともまず問題をはっきりさせるのか.
細部を先に研究するのではなく、問題をどのように解決するか、方法の枠組みを構築するかを絶対に学ぶべきだと思います.
方法1:考え方:一度に1つの要素を選択して集合に入れる
方法2:
構想:サブセットA自体を直接構築するのではなく、ビットベクトルb[]を構築する
問題に直面したら、まず問題の細部を直接研究するのか、それともまず問題をはっきりさせるのか.
細部を先に研究するのではなく、問題をどのように解決するか、方法の枠組みを構築するかを絶対に学ぶべきだと思います.
方法1:考え方:一度に1つの要素を選択して集合に入れる
#include <iostream>
using namespace std;
int a[20];
/* n , cur , 0*/
void print_subset(int n,int* a,int cur){
for (int i=0;i<cur;i++)// ,
cout<<a[i]<<' ';
cout<<endl;//
// , , ,cur > 0, minElem=a[cur-1]+1, 0
int minElem = cur ? a[cur-1] + 1 : 0;
// , print_subset(n,a,cur+1), for ,
// minElem-n-1。
// ( )
for (int i=minElem;i<n;i++) {
a[cur]=i;
//
//cur+1 , , 。
// return , i++,a[cur] ( ) , ...
print_subset(n,a,cur+1);
}
}
int main(){
int n ;
while (cin>>n,n){
print_subset(n,a,0);
}
}
方法2:
構想:サブセットA自体を直接構築するのではなく、ビットベクトルb[]を構築する
#include <iostream>
using namespace std;
bool b[20] = {0}; //
/* n , b ,cur , 0*/
void print_subset(int n,bool* b,int cur) {
// cur n ( )
if(cur == n) {
for (int i=0;i<n;i++){
if(b[i])
cout<<i<<' ';
}
cout<<endl;
return ;
}
b[cur] = true;//
print_subset(n,b,cur+1);//cur+1 ,
b[cur] = false;//
print_subset(n,b,cur+1);//cur+1 ,
}
int main() {
int n ;
while (cin>>n,n) {
print_subset(n,b,0);
}
}