On The Road

題目原文 題目說明 第一行輸入兩個數字 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