版本 28eb087b4bf3f06d341c2f0452436aaeaf8fc26e
Changes from 28eb087b4bf3f06d341c2f0452436aaeaf8fc26e to e6913f5ac0f9ff2d4606f4acd299cf61dff77549
Review 1
========
I/O
--------
標準的輸入輸出有下列幾種指令
輸入:
scanf, gets, getchar, cin......
輸出:
printf, puts, putchar, cout....
但在比賽時由於需考慮效能所以多使用 scanf, printf 取代cin , cout
(因為cin, cout會回去呼叫scanf, printf)
比賽時常見的題型:
1.給測資的數量
Ex:
A+B problem
```c
int tc, a, b;
scanf("%d",&tc);
while (tc--) {
scanf("%d%d",&a,&b);
printf("%d\n",a+b);
}
```
2.以特定值(通常為 0)為中止條件
Ex:
Hi, input #
```c
/* Until zero */
int n;
while (scanf("%d",&n) == 1 && n) {
printf("Hi, %d.\n",n);
}
```
3.以EOF(End of file)為中止條件
Ex:
Hi, input #
```c
/* Until EOF */
int n;
while (scanf("%d",&n) != EOF) {
printf("Hi, %d.\n",n);
}
```
若題目為指定測資終止條件，則以EOF作為終止條件
Ex:
* scanf
```c
while (scanf() != EOF) {
...
}
* fgets
```c
while (gets() != 0) {
...
}
```
* cin
```c
while (cin >> x) {
...
}
```
1.在每個輸出後面加一個空白行
Ex:
* A+B Problem
```c
/*\n\n */
int a,b,cs=1;
while (scanf("%d%d", &a, &b) != EOF) {
printf("Case %d: %d\n\n", cs++, a + b);
}
```
2.每個輸出被空行隔開(最後一個輸出後面不會有空行)
Ex:
```c
/* Separated */
int a,b,cs=1;
while (scanf("%d%d", &a, &b) != EOF) {
if (cs > 1) putchar("\n");
printf("Case%d: %d\n",cs++,a+b);
}
```
string token:
```c
/*
* char strtok(char *str,const char *delimiters);
* str: 欲切割字串
* delimiters: 分隔字符字串
* return value: 指向當前切割字串之指標，若切割完畢則回傳NULL
*/
#include <cstring>
...
char str = "Welcome to NCKU CSIE. 1*2(3456)78\9";
for (char *token = strtok( str," \"().*"); token != NULL; token = strtok(NULL," \"().")) {
puts(token);
}
```
+--------+-------+-------+
| Output |
+========+=======+=======+
|Welcome | to | NCKU |
+--------+-------+-------+
| CSIE | 1 | 2 |
+--------+-------+-------+
| 3456 | 78 | 9 |
+--------+-------+-------+
freopen:
/*freopen*/
...
freopen("f1.in","r",stdin);
freopen("f1.out", "w",stdout);
while(scanf(...)!=EOF){
printf(...);
}
...
```c
...
freopen("f1.in","r",stdin);
freopen("f1.out", "w",stdout);
while (scanf(...) != EOF) {
printf(...);
}
```
Time complexity and Sorting
----------------------------
###Time complexity
由於競賽題目多有時間限制，我們必須分析程式碼的時間複雜度，根據測資的數量判斷程式大概的執行時間，以避免超過題目的時間限制
𝑶(𝒏):
for(i=0; i<n; i++){
...
}
```c
for (i = 0; i < n; i++){
...
}
```
𝑶(𝒏^2):
for(i=0; i<n ;i++)
for(j=0; j<n; j++){
...
}
𝑶(𝟐^M):
int two(int n){
if(n < 2) return 1 << n;
return two(n - 1)+ two(n - 1);
```c
for (i = 0; i < n ;i++)
for(j = 0; j < n; j++) {
...
}
/* maximum n=M */
```
𝑶(𝟐^M):
```c
int two(int n){
if (n < 2) return (1 << n);
return two(n - 1) + two(n - 1);
}
/* maximum n=M */
```
**𝑂(1,000,000) 近似於 1 sec**
###Sorting
「排序演算法」
顧名思義就是將一串資料，依照特定的規則排序的演算法。
####Selection sort(選擇排序法)
為日常生活中常用到的方法，不斷地找到最小值，再做移動，非常直觀。
時間複雜度為 𝑂(𝑛^2)，且為不穩定排序。
####Bubble Sort
「氣泡排序法」( or 泡沫排序法, 冒泡排序法…)
重複地走訪過要排序的數列，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們交換過來。
時間複雜度 O(n^2)，氣泡排序法為穩定排序。
1.從第一個元素開始，比較相鄰的兩個元素大小
2.若第一元素大於第二元素，則交換位置
3.每回合遞減需要比較的元素個數
####Insertion Sort
「插入排序法」
每次都只為一個元素找到目前(已排序的數列中)的最佳位置
時間複雜度為 𝑂(𝑛2)，為穩定排序。
1.從第一個元素開始，該元素可以認為已經被排序
2.取出下一個元素，在已經排序的元素序列中從後向前 掃描
3.如果該元素（已排序）大於新元素，將該元素移到下 一位置
4.重複步驟3，直到找到已排序的元素小於或者等於新 元素的位置
5.將新元素插入到該位置後
6.重複步驟2~5
####Merge Sort
「合併排序法」
利用分治法（Divide and Conquer）將要排序的資料均分成兩組，分別對兩邊做排序，然後再將兩邊「已排序的資料」再做合併，即完成排序。
時間複雜度 𝑂(𝑛 lg𝑛 )，還需要額外的記憶體做合併，空間複雜度𝑂(𝑛)，為穩定排序。
1.先將a 分割成兩半a[0]~a[n/2]和a[n/2+1]~a[n-1]，然後分別對它們做Merge Sort，如此遞迴下去。
2.如果遞迴到陣列元素只有一個的時候，則要return，不必再分割。
3.兩邊分別都做完Merge Sort 之後，便對兩組資料進行「合併」動作。
####Quick Sort
1.挑選資料中的一個元素做為「基準」（以下皆以序列末端元素作為基準）
2.然後將比它小的放在前面部分，比它大的放後面部分
3.將「基準」與比它大的序列的第一個元素交換，則「基準」在序列中的位置就確定了。
4.然後對前後兩個序列分別再遞迴做Quick Sort
####STL
這個 sort 是使用 Quick Sort 加上很繁複的優化完成的。
在非必要的情況下，我們都不會自己寫而使用 STL 的sort。
Stack and Queue
---------------
###Stack
Stack 是一個有序的串列，資料的插入及刪除只發生在stack的頂端(top)
(Last-In-First-out 也就是後插入的會先被刪除)
Member function:
push():插入
pop():刪除
top()
empty()
size()
###Queue
Queue 是一個有序的串列，資料的插入只發生在queue的尾端(rear)，資料的刪除只發生在queue的前端(front)
(First-In-First-out 也就是先插入的會先被刪除)
Member function:
push():插入
pop():刪除
front()
back()
empty()
size()
###Priority Queue
Priority queue 有別於一般的 queue，資料保持排序，可以隨時得到最大值。
Member function:
push():插入
pop():刪除
top()
empty()
size()
