計算機程式設計 a.k.a. 陰影製造器
===
工欲善其事，必先利其器
---
### 編輯器 (Editor)：
[Sublime Text 3](https://www.sublimetext.com/3)
[Visual Studio Code](https://code.visualstudio.com/)
Emacs ~~P老師用der~~
Vim **信仰**
* 可以下載更多插件讓你的編輯器更好用噢~
### 編譯器 (Compiler):
[MinGW](http://www.mingw.org/)
* 記得要設定環境變數 C:\MinGW\bin
* 可以用 ```gcc -v``` 指令來確認是否安裝成功！
[安裝教學傳送門](https://me1237guy.pixnet.net/blog/post/60709168-%E5%AE%89%E8%A3%9Dmingw---minimalist-gnu-for-windows)
---
### 集成開發環境 (IDE):
[Visual Studio](https://visualstudio.microsoft.com/vs/)
[Dev C++](https://sourceforge.net/projects/orwelldevcpp/)
---
### Linux
* 要用的東西都自帶惹~
* 可以用 Windows Subsystem For Linux
[安裝教學傳送門](https://blog.birkhoff.me/bash_on_windows_installation/)
第一支程式
---
```clike=
#include <stdio.h>
int main() {
printf("Hello world!\n");
return 0;
}
```
### 編譯 (Compile)：
gcc hello.c
gcc hello.c -o hello.exe
### 執行 (Execute):
#### Windows:
a
a.exe
#### Linux & Mac:
./a.out
### 執行結果 (Output):
```
Hello world!
```
基本程式架構
---
把第一支程式寫出來了，那每一行是什麼意思？
### 1. 標頭檔(Header) a.k.a. 武器庫
```clike
#include <stdio.h>
#include <math.h>
#include <string.h> // 第11課
```
有很多前人已經寫好的功能都放在庫裡面可以拿來調用，不用重複造輪子。
```<stdio.h>```是標準輸入輸出程式庫(Standard I/O Library)，```printf```是那其中的函式(Function)之一，功能是把變數印在熒幕上。 ```\n```的意思是換行(可以試一試有```\n```和沒有的區別)。
### 2. 程式骨架
```
int main() {
...
}
```
* 課本寫的是**錯的**。
* ```return 0;```代表程式正常退出。
* 第8課函式會更詳細介紹這一部分。
### 3. 注釋
單行:
```clike
// this is a comment
```
區塊:
```clike
/* this is a comment
this is another comment
this is still a comment
*/
```
寫程式要寫注釋
寫程式要寫注釋
寫程式要寫注釋
因為很重要，所以說三次。
### 4. 退出程式
```return 0;``` 代表程式正常執行並退出。
---
### 現在把變數也加進來：
JudgeGirl 3. Print Two Numbers：
- 輸入兩個整數$a$和$b$，在第一行輸出$b$，在第二行輸出$a$。
```clike=
#include <stdio.h>
int main() {
int a, b;
scanf("%d%d", &a, &b);
printf("%d\n%d\n", b, a);
return 0;
}
```
### 1. 宣告變數
```clike
int a; // 整數
float b; // 第7課 浮點數
char c; // 第10課 字元
```
* int 的範圍是$-2^{31}$ ~ $(2^{31}-1)$
* 取有意義的變數名很重要喔！比如這個變數要記錄的是總和，那就應該取名```sum```而不是隨意的取名```a```
### 2. 語法
```clike
scanf("%d", &a);
printf("%d\n", a);
```
```scanf```也是```stdio.h```裡面的一個函式，功能是把變數從鍵盤的輸入讀進來。
注意兩者的區別。
* 雙引號: 字串的開始與結束
* %: ```printf```要處理的參數
* , : 隔開眾多參數
* &: 地址（記憶體位置），在第9課指標會詳細介紹
習題 1
---
把這個圖案用printf印出來.
* 先埋個伏筆，學了迴圈(Loop)後有更好的做法。
運算
---
### 此等於非彼等於
```A = B```
**是** 把```B```的值指定給```A```。
**不是** 數學裡等號的意義。
* B 可以是變數也可以是一個常數，比如```A = 9487```。
* 指定過後，A原本的值就消失了！如果還有需要用到A原本的值，可以另設一個變數來存A原本的值。
小小練習: 寫一個程式，輸入兩個整數，交換他們的值，再輸出更新後的值。
```A == B```
檢查```A```和```B```的值是否相等。
* 通常搭配第4課```if```使用。
### 加減乘除、求餘
```clike
k = i + j
k = i - j
k = i * j
k = i / j
k = i % j // 求餘
k = -i
```
* 還記得```int```的範圍是$-2^{31}$ ~ $2^{31}-1$嗎? Overflow的問題就來嘍。
當```i = 2147483647, j = 1```, ```k = i + j```就 會overflow。 ```k```不會是```2147483648```，而是 ```-2147483647```。負數那一邊也有同樣的問題。
乘法也會有overflow喔！當```i = 9487, j = 226361```, ```k = i * j```會是```-2147480489```
* Overflow 是常見的bug, 需要小心避免。（基本上，計程不太會卡overflow，可是有時候還是會不小心踩雷。DSA和ADA倒是很喜歡卡overflow）
* 直觀的解決方法就是用範圍更大的資料形態如```long long```$(-2^{63}$~$2^{63}-1)$
* 如果```long long```還是不能滿足你的需求，可以考慮用字串（第11課）來表示數字
* 除法要注意的是因為都在整數內運算，小數會被無條件捨去。
```i = 3, j = 2```, ```k = i / j```會是```1```。
* 還有一種bug就是不小心讓變數除以0或者對0求餘，SublimeLinter不一定每次都能抓出這種bug。
### 調整變數值
| 意義 | 原來的表示法 | 簡潔的表示法 |
| - | - | - |
| i 加上 j | i = i + j | i += j |
| i 減去 j | i = i - j | i -= j |
| i 乘以 j | i = i * j | i \*= j |
| i 除以 j | i = i / j | i /= j |
| i 對 j 求餘數 | i = i % j | i %= j |
| i 加 1 | i = i + 1 | i++ |
| i 減 1 | i = i - 1 | i-\- |
補充：會在其他地方看到```++i, --i``` 這種寫法，有其不一樣的意義。
簡單來說```i++```是先指定才加，```++i```是先加才指定。看個例子就明白了。
```clike
i = 1;
j = i++;
```
i是2，j是1。
```clike
i = 1;
j = ++i;
```
i是2，j是2。
* 筆者認為```++i```的寫法稍微好一些。
### 比較運算
```
i == j // 等於
i != j // 不等於
i > j // 大於
i >= j // 大於等於
i < j // 小於
i <= j // 小於等於
```
### 邏輯運算
```
i && j // i 且 j
i || j // i 或 j
!i // 非i
```
* 在C語言中，0為偽，非0即為真。 （也就是說不一定要是1才能代表真）
### 運算順序
見下表，越上面的越先算。
| 意義 | C語言表示法 |
| - | - |
| 加1、減1 | ```++``` ```--``` |
| 求負數 | ```-``` |
| 非 | ```!``` |
| 乘、除、求餘數 | ```*``` ```/``` ```%``` |
| 加、減 | ```+``` ```-``` |
| 比較運算 | ```==``` ```!=``` ```>``` ```>=``` ```<``` ```<=``` |
* 和數學一樣，要是擔心運算順序出錯，就多加幾個括弧吧！
### 程式碼風格 (Coding Style)
在等號及二元運算子兩旁加空格能提升程式碼的可讀性喔！可以參考[Google的風格指南](https://tw-google-styleguide.readthedocs.io/en/latest/google-cpp-styleguide/contents.html)。
習題 2
---
[Judge Girl 50114. Simple Polygon](https://judgegirl.csie.org/problem/0/50114)
[Judge Girl 50115. Depth of Water](https://judgegirl.csie.org/problem/0/50115)
[Judge Girl 50078. Parallelogram](https://judgegirl.csie.org/problem/0/50078)
[Judge Girl 50079. Apple Pile](https://judgegirl.csie.org/problem/0/50079)
判斷
---
### if判斷
```clike
if (condition)
statement;
```
若condition被滿足就執行statement.
* 提醒：C語言中非0即為真。
```clike
if (condition) {
statement 1;
statement 2;
}
```
用大括號將敘述們包起來就能直接執行一組敘述。
* 注意！一個常見的bug
```clike
int score;
scanf("%d", &score);
int grade_A = 0;
if (score >= 85 && score <= 100)
printf("好棒喔\n");
grade_A = 1;
printf("%d\n", grade_A);
```
```clike
if (condition) {
statement 1
}
else {
statement 2
}
```
若condition不被滿足就執行statement 2。
```clike
if (condition 1) {
statement 1
}
else if (condition 2) {
statement 2
}
```
若condition 1不被滿足就檢查是否滿足condition 2。
小練習： 給定兩個整數，印出較大的數。
### 看得出兩者的區別嗎?
```clike
if (condition 1) {
}
else if (condition 2) {
}
else if (condition 3) {
}
...
else {
}
```
```clike
if (condition 1) {
}
if (condition 2) {
}
if (condition 3) {
}
...
else {
}
```
如果condition123皆為真，第一種寫法只會執行第一個if，並略過第二三個if而第二種寫法會把三個if由上至下都執行一次。兩種寫法都是對的，要根據題目具體需求靈活使用。
---
判斷值式
```clike
(condition)? expression 1: expression 2
```
若condition為真，執行expression 1；若condition為偽，則執行expression 2
### switch 判斷
```clike
switch (flag) {
case 1:
statement 1;
break;
case 2:
statement 2;
break;
...
default:
default_statement;
}
```
根據flag的值來決定要執行的敘述。等價的if判斷寫法如下。
```clike
if (flag == 1) {
statement 1
}
else if (flag == 2) {
statement 2
}
...
else {
default_statement
}
```
看到這裡馬上就延伸出兩個問題。
1. 既然都有if判斷了為什麼還需要switch判斷?
2. ```break```到底是什麼東西？可不可以加以利用?
Example: [Judge Girl 232. What day is Today?](https://judgegirl.csie.org/problem/0/232)
---
多個條件對應同一個敘述的寫法。
```clike
switch (month) {
case 1: case 3: case 5: case 7: case 8:
case 10: case 12:
days = 31;
break;
case 4: case 6: case 9: case 11:
days = 30;
break;
default:
...
}
```
迴圈
---
### while 迴圈
只要condition為真，statement就會一直執行下去，直到condition變為偽。
```clike
while (condition) {
statement 1;
statement 2;
...
}
```
無限迴圈
```clike
while (1) {
printf("Hello world!\n");
}
```
* 當Judge告訴你<span style="color: blue"> TLE </span>的時候可以檢查一下自己寫的迴圈是否有可能在一些情況下其實是一個無限迴圈。
小練習：給定兩個整數，印出他們的最大公因數。
提示：
$$gcd(i,j)=
\begin{cases}
j & i \text{ mod }j=0 \\
gcd(j, i \text{ mod }j) &\text{otherwise}
\end{cases}
$$
### for迴圈
```
for (initialization; condition; adjustment) {
statement 1;
statement 2;
...
}
```
通常長這個樣子啦~
```clike
for (int i = 0; i < k; i++) {
...
}
```
等價的while迴圈
```clike
i = 0;
while (i < k) {
...
i++;
}
```
小練習： 給定一個整數$k$，計算$1+2+...+k$。
### break, continue
```clike
for (initialization; condition; adjustment) {
statement 1;
if (condition 2)
break;
if (condition 3)
continue;
statement 2;
}
```
想直接跳出迴圈用```break```。
想略過這一次循環剩下來的部分用```continue```。
練習： 給定一個奇數$k$，計算$1+3+..+k$。
### 多重迴圈
```clike
for (int i = 0; i < 100; i++) {
statement 1;
for (int j = 0; j < 200; j++) {
statement 2;
}
statement 3;
}
```
* 注意在內層迴圈裡用```break```只會跳出那一個迴圈，而不會跳出整個迴圈。
statement 123各自被執行了幾次？執行的順序為？
習題 3
---
[Judge Girl 50116. Play with digits](https://judgegirl.csie.org/problem/0/50116)
[Judge Girl 50117. Divide a number](https://judgegirl.csie.org/problem/0/50117)
[Judge Girl 50080. Scan The Blocks](https://judgegirl.csie.org/problem/0/50080)
[Judge Girl 50081. Rebot Simulation](https://judgegirl.csie.org/problem/0/50081) (邦鋒經典題型)
[Codeforces: Theatre Square](http://codeforces.com/contest/1/problem/A)
陣列
---
### 屬性
首先，我們為什麼需要陣列？
有時候我們會想一次使用大量相同性質的變數，這時候用陣列的語法就會很輕鬆。比如我現在想記錄一個班裡每個人的數學期末考分數，可以寫成
```clike
int score1, score2, score3, ... , score50;
```
```clike
int score[50];
```
陣列就是一串**佔用連續記憶體的變數集合**。我們可以只利用一個名稱(陣列名稱)來表示這些變數，以省去大量變數命名的麻煩。
在存取時，我們只需要透過指定索引(index)值的方式，就可以取得陣列中的某個元素。
* **連續**很重要。
* 大部分程式語言包括C，index都是從0開始的！
現在假設```score```這個陣列有50個元素，每個元素都是一個```int```。
```clike
print("%d\n", score[0]);
print("%d\n", score[50]);
print("%d\n", score[-1]);
```
各別執行這三行code會發生什麼事?
心得：當Judge告訴你<span style="color: cyan"> RE </span>的時候，要記得檢查陣列的index有沒有超出範圍$(0$~$n-1)$
像是邦鋒很喜歡考的地圖題就需要你小心檢查index是否有超出範圍。
### 一維陣列
要使用陣列當然需要先宣告一個陣列。
```clike
int score[5];
int score[5] = {0}; // 把全部元素都初始化為0
int score[5] = {100}; // 這個會出事
int score[5] = {1, 2, 3, 4, 5}; //把第一個元素設為1, ...
```
* ```int score[5]= {100}```只會把第一個元素設為100，而其他都被設成0，這點需要注意。
用陣列的一個好處就是我們可以用一個for迴圈輕鬆地對陣列裡的每一個元素做處理。
```clike
int score[50];
for (int i = 0; i < 50; i++) {
score[i] = 100;
}
```
小練習：給定一個整數$n$，計算斐波那契數列的第$1$~$n$項。
### 排序演算法
Computer Science領域一個很重要且基礎的問題是，給定一個陣列，要如何將這個陣列照順序排好。
排序前: 3 1 4 1 5 9
排序後: 1 1 3 4 5 9
這件事情已經有很多演算法如Quicksort, Merge Sort等能很快速地解決這個問題。課本教的Bubble Sort就是其中一種排序演算法。
https://www.youtube.com/watch?v=ZZuD6iUe3Pc
不難看出用Bubble Sort做排序其實是很慢的，不過Bubble Sort簡單易懂短短幾行就能寫好，適合初學者學習。
### 泡沫排序法 Bubble Sort
```clike
for (int i = m - 1; i >= 0; i--) {
for (int j = 0; j < i; j++) {
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1]
a[j + 1] = temp;
}
}
}
```
* 課本把誤把```j < i```寫成```j <= i ```。
### 多維陣列
二維陣列簡單來說就是一個其元素為陣列的陣列，三維以上的陣列也只是同樣概念的推廣。比如我現在想記錄30個班級裡每一位同學的數學期末考分數
```clike
int score[30][50] = {0};
int score[30][50] = {{95, 100}, {1, 1, 2, 3, 5, 8}}
```
* 課本寫的是 ```int score[30][50] = {{0}}```，不過其實不需要這麼寫。
二維陣列自然就可以用一個雙層for迴圈來對陣列裡的元素來做處理。
```clike
for (int i = 0; i < 30; i++) {
for (int j = 0; j < 50; j++) {
score[i][j] = 100;
}
}
```
小練習：開一個$5\times 20$的陣列，將元素設為$1$~$100$後把每個元素依以下形式印出來。
```
1 2 3 4 5 6 7 8 9 10 ... 19 20
...
80 81 82 83 84 85 86 87 88 89 90 ... 99 100
```
* 注意：多或少一個空格都會<span style="color: red">WA</span>。
這時候判斷值式就很好用。
```clike
for (int i = 0; i < 5; i++) {
for (int j = 0; j < 20; j++) {
printf("%d%c", a[i][j], j == 19? '\n' : ' ');
}
}
```
可以直接```printf```陣列嗎?
```clike
printf("%d", a);
```
這個倒是合法
```clike
printf("%p", a);
等價於
printf("%p", &a)
```
* %p印的是變數的記憶體位置而非變數的值。C語言中陣列的值就等於他的記憶體位置。
[Judge Girl 16. Even and Odd](https://judgegirl.csie.org/problem/0/16) 這題也是在抓輸出多餘空格的錯誤。
習題 4
---
前兩年的計程課迴圈都考了兩個星期，不過既然已經學了陣列那還是做一點陣列的練習吧 XD
[Judge Girl 50119. Paper, Scissors, Stone](https://judgegirl.csie.org/problem/0/50119) 這題有點意思，事實上這就是Pseudo random number generator的原理。
[Judge Girl 50120. Consecutive 1's](https://judgegirl.csie.org/problem/0/50120)
[Judge Girl 50121. Push Stones](https://judgegirl.csie.org/problem/0/50121)
[Judge Girl 50085. Tank Simulation](https://judgegirl.csie.org/problem/0/50085)
陣列 (2)
---
### 全域變數、區域變數
我們可以開任意大小比如$1000000\times 1000000$的陣列嗎？
一個```int```佔4 bytes，$1000000\times 1000000$個``int``就佔 4 TB。
先檢查每一個subtask的記憶體限制，再決定要開多大的陣列。否則，
**MLE**。
---
那麼，能開$10000\times1000$的陣列嗎?
$4\times10000\times1000=40MB < 64 MB$
```clike=
#include <stdio.h>
int main() {
int a[10000][1000]; // 區域變數
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 1000; j++) {
a[i][j] = 1;
}
}
printf("ok\n");
return 0;
}
```
執行結果：
```
Segmentation fault (core dumped)
```
也就是<span style="color: cyan">Runtime Error</span>。
區域變數(local variables)被存在堆疊(stack)，容量一般被限制為$4\,MB$（會根據環境變動，但一般都只有幾$MB$）。
一台電腦好幾$GB$的記憶體難道我們只能用那區區$4\,MB$ ?!
```clike
#include <stdio.h>
int a[10000][1000]; //全域變數
int main() {
for (int i = 0; i < 10000; i++) {
for (int j = 0; j < 1000; j++) {
a[i][j] = 1;
}
}
printf("ok\n");
return 0;
}
```
執行結果：
```
ok
```
全域變數(global variables)被存在堆積(heap)，並沒有$4 MB$的限制。
全域變數好棒棒，那我們都用全域變數就好了啊?
**不行。**
1. 任何函式都能修改全域變數，所以一旦全域變數的值被亂改，我們無法鎖定到底是哪一部分的程式碼出了問題。（到第8章函式會再詳細說明）
2. 全域變數容易和區域變數起名稱衝突。
結論：全域變數應盡量避免使用。
嗯... 那我們要怎麼存一個$40 MB$的變數集合？
1. 動態配置記憶體！（第17章）
2. 目前暫時使用全域變數吧。
Linux & Command Line
---
204有兩種作業系統可供選擇 —— Windows 10和Ubuntu.
Ubuntu是Linux的其中一個發行版（也就是以Linux為核心的衍生作業系統）
那為什麼要會用Linux?
1. 現在絕大部分的伺服器包括系上的工作站(workstation)用的都是Linux。
2. 修SP和NASA會用到。
3. 強大的命令行功能。
~~4. 看起來比較厲害 科科~~
Windows就已經提供了方便、好用的Windows Subsystem for Linux (WSL)。
[安裝教學傳送門](https://blog.birkhoff.me/bash_on_windows_installation/)
### 檔案配置
不同於Windows將系統分成若干的磁碟區，Linux以樹狀方式儲存檔案與設備。
/ root directory 根目錄，所有目錄的起源
\~ home directory 家目錄，登入系統時進入的目錄
. working directory 當前目錄
.. parent directory （上一層目錄）
絕對路徑 開頭是/的路徑
相對路徑 開頭是./但./經常被省略。
### 常用的指令與技巧
- ssh (**S**ecure **S**hell Protocol)，一種遠端連線程式。
```
ssh b08902000@linux1.csie.org
```
之後再輸入自己的密碼就能連到系上的工作站了。
需要跑很久的程式交給工作站就對了!
用WSL的話，Windows裡的資料都會在/mnt裡面。
* tab/上下
按tab可以自動補全指令、目錄或檔案名稱，如果遇到多個可能的就會停在分叉點，連按兩次可以列出所有可能性
按上下鍵可以重複使用已輸入過的指令。
* ctrl-c / ctrl-d
按ctrl-c 可以終止目前的程式，如果不小心寫到TLE或RE的時候很好用。
按ctrl-d代表EOF，表示文件結束。
* clear / ctrl-l
清空目前畫面
* exit / logout
離開Linux系統的指令。
* man
**man**ual，可以查詢各種內建指令的功能與用法。
比如計程會用到的
```
man ascii
man qsort
man printf
```
* ls
**l**i**s**t，列出本目錄或指定目錄底下的檔案。
-a 列出包括隱藏檔案（開頭為一個點）的所有檔案。
-l 用清單格式列出，可以看到檔案的目錄權限等。
* cd
**c**hange **d**irectory，前往指定的目錄。
```
cd ..
cd /mnt/c/Code
```
* mkdir
**m**a**k**e **dir**ectory，建立新的目錄
* touch
就是戳一個檔案，不存在的話就建立他。可以用來改變時間戳。
* rm
**r**e**m**ove,移除檔案。
-r 遞迴地(recursively)移除某個目錄以及其底下所有檔案目錄。
-f 強制(forcefully)移除，系統不會一一詢問是否移除。
* 慎用 rm -rf / （很可怕
* gcc
**G**NU **C**ompiler **C**ollection
-o 自訂執行檔名。不加參數的情況，會產生預設檔名a.out
-g 讓產生的執行檔可以用GDB Debug
-Ddef 可以定義程式裡的def
-O[n] 可以做不同等級的優化 n=0~3，不是數字越大越好
-Wall 顯示所有警告訊息
-std=c99
想要執行可執行的檔案在前面打./就可以了。
* diff
**diff**erence，比較兩個檔案不同的地方
```
diff sample_output my_output
```
如果完全一樣就不輸出任何內容。
* 今天兩個一樣的檔案作diff後發現不一樣是因為windows和linux的換行符號不一樣。windows的換行符號是\r\n而linux的是\n。雖然只是個小問題，不過下個星期還是花一點點時間來說清楚這個部分吧~
* time 替某個程式計時。會有三種時間(real/user/sys)評估程式效率是看user time, real time可能會因為工作站忙碌而被拉長
```
time ./a.out
```
* redirect
重導向符號一般有3個 >, >>, <。
\> 把指令或程式的結果寫入一個新檔案，如果檔案名稱已存在就覆蓋。
```
./a.out > my_output
```
\>> 將結果接續在檔案的尾端（如果檔案不存在就建立）
```
./a.out >> my_output
```
< 把右邊的檔案當做左邊的指令的輸入
```
./a.out < input > output
```
* cat
con**cat**enate，串接並輸出一個以上的檔案內容。
cat file1 file2 file3...
* scp
```scp file1 [file2 fil3 ...] b08902000@linux1.csie.org:~/```
把檔案從本地端上傳到遠端的該路徑。
```scp b08902000@linux1.csie.org:~/file .```
把遠端的檔案下載到目前目錄。
* sudo
以superuser的權限執行指令，在工作站上不能使用,有些跟安全性或系統內部的指令要有superuser的權限才能執行
```
sudo apt-get update
sudo apt-get install gcc
```
Q: 那可以直接在工作站上寫code嗎？
A: 可以，用vim！
https://gitbook.tw/chapters/command-line/vim-introduction.html
關於Linux的教學就到這邊，對其他Linux知識有興趣的話可以看看 [鳥哥的Linux私房菜](http://linux.vbird.org/linux_basic/)
習題 5
---
[Judge Girl 50086. Students and Party](https://judgegirl.csie.org/problem/0/50086)
[Judge Girl 50087. See-Saw](https://judgegirl.csie.org/problem/0/50087) 有辦法只用一層迴圈嗎？
[Judge Girl 50122. Knights' Tour](https://judgegirl.csie.org/problem/0/50122)
[Judge Girl 50123. Magic Square](https://judgegirl.csie.org/problem/0/50123)
[Codeforces. Doors Breaking and Repairing](http://codeforces.com/contest/1102/problem/C)
浮點數
---
我們之前一直在使用的```int```和```long long```都只能存整數。
```clike
float score;
double height;
```
```float```和```double```能存帶有小數點的整數。```float```占4個byte，```double```顧名思義占兩倍的memory也就是8個byte。多的memory是用在提升精準度。
```clike
#include <stdio.h>
int main() {
if (0.2 + 0.1 > 0.3)
printf("not ok\n");
else
printf("ok\n");
return 0;
}
```
#### Output:
```
not ok
```
直接對浮點數作比較會出事，**必須**用machine epsilon
```clike
#include <stdio.h>
#include <float.h>
int main() {
if (0.2 + 0.1 - 0.3 < FLT_EPSILON)
printf("ok\n");
else
printf("not ok\n");
return 0;
}
```
#### Output:
```
ok
```
### 輸入與輸出
整數用的是```%d```，浮點數要改成用```%f```
```clike
#include <stdio.h>
int main() {
float a;
scanf("%f", &a);
printf("%f\n", a);
return 0;
}
```
### 類別轉換
如果一個算式同時出現整數和浮點數會怎麼樣？
```int``` -> ```float``` -> ```double```
左邊的會先被轉換成右邊的再運算。
小練習：輸入多個數字，計算他們的平均。
函式
---
呼叫一個函式有幾件事情需要注意：
* 標頭檔 (header file)
* 原型 (prototype)
* 函式名稱 (function name)
* 參數 (parameters)
* 回傳值 (return value)
### 標頭檔
之前其實已經說過要使用武器，必須先說你從哪個武器庫裡拿武器。
系統定義函式
```clike
#include <math.h>
```
使用者定義函式
```clike
include "my_header.h"
```
### 函式原型
函式原型就是函式的說明書，記載函式應該如何使用。
* 在原型後面加上分號表示結束。意思是這裡只會說明函式應該如何使用，而非函式內部如何使用
```clike
double fmax(double x, double y);
```
這個函式的名稱是```fmax```。
這個函式有兩個參數，類別皆為```double```。
* 函式可以沒有參數，這時候在參數的位置寫```void```。
* 參數甚至可以有任意多個，比如```printf```。
回傳值是函式計算的結果，這個函式的回傳值的類別是```double```。
* 函式一樣可以沒有回傳值，```return;```代表結束。
### 基本架構
```clike
int my_functoin(int foo, int bar) {
int baz;
...
return baz;
}
```
### 前置宣告
```clike
#include <stdio.h>
int main() {
say_hello();
return 0;
}
void say_hello() {
print("hello world!\n");
return;
}
```
這個會出事，因為編譯器在```main```讀到```say_hello()```的時候他還不知道```say_hello()```是什麼東西。
solution 1:
```clike
#include <stdio.h>
void say_hello() {
printf("hello world!\n");
return;
}
int main() {
say_hello();
return 0;
}
```
solution 2:
```clike
#include <stdio.h>
void say_hello(void);
int main() {
say_hello();
return 0;
}
void say_hello() {
printf("hello world!\n");
return;
}
```
### 參數傳遞
```clike
#include <stdio.h>
void plus_one(int a) {
a += 1;
}
int main() {
int a;
scanf("%d", &a);
plus_one(a);
print("%d\n", a");
return 0;
}
```
Input:
```
1
```
Output:
```
1
```
變數會先在被呼叫的函式被copy一次，並在退出函式時被消滅，原本的變數不會被變動。
那如果參數是一個陣列呢?
```clike
#include <stdio.h>
void plus_one(int a[]) {
a[0] += 1;
}
int main() {
int a[1] = {1};
plus_one(a);
printf("%d\n", a[0]);
return 0;
}
```
陣列不會做跟上面一樣的事情，而是直接變動陣列裡面的元素。
### 函式的優點
為什麼要用函式？
邦鋒名言： One thing at a time.
* 可以專心寫好一個功能。
* 避免一直重複複寫一樣的功能，程式碼乾淨利落。
* 可讀性高
* ~~之後第14課遞迴的時候要用到。~~
習題 6
---
[Judge Girl 50088. Mountain Travelers](https://judgegirl.csie.org/problem/0/50088)
[Judge Girl 50124. Knights' Tour with Functions](https://judgegirl.csie.org/problem/0/50124)
[Judge Girl 50125. Consecutive 1’s with Function](https://judgegirl.csie.org/problem/0/50125)
指標
---
### 基本用法
首先，什麼是指標?
**指標是一個整數，存的是另一個變數的記憶體位址。**
Nothing more.
私心建議：沒事不要亂用指標，容易出錯而且不好debug。不過有些場合沒有辦法不用，像是用C實作資料結構（第17課）、想用function來直接改變變數的值或想要動態配置記憶體時就一定要用指標。
---
來看一個簡單的範例
```clike=
#include <stdio.h>
int main() {
int a = 10;
int *b = &a;
printf("%d\n", *b);
(*b)++;
printf("%d\n", *b);
return 0;
}
```
#### 解析：
line 5: b是一個指向整數的指標，我們讓他存a的記憶體位址。
宣告的時候在變數名旁邊加\*的意思就是跟編譯器說這個變數是一個指標。
&a就是a的位址（還記得scanf的語法嗎？）
line 6: 在宣告以外的場合在變數名旁加\*的意思是對這個指標存的記憶體位址**取值**
line 7: 我們不止可以取值，還可以直接對記憶體做變動，所以指標十分強大。
---
#### 不要這麼做
```clike
int* a, b, c;
```
---
#### 一個絕對不指向任何有效位址的指標
```clike
#include <stdio.h>
...
ptr = NULL // 或者ptr = 0
```
通常這種指標是用來表示結束點。
---
### 參數傳遞
上面有提到我們可以利用指標讓function直接改變變數的值。
```clike=
#include <stdio.h>
void swap(int a, int b) {
int temp = a;
a = b;
b = a;
}
int main() {
int x, y;
scanf("%d%d", &x, &y);
swap(x, y);
printf("%d %d\n", x, y);
return 0;
}
```
試試看執行這份code，會有什麼問題？
能用指標來實現我想要達成的交換兩變數的值嗎？
### 指標與陣列
之前說過，**陣列就是一串佔用連續記憶體的變數集合**，而且這件事情很重要。
現在我們就來學怎麼用指標的語法對陣列操作。
```clike
int a[100];
int *b = a;
```
這樣```*b```就等同於```a[0]```
我們不可能只對陣列的第一個元素做操作，對第i個元素取值可以用下面這個片語
```*(b + i)```，這個和```b[i]```是完全等價的
那如果我們現在不想要指向第一個元素了呢?
```
b++;
b += i
```
都可以。
那為什麼這些寫法會成立？因為**陣列就是一串佔用連續記憶體的變數集合**。
* 要注意的是這裡的i是以元素大小而不是Byte數作為單位，比如```*(b + i)```說的是對i個之後的int取值。
### Pointers to pointers
```clike
int a = 10
int *b = &a;
int **c = &b;
```
#### 解析：
```b```存的是整數```a```的位址
```c```存的是指向```a```的指標即```b```的位址
習題 7
---
[Judge Girl 50128. Split a List](https://judgegirl.csie.org/problem/0/50128)
[Judge Girl 50129. Loops](https://judgegirl.csie.org/problem/0/50129)
[Judge Girl 50090. Count Pointers](https://judgegirl.csie.org/problem/0/50090)
[Judge Girl 50091. Two-level Table](https://judgegirl.csie.org/problem/0/50091)
字元
---
這星期回到比較輕鬆的章節~
### 基本用法
在第一堂課其實就有提倒```char```字元了 XD 今天再稍微多說一點。
```clike
#include <stdio.h>
int main() {
char c;
scanf("%c", &c);
printf("%c\n", c);
printf(sizeof(c));
return 0;
}
```
stdin:
```
a
```
stdout:
```
a
1
```
那現在來一個黑魔法
```clike
#include <stdio.h>
int main() {
char c = 'a'; // 字元要用單引號
c -= 32;
printf("%c\n", c);
return 0;
}
```
stdout:
```
A
```
* 字元本質上存的也是一個數字，和```int```沒有差別！那為什麼用字元就能印出字母？
答曰因為有ASCII(American Standard Code for Information Interchange)碼。這個編碼把0~127的整數對應到一個字母上。
* ASCII一開始的確是7bit(0~127)的編碼，但現在普遍會使用Extended ASCII來充分使用8個bit。
* 因為```char```的範圍很小，要注意overflow的問題噢！
### 一點點題外的題外話
在台灣普及的中文編碼是大五碼(Big-5)，但各廠及政府皆推出自己的大五碼延伸集，彼此互不相容，造成亂碼問題。
參考：https://zh.wikipedia.org/wiki/%E5%A4%A7%E4%BA%94%E7%A2%BC
https://zh.wikipedia.org/wiki/%E4%B8%AD%E6%96%87%E4%BA%82%E7%A2%BC
### 常用函式
| 函式名稱 | 分類 |
| - | - |
| ```isalnum``` | 英文字母或數字 |
| ```isalpha``` | 英文字母 |
| ```islower``` | 小寫英文字母 |
| ```isupper``` | 大寫英文字母 |
| ```isdigit``` | 數字 |
| ```isxdigit``` | 16進位數字 |
| ```isprint``` | 可顯示字元（包含空白） |
| ```isgraph``` | 可顯示字元（不包含空白）|
| ```isspace``` | 空白 |
| ```ispunct``` | 標點符號 |
| ```iscntrl``` | 控制字元 |
回傳結果是 0/1 的整數
這是邦鋒課本裡面的表，我覺得比較常用的是```isdigit``` ```isalnum``` ```isupper``` ```islower``` ```isspace```。
```clike
c = 'a'
if (isalpha(c))
printf("yes\n");
else
printf("no\n");
```
| 函式名稱 | 動作 |
| - | - |
| ```tolower``` | 轉成小寫英文字母 |
| ```toupper``` | 轉成大寫英文字母 |
回傳結果是做完動作的字元
```clike
c = 'a'
printf("%c\n", toupper(c));
```
### 補充: 一個神奇的bug
```clike
#include <stdio.h>
int main()
{
char c;
printf("Input No.1\n");
scanf("%c", &c);
printf("c = %c\n", c);
printf("Input No.2\n");
scanf("%c", &c);
printf("c = %c\n", c);
printf("Input No.3\n");
scanf("%c", &c);
printf("c = %c\n", c);
return 0;
}
```
```
Input No.1
s
c = s
Input No.2
c =
Input No.3
a
c = a
```
字串
---
> C 其實沒有字串這個類別。
好，我們今天就上到這裡，下課。
<br><br><br><br><br><br><br><br><br><br>
C++和Python其實都有```string```這個類別，不過C沒有，我們用**字元的陣列**來代表字串。
### 基本用法
```clike
#include <stdio.h>
int main() {
char a[80];
scanf("%s", a); // 讀到空格或換行就結束。
printf("%s\n", a);
char b[64] = "aloha", c[64] = "int main()\n{\n}\n";
// 字串的初始化要用雙引號 " "
printf("%s\n%s\n", b, c);
return 0;
}
```
問題就來了。```b```的長度是64，aloha只有5個字，當你在```printf```的時候編譯器是怎麼知道你的字串已經結束？
還記得上次提到的ASCII表嗎?ASCII表的第一個字元 NULL就是 ```\0```，字串處理函式遇到```\0```就知道字串已經結束。
小練習：如果你要存一個最多100個字的字串，你的字元陣列最少要開多大？
* 注意： 字串的題目很多時候出bug都是因為最後的```\0```沒有處理好。
### 其他寫法
這些是課本有提到不過我個人覺得比較少用到的寫法
```clike
char a[] = "aloha" // 沒說長度，讓編譯器自己算。
char *b = "aloha" // 字元指標
```
### 常用函式
首先，你必須```#include <string.h>```。
1. strlen
給定一個字串，回傳字串的長度
```clike
#include <string.h>
#include <stdio.h>
int main() {
char a[80];
scanf("%s", a);
printf("%lu\n", strlen(a));
return 0;
}
```
小練習：自己實作```strlen```函式。
2. strcpy, strncpy, strcat, strncat
```strcpy```會把source字串複製並**覆蓋**到destination。strncpy做的事情也一樣，只是你需要多給一個參數說你想複製多少個字元。
```clike
#include <string.h>
#include <stdio.h>
int main() {
char source[80] = "aloha", destination[80] = "hello";
strcpy(destination, source);
printf("%s\n", destination);
return 0;
}
```
```strcat```會把source字串複製並**接到**destination。strncat做的事情也一樣，只是你需要多給一個參數說你想複製多少個字元。
```clike
#include <string.h>
#include <stdio.h>
int main() {
char source[80] = "aloha", destination[80] = "hello";
strcat(destination, source);
printf("%s\n", destination);
return 0;
}
```
* 注意：編譯器不會幫你檢查複製/接上的結果會不會超過目標字元陣列的大小，超過的部分會被吃掉，這也就是所謂緩衝區覆蓋(buffer overrun)
3. strcmp, strncmp
比較兩個字串是否相同，相同的話回傳0，前者比後者“大”回傳正數，後者比回傳“大”回傳負數。
大小是用ASCII表作為標準。
strncmp做的事情也一樣，只是你需要多給一個參數說你想比對前幾個字元。
```clike
#include <string.h>
#include <stdio.h>
int main() {
printf("%d\n", strcmp("aloha", "hello"));
printf("%d\n", strcmp("aloha", "aloha"));
return 0;
}
```
小練習:讀入兩個字串，檢查這兩個字串是否相同，字串的長度 < 64。
4. strchr, strrchr, strstr
strchr在字串中搜尋一個字元c, 如果找的到就回傳第一個字元c的記憶體位置。
strrchr也是一樣，不過就是反著找。
strstr也是一樣，不過是在字串裡面找字串。
```clike
#include <string.h>
#include <stdio.h>
int main() {
char a[80] = "helloaloha";
char *ptr = strchr(a, 'a');
printf("%lu\n", ptr - a);
return 0;
}
```
5. strtok
strtok會把字串切成一段一段的token。token就是字串被delimeters中的任何字元所隔開的部分。
strtok的用法很特別，分為3個步驟。
* 先呼叫strtok一次。```token = strtok(string, delimeters)``` 會把string切成很多個token並指定給定一個指標token。每個token都會在最後被塞入一個\0，可以用各種字串函式處理。
* 進入while迴圈檢查token是否為NULL，然後作處理。
* 呼叫多一次strtok ```token = strtok(NULL, delimeters)```跳到下一個token。
```clike
#include <string.h>
#include <stdio.h>
int main() {
char a[80] = "welcome,to,facebook.mark.zuckerberg";
char *token;
token = strtok(a, ",.");
while (token != NULL) {
printf("%s\n", token);
token = strtok(NULL, ",.");
}
return 0;
}
```
最後一份習題
---
寫一份能印出自己的Code。
[Quine](https://en.wikipedia.org/wiki/Quine_(computing))
例 :
```clike
#include <stdio.h>
int main() {
char c;FILE *f;
f=fopen(__FILE__,"r");
while((c=fgetc(f))!=EOF)putchar(c);
}
```
這個計程不會考，不過我覺得還蠻有趣的 XD
Sign in with Wallet
Connect another wallet