星期六, 7月 22, 2006

小程式的效率改進

從名題精選百則中,有一題簡單題是這樣子寫的
寫一個程式,列出所有元素的所有子集

一開始很簡單的想法,就是用遞迴造樹,哈哈,我寫的程式碼如下




#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.102

bitset<32> bitvec; // 32 bits, all zero
This 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

真希望自己在之前寫的一句話還記得,名題百則看完做為資料結構和演算法的前導,希望我真的會把名題百則看完

星期四, 7月 20, 2006

寫程式

首先,把blog變寬嘍,這樣子會好一點,而且,寫很少字就讓人認為很多,好像在騙自己一樣....

今天無聊重寫了一下acm 673 parenthesis balance,嗯,寫出讓我自己還算滿意的程式碼(這也是當然,我都不知道重寫幾次了...Orz)



#include <iostream>
#include <string>
#include <vector>
using namespace std;

bool parenthesis_balance(const string& s);

int main(){
string s;
int input_data_sum=0;
cin >> input_data_sum;
getline(cin,s);
for(unsigned int i=0;i<input_data_sum;i++){
getline(cin,s);
if(parenthesis_balance(s)) cout << "Yes" << endl;
else cout << "No" << endl;
}
}

bool parenthesis_balance(const string& s){
vector<char> symbol;
for(unsigned int i=0;i<s.length();i++){
if(s[i]=='[' || s[i]=='(') symbol.push_back(s[i]);
else if(symbol.size()>0 && s[i]==']'&& symbol[symbol.size()-1]=='[')
symbol.pop_back();
else if(symbol.size()>0 && s[i]==')'&& symbol[symbol.size()-1]=='(')
symbol.pop_back();
else return false;
}
if(symbol.empty()) return true;
else return false;
}


粗體的地方,是一開始沒有寫而有Runtime Error,後來修正的,大部分的Runtime Error都是存取非法記憶體

po這個程式碼做什麼呢,只是想測試一下程式碼po在lblog上效果如何XD,一方面...醜媳婦總見公婆,醜程式碼總是要見大眾,所以,我覺得,還是把自己的程式碼po出來讓大家笑一下也好,哈哈

事實上是,想提醒自己,都大一結束了,只能po這種程式碼,未免太好笑,要好好再努力
我旁邊還有一本名題精選百則,今天看過之後,有一半的問題我可以快速解,還有一半的問題需要好好想想,這本看完開始看資結和演算法,希望有此做前導,會比較輕鬆

學MFC呢? 我聽從小蠍的建議,資料結構演算法要學的,MFC也是要看的

雖然 我最近這幾天查到的資料...MFC真的被罵的很慘...反倒是wxWidgets好像是個不錯的東西的樣子

ps:原來html的程式碼是這樣子排版的...我排了快一個小時..Orz

生活

回彰化最大的好處是,有冷氣吹...
不過也因為這樣,常常睡一整天
在家是會寫程式沒錯啦,我也的確沒在偷懶,但是
常常一睡就是五六個小時過去了...這真是要不得....
話說,今天還是正常點睡覺好了~哈

星期二, 7月 18, 2006

C++討論

啊,我終於醒了?昨天我是幾點睡?三點多吧....
昨天josh心情一好,我又用了較為特殊的普通方法抓了C++ ANSI/ISO IEC 14882 2003(簡言之就是C++ standard 2003),兩個人就地討論起來了,從一點到三點,不過,我不能稱之為討論,josh對standard的熟悉度,遠大於我(畢竟我才第一天抓,但是我覺得,我抓完,也不一定會看),變成他跟我說那一頁,我只能靠著Adobe Acobat的ctrl +f 跟他討論,不然就是他提出來,問我,但是我不一定會,哈哈,大部分時間還是他自己想的,由此可知雙方程度有差多少,哈,這樣子討論下來,心情還蠻好,但是也頗糟,好的原因是,有人可以講,真的是一件讓人高興的事

糟的是,這樣子的討論對josh幫助不大,我討厭不能幫助人的感覺

所以現在有想法啦,第一,請josh找別人討論,不然就是,我自己的整體實力還要再整個一直加強加強,不然,不能幫到就算了,如果害到,我會覺得很抱歉的

但是真的覺得,這場晚睡有值得(事實上本來想從昨天開始早睡),哈,期待josh的新的blog整理

星期日, 7月 16, 2006

MFC

MFC Microsoft Fundation Clases

基本上而言是一個很有趣的東西,去翻了ptt programming版精華區才知道,原來匈牙利命名法的好與壞,基本上,MFC是microsoft用來包裝windwos api(windows SDK?),但是MFC的包裝雖然是OO,但是不甚完整,連MS自己開發Office時用的都是自己對windows api重新包裝,而不用MFC,高階Microsoft的開發人員blog上面寫著,就算要用,我也不會用MFC而使用C#

就我所知,連Windows programming 大師 Charles Petzold 都不喜歡MFC,他寫過Windows SDK的書,寫過programming windows with C#,但是就是沒寫過with MFC的

那麼我學MFC,變成一個很有趣的狀況就是了,當大家都在罵時,為什麼我還要學?

當然,有理由是
1. 我書都買了,不學可惜
2. C++ with MFC還是在C++上還能算是一個開發windows programming
所以,現在的我,應該是說,會邊學邊看,為什麼MFC讓那麼多人不喜歡

我對我要學MFC所下的結論是

學MFC不論在技術、現有環境上皆為一件趣事