# 資訊學科能力競賽校內初賽秘笈
by: hush
---
## C/C++基本語法
* Input/Output 輸入/輸出
* Variable 變數
* Operator 運算子<font color="red">(優先級)</font>
* if/else 判斷結構
* Loop 迴圈
* Array 陣列
* Function 函式<font color="red">(作用域)
* Recursion 遞迴</font>
* Pointer 指標
----
[APCS觀念題範例](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2022/10/觀念題_題型範例.pdf)
當觀念題爆算一波就對了
---
## 儲存容量單位
1Byte=8Bits
----
例題：
from 107北二區筆試
----
Ans: (B)
---
## 進位制
- 日常：10進制、12進制(hour)、60進制(second, minute)
- 計算科學：2進制、8進制、16進制
----
----
英文縮寫
* 10進制：Dec (Decimal)
* 2進制：Bin (Binary)
* 8進制：Oct (Octal)
* 16進制：Hex (Hexadecimal)
----
### 10進制轉2進制
----
方法一：觀察法(靠感覺)
e.g.
$13=1\times 2^3+1\times 2^2+0\times 2^1+1\times 2^0$
$13_{(10)}=1101_{(2)}$
----
方法二：短除法
----
### 10進制轉n進制
用短除法，e.g.:
$923_{(10)}=39B_{(16)}$
$1234_{(10)}=44A_{(17)}$
$99_{(10)}=10200_{(3)}$
----
### n進制轉10進制
直接乘回去，e.g.:
$10110_{(2)}=1\times 2^4+1\times 2^2+1\times 2^1=22_{(10)}$
$A1B_{(16)}=10\times 16^2+1\times 16^1+11\times 16^0=2587_{(10)}$
$ABC_{(23)}=10\times 23^2+11\times 23^1+12\times 23^0=5555_{(10)}$
----
### 2、8、16進制快速轉換
e.g.: $10111001_{(2)}=271_{(8)}=B9_{(16)}$
----
### 10進制小數轉2進制小數
1. 先處理整數部分
2. 把小數部分$\times 2$，記下乘完的整數部分(0 or 1)
3. 保留小數部分重複2.直到小數變0或出現循環
----
e.g.: 0.625
$0.625\times 2 = 1.25\quad\Rightarrow\quad 1 \, (\text{整數}),\, 0.25\, (\text{小數})$
$0.25\times 2 = 0.5\quad\Rightarrow\quad 0\, (\text{整數}),\, 0.5\, (\text{小數})$
$0.5\times 2 = 1.0\quad\Rightarrow\quad 1\, (\text{整數}),\, 0\, (\text{小數})$
取下來的整數部分從上到下排列：1 0 1
所以：$0.625_{(10)} = 0.101_{(2)}$
----
e.g.: 0.2
$0.2 \times 2 = 0.4 \quad \Rightarrow \quad 0 , (\text{整數}), 0.4, (\text{小數})$
$0.4 \times 2 = 0.8 \quad \Rightarrow \quad 0 , (\text{整數}), 0.8, (\text{小數})$
$0.8 \times 2 = 1.6 \quad \Rightarrow \quad 1 , (\text{整數}), 0.6, (\text{小數})$
$0.6 \times 2 = 1.2 \quad \Rightarrow \quad 1 , (\text{整數}), 0.2, (\text{小數})$
$0.2 \times 2 = 0.4 \quad \Rightarrow \quad (\text{遇到循環})$
$0.2_{(10)} = 0.\overline{0011}_{(2)}$
----
### 2進制負數
1. 將所有位元倒轉，即為一補數(1’s Complement)
2. 將一補數+1，即為二補數(2’s Complement)
3. 二補數(2’s Complement)即為此負數的二進制表示
---
## 位元運算
* NOT
* AND
* OR
* XOR
* LSH, RSH
----
### NOT
C++中"~"表示NOT(取一補數)
```cpp=
int a=12;
cout << ~a; //-13
```
----
### AND
C++中"&"表示AND
```cpp=
int a=6,b=11;
cout << a&b ; //2
```
----
### OR
C++中"|"表示OR
```cpp=
int a=5,b=3;
cout << a|b; //7
```
----
### XOR 互斥或
C++中"^"表示XOR
```cpp=
int a=5,b=3;
cout << a^b; //6
```
----
### LSH 左移
左移(一格)示意圖，C++中"<<"表示LSH
```cpp=
int a=5;
cout << (5<<3); //5*8=40
```
----
### RSH 右移
右移(一格)示意圖，C++中">>"表示RSH
```cpp=
int a=18;
cout << (a>>2); //18/4=4
```
---
## 資料結構
----
### 堆疊(Stack)
----
Stack 是一種後進先出（Last-In-First-Out, LIFO）的資料結構，每次取出的元素是最晚放進去的元素。
感謝Programiz的圖
----
| 常用函式 | 功能 |
| -------- | ------------------------ |
| empty() | 回傳stack是否為空 |
| size() | 回傳stack有幾個元素 |
| push(x) | 將元素x加入到stack的頂端 |
| pop() | 將stack頂端的元素彈出(刪除) |
| top() | 查詢stack的頂端的元素 |
p.s.: 沒有clear()
----
```cpp=
#include <iostream>
#include <stack>
using namespace std;
int main()
{
stack<int> s;
s.push(10);
cout<<s.top()<<'\n'; //10
cout<<s.empty()<<'\n'; //0
cout<<s.size()<<'\n'; //1
s.push(20);
cout<<s.top()<<'\n'; //20
cout<<s.empty()<<'\n'; //0
cout<<s.size()<<'\n'; //2
s.pop();
cout<<s.top()<<'\n'; //10
cout<<s.empty()<<'\n'; //0
cout<<s.size()<<'\n'; //1
s.pop();
//cout<<s.top()<<'\n'; //stack為空會RE
cout<<s.empty()<<'\n'; //1
cout<<s.size()<<'\n'; //0
}
```
----
### 佇列(Queue)
----
Queue 是一種先進先出（First-In-First-Out, FIFO）的資料結構，每次取出的元素是最早放進去的元素。
感謝Programiz的圖
----
| 常用函式 | 功能 |
| -------- | -------------------- |
| empty() | 回傳queue是否為空 |
| size() | 回傳queue有幾個元素 |
| push(x) | 將元素x加入queue的後端 |
| pop() | 將queue前端的元素彈出(刪除) |
| front() | 查詢queue的前端的元素 |
| back() | 查詢queue的後端的元素 |
p.s.: 從後端放入，一樣沒有clear()
----
```cpp=
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int> q;
q.push(10);
cout<<q.front()<<'\n'; //10
cout<<q.back()<<'\n'; //10
cout<<q.empty()<<'\n'; //0
cout<<q.size()<<'\n'; //1
q.push(20);
cout<<q.front()<<'\n'; //10
cout<<q.back()<<'\n'; //20
cout<<q.empty()<<'\n'; //0
cout<<q.size()<<'\n'; //2
q.pop();
cout<<q.front()<<'\n'; //20
cout<<q.back()<<'\n'; //20
cout<<q.empty()<<'\n'; //0
cout<<q.size()<<'\n'; //1
q.pop();
//cout<<q.front()<<'\n'; //queue為空會RE
//cout<<q.back()<<'\n'; //queue為空會RE
cout<<q.empty()<<'\n'; //1
cout<<q.size()<<'\n'; //0
}
```
---
## 圖論
我偷懶所以直接丟[簡報](https://hackmd.io/@zanthia99/ryaORk79yx)給你們看
---
## 二元樹的前中後序遍歷
二元樹的DFS可以分成
* 前序遍歷 (Preorder Traversal)
* 根節點->左子樹->右子樹
* 中序遍歷 (Inorder Traversal)
* 左子樹->根節點->右子樹
* 後序遍歷 (Postorder Traversal)
* 左子樹->右子樹->根節點
----
e.g.
* 前序：1->2->4->7->8->5->3->6->9->10
* 中序：7->4->8->2->5->1->3->9->6->10
* 後序：7->8->4->5->2->9->10->6->3->1
----
- 經典題：
1.給你中序+前序，求後序
2.給你中序+後序，求前序
----
- 第一題解法：
1.前序第一個值為根節點
2.用根節點在中序分割左右子樹
3.對左右子樹遞迴做1.
4.還原子樹後即可求後序
- 第二題解法：
1.後序最後一個元素為根節點
2.3.一樣
4.還原子樹後即可求前序
---
## 複雜度
抱歉我繼續偷懶[簡報在這](https://hackmd.io/@hush/rkXrlj420#/)
---
## 排序演算法
- [基本的排序演算法](https://hackmd.io/@hush/r1aN7sEb1l)
- [Quick sort](https://hackmd.io/@hush/HyjCw3bzke)
- [Merge sort](https://hackmd.io/@hush/S1CIgQb4Jx)
---
## 數論
[簡報在這](https://hackmd.io/@hush/H1zmO819Jl#/)
----
重點：
- 費馬小定理
- 快速冪
---
## 邏輯
----
- 例題：
三位智者在樹下睡覺時被小孩在臉上塗鴉，三人醒來時都看著對方大笑，結果一段時間後大家都笑不出來了，為何？
----
- 解答：
任何一位智者都會想，另外兩位(取名為A, B)都在笑，但若自己沒被塗鴉，A看到B在笑就會發現A自己也被塗鴉，那A就不會笑(矛盾)
----
- 有趣練習題：[腦力補給](https://www.morningrefresh.com/iq/category/14/)
---
# 謝謝大家
{"description":"by: hush","title":"學科校內初賽考點","contributors":"[{\"id\":\"b49547c8-0e7f-46d0-99b2-8a45dfee8e90\",\"add\":6532,\"del\":43}]"}