# APCS考前再確認

## 觀念題的熟練程度

1. 程式碼追蹤
- `遞迴`呼叫
- 多層`for loop` + `if-else`

2. 運算子的優先順序與使用
- ** 最優先
- AND/OR/NOT/XOR

3. 經典演算法觀念
- 二元搜尋法只適用於**已排序資料**

4. 電腦運作知識：電腦記憶體的使用
5. 變數的範圍：全域變數 vs. 區域變數

## 實作題的熟練程度
1. 確保熟悉`Eclipse` IDE操作
- 新增Pydev專案
- 新增.py檔案
- 編輯與執行
2. 資料輸入
- 轉換資料型態：輸入字串，轉成`int`型態

 a = int(input())

- 一次輸入多個**用空白隔開**的字串，

 list_a = input().split(" ")

- 將`list`中元素轉換成`int`型態

list_a = input().split(" ")
list_b = []

for i in range (len(list_a)):
	list_b.append(int(list_a[i])) 

3. 善用`f-string`語法輸出資料
- 同時印出多個變數

a = 1
b = 2
print(f'{a} {b}')

- 不換行列印

print(f"Hello", end='')
print(f"Hello")

4. 熟悉`for-loop`控制操作：畫出以下三角形

   *
  ***
 *****
*******

5. `list`操作
- `.append()`: 加入元素
- `.sort()`: 由小到大排序
- `.sort(reverse=True)`: 由大到小排序

6. `function`宣告與呼叫

def func():
    return 

7. 經典資料結構
- Stack/Queue的建立與操作
- Tree的建立與操作
- 利用親子關係建立一棵樹
- DFS: 求樹的最大深度

family = []  # 宣告一個List，紀錄每個成員的child
blood_distance = 0       # 紀錄最長血緣距離
isChild = [False]*100000    # 紀錄每個成員是否為其他人的小孩
children = [0]*100000    # 紀錄每個成員有多少小孩

# 計算從該node出發的最大深度，也就是與該成員的最長血緣距離
def DFS(node):
    global blood_distance
    
    # 如果該成員沒有child，回傳血緣距離為0
    if(children[node] == 0):
        return 0
    # 如果該成員有一個child，遞迴呼叫往下找，回傳血緣距離
    elif (children[node] == 1):
        for i in range(n-1):
            if(family[i][0] == node):
                return DFS(family[i][1]) + 1
    # 如果該成員有兩個以上child，遞迴呼叫往下找，各自得到最長的血緣距離後比較，回傳較長血緣距離
    else:
        depth1 = 0 #紀錄最長深度
        depth2 = 0 #紀錄次長深度
        for i in range(n-1):
            if(family[i][0] == node):
                depth = DFS(family[i][1])+1
                if depth > depth1:
                    depth1 , depth = depth, depth1
                if depth  > depth2:
                    depth2 = depth
        
        blood_distance = max(blood_distance, depth1 + depth2)
        return depth1
        
# 使用者輸入家族成員總數
n = int(input())

# 使用者輸入各node的親子關係
for i in range(n-1):
    temp = input().split(' ')
    member = []
    member.append(int(temp[0]))
    member.append(int(temp[1]))
    # 各node的親子關係彙總到family
    family.append(member)
    # 登記各成員是否為他人的child
    isChild[int(temp[1])] = True
    # 加總每個node的小孩數量
    children[family[i][0]] += 1
    
# 找到root
for i in range(n):
    if (isChild[i] == False):
        root = i
        break

# 計算根節點的最大深度
deepest = DFS(root)

8. 經典搜尋/排序演算法
- 描述運作方式：[知名搜尋與排序演算法](https://hackmd.io/@howkii-studio/search_sort_algo)
- 用程式碼實作其運作

###### tags: `APCS檢定應試指南`