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

int tc, a, b;
scanf("%d",&tc);
while (tc--) {
    scanf("%d%d",&a,&b);
    printf("%d\n",a+b);
}

2.以特定值(通常為 0)為中止條件

Ex:

Hi, input #

/* Until zero */

int n;
while (scanf("%d",&n) == 1 && n) {
    printf("Hi, %d.\n",n);
}

3.以EOF(End of file)為中止條件

Ex:

Hi, input #

/* Until EOF */
int n;
while (scanf("%d",&n) != EOF) {
    printf("Hi, %d.\n",n);
}

若題目為指定測資終止條件，則以EOF作為終止條件

Ex:

• scanf

while (scanf() != EOF) {
    ...
}

• fgets

while (gets() != 0) {
   ...
}

• cin

while (cin >> x) {
    ...
}

1.在每個輸出後面加一個空白行

Ex: * A+B Problem

/*\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:

/* 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:

/*
 * 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);
}

freopen:

...
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++){
   ...
}

𝑶(𝒏^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);
}
/* 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()