On The Road

題目原文 題目說明 實作 stack 三種功能：1. 刪除堆頂元素 2. 輸出頂端元素  3. 丟數字進堆疊。 思路 利用 STL 裡的堆疊分別使用 pop、top、push 三種 function。 #include<iostream> #include<stack> using namespace std; int main() { stack<int> s; int n; cin >> n; while(n--) { int select; cin >> select; if(select == 1) s.pop(); if(select == 2) cout << s.top() << endl; if(select == 3) { int num; cin >> num; s.push(num); } } }

題目原文 題目說明 第一行輸入幾筆資料，第二行輸入此資料共幾片(n) 雪花，接下來 n 行代表雪花編號。 輸出可裝出最多不同雪花的數目 (需連續)。 思路 假設共 5 片雪花，編號分別是 4 1 4 2 3 5，從第一個 4 開始取，接下來是 1 和 4，碰到 4 時因為與第一個 4 編號相同，所以記下此次最多取出相異雪花數目為 2；接下來從 1 開始取，依序是 4 2 3 5，記下此次最多可取出相異數目為 5 ，並且每次取出數目時都與 max 比大小，最後傳回最大值即可。 #include<iostream> using namespace std; int check(int[], int); int main() { int t, n; scanf("%d", &t); while(t--) { scanf("%d", &n); int arr[n]; for(int i = 0; i < n; i++) scanf("%d", &arr[i]); int ans; ans = check(arr, n); printf("%d\n", ans); } } int check(int arr[], int n) { int max = 0; int count = 0; int stop = -1; for(int i = 0; i < n; i++) { for(int j = stop + 1; j < i; j++) { if(arr[j] == arr[i]) { stop = j; // 利用 stop 記住 i = stop + 1; // 往下一個移動 if(count > max) max = count; count = 0; } } count++; } if(count > max) return count; else return max; }

題目原文 題目說明 輸入一段文章，輸出每一單字，並按字典序排列。 思路 一個單字一個單字去讀，若遇到像 andy's 這種詞，須將其切割為 andy 和 s 兩個單字， 讀完丟入 set (會自動依字典序排列)，再利用迭代器輸出即可。 #include<iostream> #include<cctype> #include<cstring> #include<sstream> #include<set> using namespace std; set<string> dict; int main() { string input; while(cin >> input) { for(int i = 0; i < input.length(); i++) { if(isalpha(input[i])) input[i] = tolower(input[i]); else input[i] = ' '; // 非字母轉成空白字元 (ex. andy's 變 andy s) } stringstream ss; // 拿來切割 (ex. andy s 變兩個字串) ss << input; string output; while(ss >> output) dict.insert(output); // 會自動由小到大排 } set<string>::iterator it; for(it = dict.begin(); it != dict.end(); it++) cout << *it << endl; return 0; }

題目原文 題目說明 第一行輸入兩個數字 N 和 Q，分別代表：有 N 個大理石和查找 Q 個數。 接下來的 N 行代表大理石所寫上的數，由小到大依序排列，最後求題目所問某數在哪個位置。 思路 利用 algorithm 裡的 sort 進行排序，再利用 lower_bound 查找出位置。 lower_bound ：用來找出第一個大於或等於某數的位置。 #include<cstdio> #include<algorithm> using namespace std; const int maxn = 10000; int main() { int n, q, arr[maxn], count = 0; while(scanf("%d %d", &n, &q) == 2 && n) { printf("CASE# %d:\n", ++count); for(int i = 0; i < n; i++) scanf("%d", &arr[i]); sort(arr, arr+n); while(q--) { int num; // 要搜尋的數 scanf("%d", &num); int pos = lower_bound(arr, arr+n, num) - arr; // 用 lower_bound 查找 num 的位置 if(arr[pos] == num) printf("%d found at %d\n", num, pos+1); else printf("%d not found\n", num); } } }

題目原文 題目說明 只有兩種顏色，且相鄰兩點需不同色，若可以達成，則輸出 BICOLORABLE，反之輸出 NOT BICOLORABLE。 思路 首先以 vector 建立表格來儲存與某節點相鄰的其他節點，以 queue 來儲存節點走訪的順序。 建立好連通表後，開始走訪，走訪做兩種事情：著色和檢查是否同色，可隨機從某點開始(以下程式碼以 n1 當第一個節點)，將其 push 進 queue 裡並著上顏色，塗完顏色後以 current 記住後 pop 出去， 接著開始替相鄰節點(由連通表依序取出)著色，若相鄰節點尚未著色，則 push 到 queue 裡，當作下一個要走訪的 current，並著上與當前 current 相反顏色；已著色則檢查是否與當前 current 同色，同色則可確定非 bicolorable。著完後色都沒問題即為 bicolorable。 簡言之， 1. 建連通表  2. 按連通表依序著色  3. 著色過程中檢查是否符合規定。 #include<cstdio> #include<vector> #include<queue> int main() { int node; while(scanf("%d", &node) && node) { int edge, n1, n2; int color[200] = {0}; bool check = true; std::vector<int> vec[205]; // 所在列數代表它是第幾個點 後面push進和它連接的點 std::queue<int> que; scanf("%d", &edge); for(int i = 0; i < edge; i++) { scanf("%d %d", &n1, &n2); vec[n1].push_back(n2); // 建連通表 記得兩邊互相連接 vec[n2].push_back(n1); } que.push(n1); color[n1]

說明 建構出以學生姓名和成績為節點的佇列。 思路 以鏈結串列建立佇列，概念大致和上一篇： 陣列實作串列  相同。 #include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct student { char name[20]; int score; struct student *next; }node; node *front = NULL; // 先都指向 NULL node *rear = NULL; int enqueue(char[], int); // 新增 int dequeue(); // 刪除 推第一個出來 int show(); int main(void) { int score, select; char name[20]; do { printf("請輸入 1. 新增 2. 刪除 3. 顯示 4. 結束: "); scanf("%d", &select); switch(select) { case 1: printf("請輸入姓名 成績: "); scanf("%s %d", &name, &score); enqueue(name, score); // 存進去 break; case 2: dequeue(); break; case 3: show(); break; } } while(select != 4); return 0; } int enqueue(char name[], int score) { node *newnode = (node *)malloc(sizeof(node)); newnode->score = score; strcpy(newnode->name, name); if(rear == NULL) fr

思路 以陣列來建立佇列，擁有兩個動作 — 加入和刪除，並且用 front 和 rear 分別指向佇列的前端和尾端。 一開始，front 和 rear 都預設為 -1，每加入一個元素，rear 的值 + 1；每刪除一個元素，front 的值 + 1。 以陣列建立的缺點是大小無法事先規劃。 #include<stdio.h> #include<stdlib.h> #define max 10 int queue[max] = {0}; int front = -1; int rear = -1; int main(void) { int value, select = 1; while(rear < max - 1 && select != 3) { printf("請輸入1. 存入數值 2. 取出數值 3. 結束: "); scanf("%d", &select); switch(select) { case 1: printf("請輸入數值: "); scanf("%d", &value); rear++; queue[rear] = value; break; case 2: // 取出 if(rear > front) { front++; printf("取出的值為 %d\n", queue[front]); queue[front] = 0; // 取完 } break; default: break; } } printf("輸出佇列中所有元素: "); if(rear == max - 1) printf("佇列已滿\n"); else if(front >= rear) printf("佇列已空\n"); else { while(rear &

八皇后問題 在 8 * 8 的棋盤上擺入八個皇后，兩兩之間不能在同一行、同一列或對角線上， 求出共幾種解法並印出。 思路 可利用遞迴方式解決，每次放一個新的都與前面作比較，檢驗是否合格。 #include<iostream> #include<conio.h> // getch() #include<cmath> using namespace std; #define max 8 int answer = 0; // 放外面 因為會一直累加 class QueenPuzzle { int queens[max]; public: void print(); void place(int i); // 放入 int isValid(int n); // 放入第 n 個是否合格 }; void QueenPuzzle::print() { for(int i = 0; i < max; i++) { for(int j = 0; j < max; j++) { if(j == queens[i]) cout << "Q "; else cout << "1 "; } cout << endl; // 排完一列 換行 } if(getch() == 'q') // 按 q 鍵正常退出 exit(0); } void QueenPuzzle::place(int i) { for(int j = 0; j < max; j++) { if(i == max) { answer++; cout << "第 " << answer << " 組解: " << endl; print(); return; } queens[i] = j; if(isValid(i)) // 成功 下面一位 如果不行 就回到迴圈 j++ 往右一格

題目原文 題目說明 輸入 N - M 之值，輸出可能的 N 值。 思路 設 N = 10 * a + b，輸入 input = 10 * M + b - M = 9 * M + b 。以個位數處理，最後反求 N 值。 #include<stdio.h> int main(void) { long long input; int b; while(scanf("%lld",&input) && input) { int first = 0; for(b = 9; b >= 0; b--) // 逆向思考, 以個位數 b 處理 { if((input - b) % 9 == 0) // 若 input - b 再除以 9 為整數 (因為 M 為整數) { if(first) putchar(' '); first = 1; printf("%lld",(input - b) / 9 * 10 + b); } } printf("\n"); } }

1.       隨機變數 (random variable) 是將一個實數與樣本空間中的每個元素做連結的變數 , 可分為離散 discrete ( 可數 count) 和連續 continuous ( 量測 measured) 2.       對於隨機變數  X, 以 f(x) 表示其所有數值 x 的機率 , 序對 (x, f(x)) 的集合稱為隨機變數  X  的機率 質量函數  PMF (probability mass function) 3.       累積分布函數  CDF (cumulative distribution function) F(x) = P(X  ≦   x) 計算隨機變數 X 的數值小於或等於某實數  x  的機率        是單調不遞減函數 4.       考慮連續 : 探討的是隨機變數的一段區間而不是一個點的數值 , 且區間的末端點是否包含進來並不重要 , 此時 f(x) 稱為機率密度函數  PDF (probability density function) 5.       連續的  CDF F(x) = P(X ≦ x), 所以 P(a<X<b) = F(b) - F(a) 6.       連續的  PDF f(x) 和  CDF F(x) 互為微積分關係 , PDF  積分變  CDF ( 從    -∞  積到  x ) , CDF  微分變  PDF

1.     互斥   mutually exclusive       P(A∪B ) = P(A) + P(B)     ∵  P(A ∩ B) = Ø 2.     獨立     independence        P(A ∩ B ) = P(A)  ‧  P(B)     (if and ony if) 已知一些 information (B) ，但對整個條件機率沒有任何幫助或影響。 P(A | B) 還是等於 P(A) ， P(B | A) 也還是等於 P(B)

1. Axioms of Probability     (1) For any event, P[A] ≧ 0     (2) P[S] =1     S : sample space，代表所有可能都發生     → 由(1)、(2)可知，機率是介於 0 到 1 之間的數     (3) 互斥事件聯集的機率= 個別事件機率的加總 2. Equally likely outcomes : no one outcome is any more likely than any other     亦即每個可能性一樣 ( 沒有任何偏好 )，所以假設有 n 個 outcome，則每個 outcome 的機率都是 1/n。 3. Conditional probability 條件機率 : 滿足某條件下，某事情的機率。     P[A]=prior probability 先驗條件，P[A | B]=Conditional probability 條件機率，讀作 the probability of A given B。     條件機率的物理意義 : P[A] reflects our knowledge of the occurrence of A prior to performing an experiment.     而條件機率因為多給了已知條件，所以正確率得以大幅提升。 參考資料來源 — Probability and Stochastic Processes: A Friendly Introduction for Electrical and Computer Engineers by Roy D. Yates and David J. Goodman

1. Probability is based on a repeatable experiment ，其中 experiment = procedure + observation 。例如為了知道買 A 款和 B 款手機的機率，procedure 就是到店裡調查，observation 為觀察下一個客人是買哪款手機。注意即使 procedure 一樣，若 observation 不同 ( 即有興趣的點不同 )，則實驗就不相同。此時所得的 model 屬於 equal likely，因為客人沒有特別偏好， A 和 B 的機率差不多。另外， outcome 為一次實驗所得的特定結果， event 為某一組 outcome 的集合。 2.  (1) Mutually exclusive sets ( 互斥 ) : 代表集合間的交集為空集合。( 重要 , 很多概念由此衍生 )       p.s. 若一事件的發生並不影響另一事件，則稱為獨立事件。      (2) Collectively exhausive sets ( 周延 ) : 代表進行某次實驗所得的結果一定在這些集合裡面。      (3) Partition : mutually exclusive 和 collectively exhausive 同時滿足。 3. Sample space : 把所有 outcome 集合起來，須滿足 3 個條件 —     (1) mutually exclusive     (2) collectively exhausive   (3) finest - grain     finest - grain : all possible distinguishable outcomes are identified separately ( 代表須為最小單位 ) 4. outcome、event、sample space 的關係 :     (1) outcome — element     (2) event — set     (3) sample space — universal set 參考資料來源 — Probability and Stochastic Processes: A Friendly Introduction f

1.  在圖   G  中，如果去掉一點   v ，剩下的圖   G  產 生比 圖   G  更多   connected component ，那 麼 這個點就 是   cut vertex 。但是在   complete graph 裡，找不到這 麼 一個 點   v  可以生成更多的   connected component ，所以   complete graph  並沒有   cut vertex 。 ( e.x. K4  去掉任一點只會變成  K3 ， 它 還是只有一個連通 圖   ) 2. Vertex cut  則是由點組成的一個集合，去掉這些點，剩下的圖   G  就會變成   disconnected 。 3. Vertex connectivity ，即   k(G) ，則是指最少要去掉幾個點，也就是   vertex cut  的最小數目，剩下的圖   G  會變成   disconnetced ，或是變成只剩單獨一點 。 (  因 為   vertex cut  可能有包含很多點，但其實用不著那 麼 多個點就能讓剩下的 圖   G  變成   disconnected ，所以另外定義   k(G)  ) e.x.  (1) k(K4)=3 — 因 為   complete graph  沒有   vertex cut ，所以   k(Kn) = n-1 ，讓 它 變成單獨一 點         (2) k(C4)=2 — 拿掉對角線兩個點，可另外推得當 n ≧ 3 ， k(Cn)=2         (3) k(W4)=3 — 拿掉中間和對角線兩個點         (4) k(K2,3)=2 — 拿掉其中一邊的所有點，讓另一邊的點彼此連不起來，可另外推得   k(Km,n)=min(m,n)         (5) k(Q3)=3 — 拿掉底部正方形對角線兩點後，再拿掉上層另外一邊的對角線其中一點，可另外推得  k(Qn)=n