程式設計的第一堂課
C++ 基礎語法
簡單題目（一）：
輸入一個數字 $n$，代表接下來會輸入 $n$ 個數字，請輸出那些數字的總和。 Input: 5 1 2 3 4 5 Output: 15
//practice
#include <iostream>
using namespace std;
int main()
{
int sum = 0, tmp, runt;
cin >> runt;
for (int i = 0; i < runt; i++)
{
cin >> tmp;
sum += tmp;
}
cout << sum << "\n";
return 0;
}
簡單題目（二）：
輸入一個字串，然後將其反轉輸出。 Input: ABCDE Output: EDCBA
//practice
#include <iostream>
using namespace std;
int main()
{
char str[5];
cin >> str;
int i = strlen(str);
// 計算字元數量可以用 strlen
while (i >= 0)
{
cout << str[i];
i--;
}
cout << "\n";
return 0;
}
未定義行爲（Undefined Behavior）
未定義行爲是有可能可以編譯過的，但是執行結果會與編譯器有關。
最常見的比如說：
cout << 1 / 0 << endl;
編譯器有時候會做一些優化動作，比如以下：
int func(unsigned char x)
{
int value; /* assuming 32 bit int */
cin >> value; // type 2147483647
if (value + 1 < value)
bar();
return value;
}
由於編譯器知道 if 不會成立，因此可能程式碼會被優化成：
int func(unsigned char x)
{
int value = 2147483647;
return value;
}
但事實上 value + 1 會 overflow 變成負數，此時 bar() 會被觸發。
浮點數誤差
在現在的 CPU 中，幾乎都支援雙精度浮點數運算，因此 float 和 double 的效能幾乎是相同的，但 float 精度是 $10^{-6}$，而 double 的效能是 $10^{-15}$；因此請使用 double，float bad。
string
C 語言沒有所謂的 string，我們都用 char 陣列模擬，遇到 /0 中止。
而 C++ 的 STL 有提供所謂 string，讓我們可以很方便的進行 IO、字串操作。
I/O
C++ 鼓勵使用 stream 來進行 I/O，且純 stream 效能比 stdio 高。
int a; double b; string c; string d;
cin >> a >> b >> c;
cin.getline(str);
// 注意此時 str 可能會讀到空的東西，因爲 buffer 中可能有換行，預設 getline 使用 /n 劃分
I/O 優化
stream 雖然本身比 stdio 效能高，但因爲要頻繁 flush 且要與 stdio 同步，因此我們可以選擇關閉同步；
ios::sync_with_stdio(false);
cin.tie(0);
且與其使用 endl 換行，不如使用 \n 換行，因爲前者會 flush buffer。
有興趣可以參考這篇文章，寫的很仔細。
模板（template）
模板是個非常重要的概念！
不過注意模板其實是語法糖，會在編譯器間展開，所以同一個模板函數可能會生出很多不同函數，如果用 static variable 要注意哦。
會發現 int 的 myswap 的 cnt 和 double 的完全無關，因為在編譯階段就會被展開成兩個不同函數！
有興趣可以參考這篇文章，但內容可能會有點艱澀。
巨集（macro）
巨集是編譯器提供的很強大的工具，我們可以簡單的使用：
#define REP(i, n) for(int i = 0; i < n; i ++)
REP(i, 3) {
REP(j, 3) {
cout << i << " " << j << endl;
}
}
也可以用巨集寫出偽函數：
#define max(a, b) (a > b ? a : b)
cout << (max(5, 3) + 3) << endl;
不過要注意，如果你是下面的寫法，就可能會出問題：
#define max(a, b) a > b ? a : b
cout << (max(5, 3) + 3) << endl;
因為 define 的本質是帶入，因此會變成：
cout << (5 > 3 ? 5 : 3 + 3) << endl;
他和模板類似，都是在編譯期進行展開。
有興趣可以參考這篇文章，講解 Linux 核心原始程式碼巨集，相當有趣。
如果有興趣，還有一個叫做 inline 的 C++ feature，也是將函式在呼叫他的地方展開，能節省呼叫時間；但不能做遞迴操作，這邊不細談。
編譯器優化
前面有提到，編譯器會進行所謂的優化（因此你寫組合語言寫出來的東西可能還沒有寫 C 語言快，因為 gcc 的優化做的不錯）。
在你的程式前面加上這一行就可以了：
#pragma GCC optimize("Ofast,unroll-loops")
Ofast 可以改成 O1、O2、O3，代表要進行多少優化（數字越小優化越多），越多優化程式就越偏移你的本意，這是雙面刃；但我迄今沒有出現過因為編譯器優化而導致程式執行錯誤。
有興趣可以參考這篇文章。
時間複雜度
複雜度有什麼用呢？能讓我們估算程式的執行時間。
雖然說 $O(N) = O(2N)$，但我們在寫 code 的時候還是儘量估準一點。 以現在電腦的運算量，一秒大概可以執行 $5 * 10^8$ 計算。
所以一個 $O(N^3)$ 的演算法，如果 $N = 1000$，他可能會需要一到兩秒來執行；在有優化的簡單操作下，也是有可能壓到一秒以下的，
例題：
void bubble_sort(int arr[], int len) {
int i, j;
for (i = 0; i < len - 1; i++)
for (j = 0; j < len - 1 - i; j++)
if (arr[j] > arr[j + 1])
swap(arr[j], arr[j + 1]);
}
這個叫做 bubble_sort，是很經典的排序演算法，可以參考下圖：
每一次循環最大個的都會跑到最後面，因此可以完成排序。
請分析看看他的時間複雜度吧！
可以看看這隻影片，會讓你更瞭解這個演算法，也可以驗證你的答案是否正確哦。
我們之後的所有操作，都會探討時間複雜度。
資料結構
基本上電腦程式的動態資訊都是儲存在記憶體（RAM）裡面，RAM 的全名是 Random Access Memory，其中 Random Access 就是你可以任意存取其中某一位。
而 RAM 就是你可以在 O(1) 時間內存取某一個地址的一個電腦元件。
而資料結構就是在電腦當中要用怎樣的格式儲存資料，不同的格式能帶來不同的優缺點。
可以先參考 基本資料結構： linked list、queue、stack，再參考 STL 所提供的資料結構。
