非常陽春的圈圈叉叉小遊戲,可以兩個人玩,但沒有電腦玩家。
練習和試驗一些基本的JAVA語法、事件,玩玩Swing的component。用JSmooth把檔案包成exe執行檔,可以直接在windows執行。
功能:
1. 兩個玩家玩井字遊戲。當獲勝者出現顯示獲勝者,若至遊戲結束皆無獲勝者則顯示"Draw"。
2. 隨時可按"New Game"或Alt+n開始新遊戲。
執行畫面:
檔案下載:
TicTacToe.rar (149 kb)
非常陽春的圈圈叉叉小遊戲,可以兩個人玩,但沒有電腦玩家。
練習和試驗一些基本的JAVA語法、事件,玩玩Swing的component。用JSmooth把檔案包成exe執行檔,可以直接在windows執行。
功能:
1. 兩個玩家玩井字遊戲。當獲勝者出現顯示獲勝者,若至遊戲結束皆無獲勝者則顯示"Draw"。
2. 隨時可按"New Game"或Alt+n開始新遊戲。
執行畫面:
檔案下載:
TicTacToe.rar (149 kb)
這題要用給定的文法規則,去檢查輸入的句子是否符合文法。我直接暴力的遞迴...
TIP
雖然題目寫"You can assume that all words will be correctly formed",但實際上加了判斷不和語法的單字才拿到AC。
CODE
#include <iostream> #include <vector> using namespace std; enum { A, MOD, BA, DA, LA, NAM, PREDA }; vector<int> loglan; int n; bool vowel(char c){ return ( c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' ); } int convert_loglan(string s, int n){ if( !vowel( s[n-1] ) ) return NAM; if( n == 1 ) return A; if( n == 2 ){ switch( s[0] ){ case 'g': return MOD; case 'b': return BA; case 'd': return DA; case 'l': return LA; } } if( n==5 && (( !vowel(s[0]) && !vowel(s[1]) && vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) ) || ( !vowel(s[0]) && vowel(s[1]) && !vowel(s[2]) && !vowel(s[3]) && vowel(s[4]) )) ) return PREDA; return NAM; } bool predstring(int st, int ed){ if( st == ed ) return (loglan[st] == PREDA); //"PREDA" return (loglan[ed] == PREDA && predstring(st, ed-1)); //"<predstring> PREDA" } bool verbpred(int st, int ed){ return (loglan[st] == MOD && predstring(st+1, ed)); //"MOD <predstring>" } bool predname(int st, int ed){ if( st == ed ) return (loglan[st] == NAM); //"NAM" return (loglan[st] == LA && predstring(st+1, ed)); //"LA <predstring>" } bool preds(int st, int ed){ for(int i=st+1; i<ed; ++i){ if( loglan[i] == A ){ return (preds(st, i-1) && preds(i+1, ed)); //"<preds> A <predstring> -> <preds> A <preds>" } } return predstring(st, ed); //"<predstring>" } bool statement(void){ for(int i=1; i<n; ++i){ if( loglan[i] == MOD ){ bool pv = predname(0, i-1) && verbpred(i, n-1); //"<predname><verbpred>" bool pvp = 0; for(int j=i+1; j<n-1; ++j) pvp += (predname(0, i-1) && verbpred(i, j) && predname(j+1, n-1)); //"<predname><verbpred><predname>" return (pvp || pv); } } return 0; } bool predclaim(void){ if( loglan[0] == DA ){ return preds(1, n-1); //"DA <preds>" } for(int i=1; i<n; ++i){ if( loglan[i] == BA ) return (predname(0, i-1) && preds(i+1, n-1)); //"<predname> BA <preds>" } return 0; } bool sentence(void){ return ( statement() || predclaim() ); } int main(){ string s; while( (cin >> s) && (s[0] != '#') ){ int len = s.size(); if( s[len-1] == '.' ){ s.erase(len-1); loglan.push_back( convert_loglan(s, len-1) ); n = loglan.size(); cout << (sentence() ? "Good" : "Bad!") << endl; //initialize loglan.clear(); } else loglan.push_back( convert_loglan(s, len) ); }//while return 0; }
simulation,類似Josephus problem,照著規則模擬。
CODE
#include <iostream> #define MAX 20 int main(){ int n, k, m; bool a[MAX]; while( scanf("%d%d%d", &n, &k, &m) != EOF ){ if( n==0 && k==0 && m==0 ) break; for(int i=0; i<n; ++i) a[i] = 1; bool printed = 0; int i = -1, j = n, left = n; int cnt_k, cnt_m; while( left > 0 ){ cnt_k = cnt_m = 0; while( cnt_k != k ){ i = (i+1)%n; if( a[i] ) ++cnt_k; } while( cnt_m != m ){ j = (j+n-1)%n; if( a[j] ) ++cnt_m; } if( printed ) printf(","); else printed = 1; if( i == j ){ a[i] = 0; --left; printf("%3d", i+1); } else{ a[i] = a[j] = 0; left -= 2; printf("%3d%3d", i+1, j+1); } }//killing printf("\n"); }//while return 0; }
寫完132,打鐵趁熱繼續寫geometry的題目。這題很複雜,但要解決的問題很清楚,就是求兩個凸多邊形的非交集的面積(xor, 異域)。
我的算法如下:
A: 第一個凸多邊形點集合
B: 第二個凸多邊形點集合
C: A,B交集部分的點集合(初始為空集合)
1. 檢查A的每一個點,若落在B內部或邊上即將該點加入C。
2. 檢查B的每一個點,若落在A內部或邊上即將該點加入C。
3. 檢查A的每一邊,對B的每一邊逐邊檢查是否可以相交,若可相交即求交點,將交點加入C。
4. A,B交集求畢,將C集合的點逆時針排序。
5. 輸出異域面積為 (A + B – C) – C = A + B - 2C
實作方法
檢查P點是否落在圖形內部或邊上
逆時針檢查圖形的每一點,若「每一點到下一點的向量」與「每一點至P點的向量」皆為逆時針旋轉(外積>0),則P點在圖型內部。當外積=0時,P點在圖形邊上。
檢查線段P1P2與P3P4是否相交
單純用外積檢查兩線段是否互相跨立。
當 (P1P2 x P1P3)*(P1P2 x P1P4) < 0 時代表P3, P4分別在線段P1P2的兩端,故外積異號。
當 (P3P4 x P3P1)*(P3P4 x P3P2) < 0 時代表P1, P2分別在線段P3P4的兩端,故外積異號。
當兩者皆成立時,線段P1P2與線段P3P4相交。
相交線段求交點
參考「平面內兩條線段的位置關係判定及交點求解」,用向量法求解,只需用到一次除法,減少精確度的問題。
點逆時針排序
先找最左下方的點,其他的點對該點做逆時針的極角排序。
凸多邊形面積
起點與終點必須為同一個點,即X0Y0 = XnYn,而所有的點必須照順時針或逆時針排序,當點為順時針排序時,總和為負數,逆時針排序時,總和為正數,但兩者絕對值相同。
TIPS
1. 製造測資時可考慮相離、相鄰、相交的情況,而相交的圖形可考慮「其中一圖有點在另一圖中」和「兩個圖形完全沒有點在另一個圖中,但有相交部份」的兩種情況。
2. 輸出時雖然每筆輸出之間不需換行,但最後結尾仍需要換行符號,否則會給WA,不是PE。
REFERENCES
平面內兩條線段的位置關係判定及交點求解
CODE
#include <iostream> #include <vector> using namespace std; struct vertex{ float x, y; }; //return outer product of pa->pb float cross(vertex p, vertex a, vertex b){ return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) ); } float dist(vertex a, vertex b){ return (b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y); } //return true if p is inside or on boundary of g bool inside(vertex p, vector<vertex> g, int n){ int i = n - 1; for(; i>=0 && (cross(g[i], g[(i+n-1)%n], p) >= 0); --i); return (i == -1); } bool intersects(vertex p1, vertex p2, vertex p3, vertex p4){ return ((cross(p1, p2, p3) * cross(p1, p2, p4) < 0) && (cross(p3, p4, p1) * cross(p3, p4, p2) < 0)); } vertex intersection(vertex p1, vertex p2, vertex p3, vertex p4){ float b1 = (p2.y - p1.y)*p1.x + (p1.x - p2.x)*p1.y; float b2 = (p4.y - p3.y)*p3.x + (p3.x - p4.x)*p3.y; float d = (p2.x - p1.x)*(p4.y - p3.y) - (p4.x - p3.x)*(p2.y - p1.y); float d1 = b2*(p2.x - p1.x) - b1*(p4.x - p3.x); float d2 = b2*(p2.y - p1.y) - b1*(p4.y - p3.y); vertex p0; p0.x = d1/d; p0.y = d2/d; return p0; } void check_intersect(vertex p1, vertex p2, vector<vertex> g, int n, vector<vertex> &gc){ for(int i=0; i<n; ++i){ if( intersects(p1, p2, g[i], g[(i+1)%n]) ){ vertex inter = intersection(p1, p2, g[i], g[(i+1)%n]); gc.push_back(inter); } } } //check if ga vertices are inside gb void check_vertices(vector<vertex> ga, int na, vector<vertex> gb, int nb, vector<vertex> &gc, bool calc_inter){ for(int i=0; i<na; ++i){ if( inside(ga[i], gb, nb) ) gc.push_back(ga[i]); if( calc_inter ) check_intersect(ga[i], ga[(i+1)%na], gb, nb, gc); }//i } void sort_vertices(vector<vertex> &g, int n){ if( n > 0 ){ int i, j, m = 0; for(i=1; i<n; ++i) if(g[i].y < g[m].y || (g[i].y == g[m].y && g[i].x < g[m].y)) m = i; swap(g[m], g[0]); for(i=1; i<n; ++i){ m = i; for(j=i+1; j<n; ++j){ float t = cross(g[0], g[m], g[j]); if( t < 0 || (t == 0 && dist(g[0], g[j]) < dist(g[0], g[m])) ) m = j; }//j swap(g[m], g[i]); }//i } } float area(vector<vertex> g, int n){ float a = 0; for(int i=0; i<n; ++i) a += (g[(i+n-1)%n].x * g[i].y) - (g[i].x * g[(i+n-1)%n].y); return (a < 0) ? ( a / -2 ) : (a / 2); } int main(){ int na, nb, nc; //number of vertices of graph a, b, c while( scanf("%d", &na) && (na != 0) ){ vector<vertex> ga, gb, gc; vertex temp; for(int i=0; i<na; ++i){ scanf("%f%f", &temp.x, &temp.y); ga.push_back(temp); } scanf("%d", &nb); for(int i=0; i<nb; ++i){ scanf("%f%f", &temp.x, &temp.y); gb.push_back(temp); } check_vertices(ga, na, gb, nb, gc, 1); check_vertices(gb, nb, ga, na, gc, 0); nc = gc.size(); sort_vertices(gc, nc); printf("%8.2f", area(ga, na) + area(gb, nb) - (2 * area(gc, nc))); }//while printf("\n"); return 0; }
Geometry的題目,給一個圖形的所有端點座標,和圖形的質心座標,要先找出可以讓圖形「站立」的邊,即當該邊水平時,質心在邊上方並在兩端點之間。一個圖形可能有大於一個可以站立的邊,邊的代號為該邊所經過最大編號(依輸入順序)的點,最後要輸出所有可以站立的邊中,最小的邊代號。
我的做法分為兩部分,第一部分是找convex hull,用graham scan,找出圖形的凸包。第二部分用內積檢查凸包的每個邊是否可以讓圖形站立,即質心到邊兩端點的夾角是否都小於90度(內積>0)。
TIPS
UVa討論區有大量本題測資
CODE
#include <iostream> #include <vector> using namespace std; class vertex{ public: int x, y; }; int n; vertex mass; vector<vertex> v; //original order vector<int> p; //vertices id sorted by polar angle //return outer product of pa->pb int cross(vertex p, vertex a, vertex b){ return ( (a.x - p.x)*(b.y - p.y) - (b.x - p.x)*(a.y - p.y) ); } //return true if pa dot pb > 0 (<90 degree) bool dot(vertex p, vertex a, vertex b){ return ( (a.x - p.x)*(b.x - p.x) + (a.y - p.y)*(b.y - p.y) ) > 0; } int dist(vertex a, vertex b){ return ((b.x - a.x)*(b.x - a.x) + (b.y - a.y)*(b.y - a.y)); } //return true if a should be placed first than b to form counter-clockwise order bool issmaller(vertex p, vertex a, vertex b){ int f = cross(p, a, b); return ( f < 0 || ( f == 0 && dist(p, b) < dist(p, a) ) ); } void quicksort(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; (i<=right) && issmaller(v[p[0]], v[p[left]], v[p[i]]); ++i); for(; (j>left) && !issmaller(v[p[0]], v[p[left]], v[p[j]]); --j); if( i >= j ) break; swap(p[i], p[j]); } swap(p[left], p[j]); quicksort(left, j-1); quicksort(j+1, right); } } int main(){ string s; vertex temp; int i, j, tmp, minv, qn; while( (cin >> s) && (s[0] != '#') ){ scanf("%d%d", &mass.x, &mass.y); v.clear(); p.clear(); i = 0; while( scanf("%d%d", &temp.x, &temp.y) ){ if( temp.x == 0 && temp.y == 0 ) break; v.push_back(temp); p.push_back(i++); } n = v.size(); //find lowest-left for(minv=0, i=1; i<n; ++i) if( (v[i].y < v[minv].y) || (v[i].y == v[minv].y && v[i].x < v[minv].x) ) minv = i; swap(p[minv], p[0]); //sort all vertices counter clockwisely by polar angle quicksort(1, n - 1); //graham scan vector<int> q; //stack of convex hull q.push_back(p[0]); q.push_back(p[1]); for(i=2; i<n; ++i){ qn = q.size() - 1; if( (tmp = cross( v[ q[qn-1] ], v[ q[qn] ], v[ p[i] ] )) > 0 ) q.push_back(p[i]); else if( tmp == 0 ){ q.pop_back(); q.push_back(p[i]); } else{ q.pop_back(); --i; } }//i:all vertices q.push_back(p[0]); //find stable sides qn = q.size(); for(minv=n-1, i=1; i<qn; ++i){ if( (cross(v[q[i-1]], mass, v[q[i]])!=0) && (dot(v[q[i-1]], mass, v[q[i]])>0) && (dot(v[q[i]], mass, v[q[i-1]])>0) ) if( (tmp = (q[i] > q[i-1]) ? q[i] : (n - 1)) < minv ) minv = tmp; } cout << s; for(i=s.size(); i<20; ++i) printf(" "); printf("%d\n", minv + 1); }//while return 0; }
給玩家五張撲克牌,桌上有另五張的撲克牌,玩家可選擇捨棄0~5張牌,並從桌上依序補充同數量的牌。輸出可以達到的最大牌型(poker hand)。
用了bool陣列去窮舉所有捨棄牌的方式,遞補相同數量的牌後,再一一檢查牌型。
CODE
#include <iostream> #include <algorithm> using namespace std; enum { C, D, H, S }; enum { SF, FOAK, FH, FL, ST, TOAK, TP, OP, HC }; bool result[9]={0,0,0,0,0,0,0,0,0}; char line[9][16] = {"straight-flush", "four-of-a-kind", "full-house", "flush", "straight", "three-of-a-kind", "two-pairs", "one-pair", "highest-card"}; class poker{ public: int denom; int suit; }; int next(bool *slot); void check(poker *c); int main(){ int i, j, k; poker cards[2][5]; char s[10][3]; i = j = k = 0; while( scanf("%s", s[k]) != EOF ){ if( s[k][0]>='2' && s[k][0]<='9' ) cards[i][j].denom = s[k][0]-'0'; else if( s[k][0] == 'A' ) cards[i][j].denom = 1; else if( s[k][0] == 'T' ) cards[i][j].denom = 10; else if( s[k][0] == 'J' ) cards[i][j].denom = 11; else if( s[k][0] == 'Q' ) cards[i][j].denom = 12; else if( s[k][0] == 'K' ) cards[i][j].denom = 13; switch ( s[k][1] ){ case 'C': cards[i][j].suit = C; break; case 'D': cards[i][j].suit = D; break; case 'H': cards[i][j].suit = H; break; case 'S': cards[i][j].suit = S; break; }//s[0] if( i==0 && j==4 ){ i = 1; j = 0; } else if( i==1 && j==4 ){ int count = 5; bool slot[5]={0, 0, 0, 0, 0}; poker temp[5]; while(1){ j = 0; for(i=0; i<5; ++i){ if( slot[i] ) temp[i] = cards[1][j++]; else temp[i] = cards[0][i]; } check(temp); if( count == 0 ) break; count = next(slot); }//search //output printf("Hand: "); for(i=0; i<5; ++i) printf("%s ", s[i]); printf("Deck: "); for(; i<10; ++i) printf("%s ", s[i]); printf("Best hand: "); for(i=0; i<9 && result[i]==0; ++i); printf("%s\n", line[i]); //initialize for(i=0; i<9; ++i) result[i] = 0; i = j = 0; k = -1; } else ++j; ++k; }//while get data return 0; } int next(bool *slot){ if( slot[0] == 0 ) slot[0] = 1; else{ int i = 0; while( slot[i] == 1 ) slot[i++] = 0; slot[i] = 1; } int count = 0; for(int i=0; i<5; ++i) if( slot[i] == 0 ) ++count; return count; } void check(poker *c){ int denoms[14]={0,0,0,0,0,0,0,0,0,0,0,0,0,0}; int suits[4]={0,0,0,0}; //sort int i, j, min, maxsuit = 0; for(i=0; i<5; ++i){ min = i; for(j=i+1; j<5; ++j) if( c[j].denom < c[min].denom ) min = j; swap(c[i], c[min]); ++denoms[ c[i].denom ]; if( ++suits[ c[i].suit ] > maxsuit ) maxsuit = suits[ c[i].suit ]; } //find if straight bool straight = 0; for(i=1; i<5 && (c[i].denom == c[i-1].denom + 1); ++i); if( i == 5 ) straight = 1; if(!straight && (c[0].denom == 1)){ for(i=2; i<5 && (c[i].denom == c[i-1].denom + 1); ++i); if( i == 5 ) straight = 1; } if( straight ){ if( maxsuit == 5 ) result[SF] = 1; //straight flush else result[ST] = 1; //straight } if( maxsuit == 5 ) result[FL] = 1; //flush int three = 0, two = 0; for(i=1; i<=13; ++i){ switch ( denoms[i] ){ case 4: result[FOAK] = 1; //four of a kind break; case 3: result[TOAK] = 1; //three of a kind ++three; break; case 2: ++two; } }//i if( three == 1 && two == 1 ) result[FH] = 1; // full house else if( two == 2 ) result[TP] = 1; //two pairs else if( two == 1 ) result[OP] = 1; //one pair else result[HC] = 1; //highest card }
終於成功嘗試Ruby on Rails了。安裝的是rails 3.0.0,一些以舊版rails為基礎的教學文件語法不同,後來找到了rails 3版本的教學文件"Getting Started with Rails",終於step by step照著敲出了個最基礎的blog平台,有blog文章增刪修、comment增刪、tag,三項功能。
資料庫使用的是預設的SQLite,先照著查到的資料排除找不到"sqlite3.dll"的錯誤訊息。
不知不覺把121 - 130寫完了,這10題練習了C++的vector、string和其提供的函式。題目本身的話,印象最深的是DP的"125 – Numbering Paths"和學到運用餘數的"128 – Software CRC"。
simulation,但規則有點看不懂,看了中譯才搞清楚...
CODE
#include <iostream> #include <vector> using namespace std; int n, k; int kill(int i, vector<int> v); int main(){ int i, t; vector<int> r; while( (cin >> n >> k) && (n != 0) ){ r.clear(); for(i=1; i<=n; ++i) r.push_back(i); t = kill(0, r) - 1; t = (n - t) % n; cout << t + 1 << endl; }//while return 0; } int kill(int i, vector<int> v){ int p; --i; while( v.size() > 1 ){ i = p = (i+k) % v.size(); //p: killed v.erase(v.begin()+i); i = (i+k-1) % v.size(); //i: burier v.insert(v.begin()+p, v[i]); if( i >= p ) ++i; v.erase(v.begin()+i); if( i >= p ) i = p % v.size(); else i = (p - 1) % v.size(); } return v[0]; }
生成所有排序(permutations),但要檢查生成的permutation是否有連續的重複組合,如有連續的重複組合即為無效的permutatoin,若否則為有效的permutation。如"ABAB"為無效,因連續出現"AB"組合,但"ABCAB"則為有效。輸出指定的第n個有效permutation。
CODE
#include <iostream> using namespace std; #define MAX 80 int n, let, seqn; bool check(char *s, int len); void gen(char *s, int len); void output(char *s, int len); int main(){ char s[MAX]; while( (cin >> n >> let) && (n != 0) ){ seqn = 0; gen(s, 0); }//while return 0; } //return true if string is "hard", false when "easy" bool check(char *s, int len){ int i, j, k; for(i=0; i<len; ++i){ for(j=0; j<i; ++j){ for(k=j; k<i && s[k]==s[i+k-j]; ++k) ;//k if( k == i ) return false; }//j }//i return true; } void gen(char *s, int len){ for(int i=0; i<let && seqn<n; ++i){ s[len] = 'A' + i; s[len+1] = '\0'; if( check(s, len+1) ){ if( ++seqn == n ){ output(s, len+1); return; } if( seqn < n ) gen(s, len+1); } }//i } void output(char *s, int len){ for(int i=0; i<len; ++i){ if( i == 64 ) cout << endl; else if( i>0 && i%4==0 ) cout << ' '; cout << s[i]; }//i cout << endl << len << endl; }
simulation。給52張撲克牌,向左一張或左三張合併同數字或同花色,輸出合併完成後剩下的堆數和每一堆的張數。每合併一次,要檢查是否可以繼續再向左合併。
CODE
#include <iostream> using namespace std; #define MAX 52 int main(){ int i, j, k, moveto; char pile[MAX][MAX+MAX], remain[MAX]; int len[MAX]; while( (cin >> pile[0]) && (pile[0][0] != '#') ){ len[0] = 2; for(i=1; i<MAX; i++){ cin >> pile[i]; len[i] = 2; }//i: read in all cards i=1; while( i < MAX ){ moveto = i; for(j=i-1; j>=0 && len[j]==0; --j);//1 left if( (j >= 0) && (pile[j][ len[j]-2 ] == pile[i][ len[i]-2 ] || pile[j][ len[j]-1 ] == pile[i][ len[i]-1 ]) ) moveto = j; for(--j; j>=0 && len[j]==0; --j);//2 left for(--j; j>=0 && len[j]==0; --j);//3 left if( (j >= 0) && (pile[j][ len[j]-2 ] == pile[i][ len[i]-2 ] || pile[j][ len[j]-1 ] == pile[i][ len[i]-1 ]) ) moveto = j; if( i != moveto ){ len[i] -= 2; pile[moveto][ len[moveto]++ ] = pile[i][ len[i] ]; pile[moveto][ len[moveto]++ ] = pile[i][ len[i]+1 ]; i = moveto; } else for(++i; i<MAX && len[i]==0; ++i); } k = 0; for(i=0; i<MAX; i++) if( len[i] > 0 ) remain[k++] = i; cout << k << ( k == 1 ? " pile" : " piles" ) << " remaining:"; for(i=0; i<k; i++) cout << ' ' << (len[ remain[i] ] / 2); cout << endl; }//while return 0; }
給多項式,輸出x降冪y升冪排序後的多項式相乘結果。重點在於字串處理,要找到方法把輸入字串拆解出可以運算的係數及次方數。
TIPS
記得移除(不要輸出)合併同類項後係數為0的項
CODE
#include <iostream> #include <sstream> #include <vector> #include <string> #include <cstring> using namespace std; class term{ public: int coef; //coefficient int pow_x; int pow_y; }; vector<term> poly[2], result; void get_terms(int no, string s); void multiply(term a, term b); void sort_terms(int left, int right); void comb_terms(void); bool isbigger(int a, int b); string atostring(int num); int main(){ int i, j, n; string s, line1, line2; while( cin >> s ){ if( s[0] == '#' ) break; get_terms(0, s); cin >> s; get_terms(1, s); result.clear(); for(i=0; i<poly[1].size(); i++) for(j=0; j<poly[0].size(); j++) multiply(poly[1][i], poly[0][j]); sort_terms(0, result.size()-1); //sort comb_terms(); //combine like terms line1.clear(); line2.clear(); for(i=0; i<result.size(); i++){ //sign if( i > 0 ){ line1.append(" "); if( result[i].coef > 0 ) line2.append(" + "); else line2.append(" - "); } //coefficient if( result[i].coef < 0 ){ result[i].coef *= -1; if( i==0 ){ line1.push_back(' '); line2.push_back('-'); } } if( result[i].coef > 1 ){ s = atostring(result[i].coef); line2.append(s); n = s.size(); for(j=0; j<n; j++) line1.push_back(' '); } else if( result[i].coef == 1 && result[i].pow_x == 0 && result[i].pow_y == 0 ){ line1.push_back(' '); line2.push_back('1'); } //power of x if( result[i].pow_x >= 1 ){ line1.push_back(' '); line2.push_back('x'); } if( result[i].pow_x > 1 ){ s = atostring(result[i].pow_x); line1.append(s); n = s.size(); for(j=0; j<n; j++) line2.push_back(' '); } //power of y if( result[i].pow_y >= 1 ){ line1.push_back(' '); line2.push_back('y'); } if( result[i].pow_y > 1 ){ s = atostring(result[i].pow_y); line1.append(s); n = s.size(); for(j=0; j<n; j++) line2.push_back(' '); } }//i cout << line1 << endl << line2 << endl; }//while return 0; } void get_terms(int no, string s){ poly[no].clear(); //initialize polynomial vector term temp; string number; int sign = 1; int size = s.size(); char flag = '+'; for(int i=0; i<=size; i++){ if( i==0 || i == size || s[i] == '+' || s[i] == '-' ){ //if end of term if( i > 0 ){ if( flag == '+' || flag == '-' ) temp.coef = atoi(number.c_str()) * sign; else if( flag == 'x' ){ if( s[i-1] == 'x' ) temp.pow_x = 1; else temp.pow_x = atoi(number.c_str()); } else if( flag == 'y' ){ if( s[i-1] == 'y' ) temp.pow_y = 1; else temp.pow_y = atoi(number.c_str()); } poly[no].push_back(temp); } //initialize term temp.coef = temp.pow_x = temp.pow_y = 0; sign = 1; flag = '+'; number.clear(); //new term if( i < size && s[i] == '-' ){ sign = -1; flag = '-'; } }//term break point if( s[i] == 'x' || s[i] == 'y' ){ if( i == 0 ) temp.coef = sign; else if( flag == '+' || flag == '-' ){ if( s[i-1] == flag ) temp.coef = sign; else temp.coef = atoi(number.c_str()) * sign; } else if( flag == 'x' ){ if( s[i-1] == 'x' ) temp.pow_x = 1; else temp.pow_x = atoi(number.c_str()); } else if( flag == 'y' ){ if( s[i-1] == 'y' ) temp.pow_y = 1; else temp.pow_y = atoi(number.c_str()); } flag = s[i]; number.clear(); } else if( s[i] >= '0' && s[i] <= '9' ) number.push_back(s[i]); }//i } void multiply(term a, term b){ term temp; temp.coef = a.coef * b.coef; temp.pow_x = a.pow_x + b.pow_x; temp.pow_y = a.pow_y + b.pow_y; result.push_back(temp); } void sort_terms(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; i<=right && !isbigger(i, left); i++); for(; j>left && isbigger(j, left); j--); if( i >= j ) break; swap(result[i], result[j]); }//while swap(result[j], result[left]); sort_terms(left, j-1); sort_terms(j+1, right); } } //return true when a>b, false when a<=b bool isbigger(int a, int b){ if( result[a].pow_x < result[b].pow_x ) return true; if( result[a].pow_x > result[b].pow_x ) return false; if( result[a].pow_y > result[b].pow_y ) return true; return false; } void comb_terms(void){ int i = 0; while( i < result.size() ){ if( result[i].coef == 0 ) result.erase(result.begin()+i); else if( i < (result.size()-1) && (result[i].pow_x == result[i+1].pow_x) && (result[i].pow_y == result[i+1].pow_y) ){ result[i].coef += result[i+1].coef; result.erase(result.begin()+i+1); } else i++; } } string atostring(int num){ stringstream ss; ss << num; return ss.str(); }
這題頗有挑戰性,給有向圖(directed graph),要找出圖上是否有環(cycle),也要找出所有點之間存在的所有路徑數量,當路徑經過環(即代表路徑數量無窮大),路徑數量要輸出-1。
我的作法是先以dp(Floyd-Warshall做變化)找出所有點之間存在的所有路徑數量,接著判斷是否有k->k (k = 1….n)路徑存在,若存在即為環存在,再跑一次迴圈將所有可與k相連的路徑的值設為-1。
在寫的時候原本Floyd-Warshall的觀念還是沒想清楚,在最外面多加了一層算「經過幾個點」的迴圈,寫出來超冗長且bug連連。後來改用recursive去產出所有組合,想當然Time Limit Exceed。苦思良久才領悟到不必多加那一層迴圈,也搞清楚找到環以後如何去刪掉所有受影響的節點了。柳暗花明,最後看到了清爽的程式碼 :))
不過仍然是跑了兩次三層迴圈,應該算O(2 * n^3)吧,一定可以更省,就繼續研究吧。
CODE
#include <iostream> using namespace std; #define MAX 30 int main(){ int i, j, k; int maxn, side, d1, d2, total; int matrix[MAX][MAX]; //total number of paths total = 0; while( cin >> side ){ for(i=0; i<MAX; i++) for(j=0; j<MAX; j++) matrix[i][j] = 0; maxn = -1; for(i=0; i<side; i++){ cin >> d1 >> d2; matrix[d1][d2] = 1; if( d1 > maxn ) maxn = d1; if( d2 > maxn ) maxn = d2; } maxn++; //findout all paths for(k=0; k<maxn; k++) for(i=0; i<maxn; i++) for(j=0; j<maxn; j++) if( matrix[i][k] * matrix[k][j] > 0 ) matrix[i][j] += matrix[i][k]; //eliminate paths involved cycles for(k=0; k<maxn; k++) if( matrix[k][k] != 0 ) //cycle for(i=0; i<maxn; i++) for(j=0; j<maxn; j++) if( matrix[i][k] * matrix[k][j] != 0 ) matrix[i][j] = -1; //output cout << "matrix for city " << total << endl; for(i=0; i<maxn; i++){ cout << matrix[i][0]; for(j=1; j<maxn; j++) cout << ' ' << matrix[i][j]; cout << endl; } total++; }//while return 0; }
真開心再用vector寫出了這題,嘗試用vector的push_back()及erase()產生所有的組合。在取出元素時檢查未被取出的元素是否有小於該元素的元素(小的元素應該先被取出)。
這題是給一些元素,再給其中部分元素的大小關係,依字典順序輸出在給定的大小關係下所有可能的元素組合。
CODE
#include <iostream> #include <vector> #include <algorithm> using namespace std; #define MAX_LET 26 vector<char> vars; //variables bool consts[MAX_LET][MAX_LET]; //constraints void sort_vars(int left, int right); void comb(vector<char> current, vector<char> pool); int main(){ int i, j; char c, d1, d2; bool flag = false; for(i=0; i<MAX_LET; i++) for(j=0; j<MAX_LET; j++) consts[i][j] = false; while( (c = getchar()) != EOF ){ if( c >= 'a' && c <= 'z' ){ vars.push_back(c); }//get variables else if( c == '\n' ){ while( (d1 = getchar()) != '\n' ){ if( d1 >= 'a' && d1 <= 'z' ){ cin >> d2; consts[d2-'a'][d1-'a'] = true; } }//while get constraints if(flag == true) puts(""); sort_vars(0, vars.size()-1); //sort variables vector<char> tmp; comb(tmp, vars); //produce combinations //initialize flag = true; vars.clear(); for(i=0; i<MAX_LET; i++) for(j=0; j<MAX_LET; j++) consts[i][j] = false; }//get constraints } return 0; } void sort_vars(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; (i<=right) && (vars[i] <= vars[left]); i++); for(; (j>left) && (vars[j] > vars[left]); j--); if( i>=j ) break; swap(vars[i], vars[j]); } swap(vars[j], vars[left]); sort_vars(left, j-1); sort_vars(j+1, right); } } void comb(vector<char> current, vector<char> pool){ vector<char>::size_type i, j; if( pool.empty() ){ for(i=0; i!=current.size(); i++) cout << current[i]; cout << endl; return; } vector<char> tmp_cur, tmp_pool; vector<char>::size_type psize = pool.size(); for(i=0; i<psize; i++){ for(j=0; j<psize; j++){ if( consts[ pool[i]-'a' ][ pool[j]-'a' ] ) break; } if( j == psize ){ tmp_pool = pool; tmp_cur = current; tmp_cur.push_back(pool[i]); tmp_pool.erase(tmp_pool.begin()+i); comb(tmp_cur, tmp_pool); } }//i return; }
這題是要在所給的一連串字串中,排除特定一些關鍵字,再將排除後剩餘的所有單字連同原字串順序輸出。
寫出來相當開心!第一次嘗試使用C++的class與string, vector等STL(Standard Template Library),也使用了自訂class來做vector!string和vector乍看之下有點抽象,但實作起來還蠻方便有趣的,C++ Primer的作者在書中不斷警告使用者在C++要減少使用char*和array。
CODE
#include <iostream> #include <vector> #include <string> #include <algorithm> using namespace std; class cls_kwords{ public: string keyword; int title_no; int position; //ending position of keyword in title }; const int to_low = 'a' - 'A'; vector<string> words; //vector of words to ignore vector<string> titles; vector<cls_kwords> keywords; void sort_words(int left, int right); void sort_keywords(int left, int right); bool isignore(string line); bool isbigger(int a, int b); int main(){ string s; while( cin >> s ){ if( s[0] == ':' ) break; words.push_back(s); }//words to ignore //sort words to ignore sort_words(0, words.size()-1); //get titles int total = 0; string key; string::size_type i, len; cls_kwords tmp; while( getline(cin, s) ){ if( !s.empty() ){ len = s.size(); for(i=0; i<=len; i++){ if( i == len || s[i] == ' ' ){ if( !key.empty() ){ if( !isignore(key) ){ tmp.keyword = key; tmp.title_no = total; tmp.position = i; keywords.push_back(tmp); } key = ""; } } else if( s[i] >= 'A' && s[i] <= 'Z' ){ s[i] += to_low; key += s[i]; } else if( s[i] >= 'a' && s[i] <= 'z' ) key += s[i]; }//i titles.push_back(s); total++; } }//while get titles int ksize, st, j; //sort keywords ksize = keywords.size(); sort_keywords(0, ksize-1); //output for(int k=0; k!=ksize; k++){ len = titles[ keywords[k].title_no ].size(); st = keywords[k].position - keywords[k].keyword.size(); for(j=0; j<st; j++) cout << titles[ keywords[k].title_no ][j]; for(; j<keywords[k].position; j++) printf("%c", titles[ keywords[k].title_no ][j] - to_low); for(; j<len; j++) cout << titles[ keywords[k].title_no ][j]; cout << endl; } return 0; } void sort_words(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; (i<=right) && (words[i]<=words[left]); i++); for(; (j>left) && (words[j]>words[left]); j--); if( i >= j ) break; swap(words[i++], words[j--]); }//while swap(words[j], words[left]); sort_words(left, j-1); sort_words(j+1, right); } } bool isignore(string line){ vector<string>::size_type i, max = words.size(); for(i=0; i<max; i++){ if( line < words[i] ) break; else if( line == words[i] ) return true; } return false; } void sort_keywords(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(; (i<=right) && (!isbigger(i, left)) ; i++); for(; (j>left) && (isbigger(j, left)) ; j--); if( i >= j ) break; swap(keywords[i++], keywords[j--]); } swap(keywords[j], keywords[left]); sort_keywords(left, j-1); sort_keywords(j+1, right); } } //return true when a>b, false when a<=b bool isbigger(int a, int b){ if( a == b ) return false; if( keywords[a].keyword > keywords[b].keyword ) return true; else if( keywords[a].keyword < keywords[b].keyword ) return false; if( keywords[a].title_no > keywords[b].title_no ) return true; else if( keywords[a].title_no < keywords[b].title_no ) return false; if( keywords[a].position > keywords[b].position ) return true; else if( keywords[a].position < keywords[b].position ) return false; return false; }
這題是用文字給出二元樹,檢查是否是完整的樹,如果是完整的樹即輸出廣度優先搜尋(BFS, Bread First Search)的結果。
我用的方法是用quicksort先對字串排序(eg, L, R, LL, LR, RL, RR,…),接著檢查是否是完整的樹,最後再照字串順序輸出該node的數字。Runtime 0.008,程式碼也相當龐大,在這題來說顯然有更快更精簡的方法,也許可以考慮使用struct, C++的STL函式庫,也許會有更好的表現。
CODE
#include <iostream> #include <string> #include <algorithm> using namespace std; #define MAX_LEN 300 #define MAX_NODE 256 int total, num[MAX_NODE], len[MAX_NODE]; char line[MAX_NODE][MAX_NODE]; bool rep; void sort_tree(int left, int right); bool isbigger(int a, int b); void swapnode(int a, int b); bool valid_tree(void); int main(){ char c, snum[MAX_LEN], sline[MAX_LEN]; int p, pnum, pline; int i; rep = false; total = 0; for(i=0; i<MAX_NODE; i++) num[i] = -1; while( (c = getchar()) != EOF ){ if( c == '(' ){ p = pnum = pline = 0; } else if( c == ')' ){ if( p == 0 ){ sort_tree(0, total-1); if( valid_tree() ){ cout << num[0]; for(i=1; i<total; i++) cout << ' ' << num[i]; cout << endl; } else cout << "not complete" << endl; //initialize rep = false; total = 0; for(i=0; i<MAX_NODE; i++) num[i] = -1; }//end of tree else{ if( pnum > 0 ){ snum[pnum] = '\0'; sscanf(snum, "%d", &num[total]); for(i=0; i<pline; i++) line[total][i] = sline[i]; line[total][pline] = '\0'; len[total] = pline; }//if pnum > 0 total++; }//end of node } else if( c == ',' ){ p++; } else if( c >= '0' && c <= '9' ){ snum[pnum++] = c; p++; } else if( c == 'L' || c == 'R' ){ sline[pline++] = c; p++; } else ; }//while return 0; } void sort_tree(int left, int right){ if( left < right ){ int i = left + 1; int j = right; while(1){ for(i; (isbigger(i, left)==false) && (i<=right); i++); for(j; (isbigger(j, left)==true) && (j>left); j--); if( i >= j ) break; swapnode(i, j); i++; j--; }//while swapnode(left, j); sort_tree(left, j-1); sort_tree(j+1, right); } } //return true if a > b, return false if a <= b bool isbigger(int a, int b){ if( a == b ) return false; if( len[a] > len[b] ) return true; if( len[a] < len[b] ) return false; for(int i=0; i<len[a]; i++){ if( line[a][i] > line[b][i] ) return true; else if( line[a][i] < line[b][i] ) return false; } rep = true; return false; } void swapnode(int a, int b){ swap(num[a], num[b]); swap(len[a], len[b]); char tmps[MAX_LEN]; strcpy(tmps, line[a]); strcpy(line[a], line[b]); strcpy(line[b], tmps); } bool valid_tree(void){ if( (num[0] == -1) || (len[0] != 0) ) return false; if( rep ) return false; int i, j; bool flag; char tmps[MAX_LEN]; for(i=1; len[i]<=1 && i<total; i++) if( num[i] == -1 ) return false; for(i; i<total; i++){ if( num[i] == -1 ) return false; flag = false; for(j=0; j<(len[i]-1); j++) tmps[j] = line[i][j]; tmps[j] = '\0'; for(j=(i-1); (j>=0) && (len[j]>=(len[i]-1)); j--) if( strcmp(line[j], tmps) == 0 ){ flag = true; break; } if( !flag ) return false; }//i return true; }
把線上版的《約耳談軟體》(Joel On Software)照著實體書出版目錄至少看過了一遍,是融合技術、經驗、娛樂、還有勵志性的好看的書!書內談許多軟體專案開發的實務技巧,強調寫規格、定時程、Daily Build的重要性,也談及專案管理及軟體商業策略等等。
雖然有些內容還無法完全了解,但似乎對軟體業多了一分認識,也從〈軟體人員面試教戰守則〉中,思考怎樣是業界所需要的人。而勵志的〈邊開火邊移動〉更鼓勵讀者不要擔心每天只前進一點點,重點是每天都前進一點點。除此之外,由於作者曾經在微軟工作過,許多寫到關於微軟的管理風格、策略的部分都看得很過癮啊!