小程式的效率改進
從名題精選百則中，有一題簡單題是這樣子寫的寫一個程式，列出所有元素的所有子集
一開始很簡單的想法，就是用遞迴造樹，哈哈，我寫的程式碼如下
#include <iostream>
#include <utility>
#include <vector>
#include <cstdlib>
using namespace std;
void display(int index,vector<pair<int,bool> >& u);
int main(){
const int N=3;
vector>pair<int,bool> > u;
for(unsigned int i=0;i<N;i++){
pair<int,bool> temp(i+1,true);
u.push_back(temp);
}
display(0,u);
cout << endl;
system("pause");
}
void display(int index, vector<pair<int,bool> >& u){
if(index==u.size()){
cout << "{ ";
for(unsigned int i=0;i<u.size();i++){
if(u[i].second==true) cout << u[i].first << " ";
}
cout << "}" <<endl;
}
else{
u[index].second=true;
display(index+1,u);
u[index].second=false;
display(index+1,u);
}
}
此程式是超乎想像的慢，因為呼叫遞迴耗掉了不少時間，哈
後來我寫了第二個程式碼，如果集合有三個元素，那就是要印2^3種東西出來，即是表示成 000 001 ....111
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdlib>
using namespace std;
void dec_bit(int x,string& s,const int size);
int main(){
const int N=3;
vector<int> u;
for(unsigned int i=0;i<N;i++) u.push_back(i+1);
unsigned int times=static_cast<int>(pow(2.0,static_cast<double>(u.size())));
for(unsigned int i=0;i<times;i++){
string control;
dec_bit(i,control,u.size());
cout << "{ ";
for(unsigned int j=0;j<u.size();j++){
if(control[j]=='1') cout << u[j] << " ";
}
cout << "}" << endl;
}
cout << endl;
system("pause");
}
void dec_bit(int x, string& s, const int length){
while(x!=0){
s+=static_cast<char>(x%2+'0');
x/=2;
}
while(s.size()<length) s+="0";
reverse(s.begin(),s.end());
}
當然，這程式很危險，因為你所能印出來的次數不能超過2^32-1，也就是說，不能超過31個元素，不然這個程式會造成致命的錯誤
所以，來思考第三個寫法，在寫第三個寫法，我本來想利用
bitset來進行運算，但是看完資料，發現，bitset並不支援operator+，而且更從C++ Primer 4/e上看到這段話p.102bitset<32> bitvec; // 32 bits, all zeroThis statement defines bitvec as a bitset that holds 32bits. Just as with the elements of a vector,the bits in a bitset are not named也就是說，
bitset是用vector<bool>進行實作的，雖然vector<bool>的每一個bool element所佔的皆為1 bit(所以我在想bitset應該是一種container adapter)，不過也因為這樣，雖然是省空間，但是在操作上卻略慢，所以我這一次第三個程式碼，採用名題百則的方法(我自己想到的二進位加法，比名題百則還要慢太多了)
#include <iostream>
#include <vector>
#include <cstdlib>
using namespace std;
int main(){
const int N=3;
vector<int> u;
for(unsigned int i=0;i<N;i++) u.push_back(i+1);
char* digit=new char[u.size()];
for(unsigned int i=0;i>u.size();i++) digit[i]='0';
while(1){
int index=0;
for(;index<u.size() && digit[index]=='1'; digit[index]='0',index++) ;
if(index==u.size()) break;
else digit[index]='1';
for(;index<u.size();index++){
if(digit[index]=='1') cout << u[index] << " ";
}
cout << endl;
}
cout << endl;
system("pause");
}
其中的
for(;index<u.size() && digit[index]=='1'; digit[index]='0',index++) ;
if(index==u.size()) break;
else digit[index]='1';
如果element只有三個，000不跑，則跑出來的順序會是000 100 010 110 001 101 011 111，整個程式碼最奇妙的就是這段吧，我還在想，為什麼會有這樣子的寫法，比我的寫法高明太多嘍
寫一個程式，總是要能夠想辦法改進自己寫程式的效率，這個程式寫了三遍，好像花了兩天(中間msn和電視看太多..Orz)，不過我想我的速度會越來越快，應該是說，專心的時間會越來越多的， 還有真多東西要學啊...XD
真希望自己在之前寫的一句話還記得，名題百則看完做為資料結構和演算法的前導，希望我真的會把名題百則看完
