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:
```c
...
freopen("f1.in","r",stdin);
freopen("f1.out", "w",stdout);
while (scanf(...) != EOF) {
    printf(...);
}
```

Time complexity and Sorting 
----------------------------
###Time complexity

由於競賽題目多有時間限制，我們必須分析程式碼的時間複雜度，根據測資的數量判斷程式大概的執行時間，以避免超過題目的時間限制

𝑶(𝒏):
```c
for (i = 0; i < n; i++){
   ...
}
```
𝑶(𝒏^2):
```c
for (i = 0; i < n ;i++)
    for(j = 0; j < n; j++) {
        ...
    }
```
𝑶(𝟐^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)，且為不穩定排序。

![\ \ \ \ \ \    figure1  (\ \ \ 底線：已排序好的資料  \ \ \ \ 灰底底線：上一個被排序好的資料  \ \ \ \ \ 綠色斜體：被交換的資料。   )
](/selection_sort01.png)

####Bubble Sort

「氣泡排序法」( or 泡沫排序法, 冒泡排序法…)

重複地走訪過要排序的數列，一次比較相鄰兩個元素，如果他們的順序錯誤就把他們交換過來。

時間複雜度 O(n^2)，氣泡排序法為穩定排序。

1.從第一個元素開始，比較相鄰的兩個元素大小

2.若第一元素大於第二元素，則交換位置

3.每回合遞減需要比較的元素個數

![figure\ 2\ Bubble Sort](/bubble.png)

####Insertion Sort

「插入排序法」

每次都只為一個元素找到目前(已排序的數列中)的最佳位置

時間複雜度為 𝑂(𝑛2)，為穩定排序。

1.從第一個元素開始，該元素可以認為已經被排序

![](/insertionsort1.png)

2.取出下一個元素，在已經排序的元素序列中從後向前	掃描

![](/insertionsort2.png)

![](/insertionsort3.png)

3.如果該元素（已排序）大於新元素，將該元素移到下	一位置


![](/insertionsort4.png)


4.重複步驟3，直到找到已排序的元素小於或者等於新	元素的位置

![](/insertionsort5.png)

5.將新元素插入到該位置後

![](/insertionsort6.png)

6.重複步驟2~5

![](/insertionsort7.png)

![](/insertionsort8.png)

![](/insertionsort9.png)

![](/insertionsort10.png)

![](/insertionsort11.png)


![insertionsort_code](/insertionsort_code.png)

####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 之後，便對兩組資料進行「合併」動作。

![](/mergesort1.png)

![](/mergesort2.png)

![](/mergesort3.png)

![](/mergesort4.png)

![](/mergesort5.png)

![](/mergesort6.png)

![](/mergesort7.png)

![](/mergesort8.png)

![](/mergesort9.png)

![](/mergesort10.png)

![](/mergesort11.png)

![](/mergesort12.png)

![](/mergesort13.png)

![](/mergesort14.png)

![](/mergesort15.png)

![](/mergesort16.png)

![Merge Sort(divide)](/Merge_divide.png)

![Merge Sort(conquer)](/Merge_conquer.png)

####Quick Sort

1.挑選資料中的一個元素做為「基準」（以下皆以序列末端元素作為基準）

2.然後將比它小的放在前面部分，比它大的放後面部分

3.將「基準」與比它大的序列的第一個元素交換，則「基準」在序列中的位置就確定了。

4.然後對前後兩個序列分別再遞迴做Quick Sort

![Quicksort \ \ 紅色斜體: 基準\ \ \ 粗體:當前被排序好的資料](/Quicksort.png)

####STL

這個 sort 是使用 Quick Sort 加上很繁複的優化完成的。

在非必要的情況下，我們都不會自己寫而使用 STL 的sort。

![STL](/STL.png)



Stack and Queue 
---------------
###Stack

Stack 是一個有序的串列，資料的插入及刪除只發生在stack的頂端(top)

(Last-In-First-out 也就是後插入的會先被刪除)

![stack示意圖](/stack1.png)

Member function:

push():插入

pop():刪除

top()

empty()

size()

![stack](/stack.png)

###Queue

Queue 是一個有序的串列，資料的插入只發生在queue的尾端(rear)，資料的刪除只發生在queue的前端(front)

(First-In-First-out 也就是先插入的會先被刪除)

![queue示意圖](/queue1.png)

Member function:

push():插入

pop():刪除

front()

back()

empty()

size()

![queue](/queue2.png)

###Priority Queue

Priority queue 有別於一般的 queue，資料保持排序，可以隨時得到最大值。

Member function:

push():插入

pop():刪除

top()

empty()

size()

![priority queue](/priority queue2.png)