# APCS實作題分析
:::info
作答策略：
1. 了解**問題描述**，掌握輸出，確認輸入
2. 決定資料結構與演算法，用明確文字描述進行步驟
3. 開始撰寫程式碼，善用`print(變數)`檢視演算法運算過程是否正確
4. 注意檔名命名，須根據試卷要求一致，否則不予計分
5. 練習時，請計算整體程式演算法的時間、空間複雜度，探討改善空間
:::

## 105年3月
### 1. 成績指標
::: success
難度： :star:
單元範圍：`容器資料型別` `資料排序` `控制流程：判斷條件`
:::

:::info
**本題演算法設計參考：**
1. 請使用者輸入學生人數，定義`成績list`的長度
2. 請使用者輸入成績，以`成績list`儲存
3. 呼叫sort()進行`成績list`排序，並且依序將元素印出
4. 條件判斷：
- 檢查最低成績是否及格，如果是，表示全部都及格
- 輸出`best case`
- 印出`最低及格者成績`
- 結束迴圈
- 或者，檢查最高成績是否不及格，如果是，表示全部人都不及格
- 印出`最高不及格者成績`
- 印出`worst case`
- 結束迴圈
- 其他情況
- 掃描`成績list`，找出最高不及格者
- 掃描`成績list`，找出最低及格者
- 結束迴圈
:::

:::spoiler 參考程式碼

#請使用者輸入學生人數，定義成績list的長度
stu_num = int(input("Please Enter the number of students> "))
#請使用者輸入成績，以成績list儲存
stu_list = []
temp = input("Please enter the score of students> ").split()
for i in range(stu_num):
    stu_list.append(int(temp[i]))

#呼叫sort()進行成績list排序，並且輸出
stu_list.sort()
for i in range(stu_num):
    print(f"{stu_list[i]} ",end='')
print()
#條件判斷：
#檢查最低成績是否及格
#如果是，輸出best case、最低及格者成績，結束迴圈
if (stu_list[0] >= 60):
    print("best case")
    print(stu_list[0])
#檢查最高成績是否不及格
#如果是，輸出worst case，結束迴圈
elif(stu_list[stu_num-1] <= 60):
    print(stu_list[stu_num-1])
    print("worst case")

#其他情況
#掃描成績list，找出最高不及格者或是最低及格者
else:
    #找出最高不及格者
    for i in range(stu_num-1, -1, -1):
        if (stu_list[i] < 60):
            print(stu_list[i])
            break
    #最低及格者
    for i in range(stu_num):
        if (stu_list[i] >= 60):
            print(stu_list[i])
            break

:::

### 2. 矩陣轉換
`矩陣` `容器資料型別` `控制流程：迴圈` `函式`


:::info
**本題演算法設計參考：**
1. 設計function: 旋轉矩陣
- 使用臨時的陣列儲存旋轉過程
2. 設計function: 翻轉矩陣
- 使用臨時的陣列儲存翻轉過程
4. 讓使用者輸入三個數字
- 矩陣列數
- 矩陣行數
- 矩陣操作步驟數量
5. 讓使用者輸入矩陣內容
- 每列的值
6. 讓使用者依序輸入操作代號，但是倒過來執行
- 根據操作動作代號呼叫function(0:旋轉, 1:翻轉)
6. 輸出原始矩陣內容
:::
:::spoiler 參考程式碼

# 設計function: 旋轉矩陣
# 使用臨時的陣列儲存旋轉過程
def rotate(mat):
    temp_matrix = []
    for i in range(len(mat[0])-1, -1, -1):
        temp = []
        for j in range(0, len(mat)):
            temp.append(mat[j][i])
        temp_matrix.append(temp)
    return temp_matrix

# 設計function: 翻轉矩陣
# 使用臨時的陣列儲存翻轉過程
def turn(mat):
    temp_matrix = []
    for i in range(len(mat)-1, -1, -1):
        temp_matrix.append(mat[i])
    return temp_matrix

# 讓使用者輸入三個數字
# r: 矩陣列數
# c: 陣行數
# m: 矩陣操作步驟數量

r, c, m = input("Please enter R, C, M> ").split(" ")

# 讓使用者依序輸入每列矩陣內容
matrix = []
for i in range(0, int(r)):
    temp_list = []
    temp = input().split(" ")
    for j in range(0, int(c)):
        temp_list.append(int(temp[j]))
    matrix.append(temp_list)

# 讓使用者依序輸入操作代號，但是倒過來執行
# 操作動作代號(0:旋轉, 1:翻轉)
operation = input().split(" ")

for i in range(int(m)-1, -1, -1):
    if operation[i] == '0':
        temp_mat = rotate(matrix)
    else:
        temp_mat = turn(matrix)

    # 將每次運算結果複製給matrix
    matrix = temp_mat[:]

# 輸出原始矩陣的列數與行數
print(f"{len(matrix)} {len(matrix[0])}")

# 輸出原始矩陣內容
for i in range(len(matrix)):
    for j in range(len(matrix[0])):
        print(f"{matrix[i][j]}", end=' ')
    print()

:::

### 3. 線段覆蓋長度
`函式與遞迴`

:::info
**本題演算法設計參考：**
1. 宣告兩個list，分別儲存兩個線段資訊，用`True`,`False`紀錄
2. 設計一個function，標記線段資訊
3. 請使用者輸入線段數量
4. 請使用者根據線段數量，依序輸入起點、終點座標值，用空格隔開
5. 呼叫function，標記線段
6. 利用while迴圈找出各列索引為True的數量，輸出總覆蓋的長度
:::

:::spoiler 參考程式碼

# 宣告兩個list，分別儲存兩個線段資訊，用`True`,`False`紀錄
list1 = [False] *100000
list2 = [False] *100000
size = len(list1)
index = 0
counter = 0

# 設計一個function，標記線段資訊
def segment(list_a, start, end):
    for i in range(start, end):
        list_a[i] = True

# 請使用者輸入線段數量
num = int(input())

# 請使用者輸入第一段線段起點、終點座標值，用空格隔開
temp = input().split(' ')
start = int(temp[0])
end = int(temp[1])
# 呼叫function，標記線段
segment(list1, start, end)

# 請使用者輸入其他段起點、終點座標值，用空格隔開
for i in range(1, num):
    temp = input().split(' ')
    start = int(temp[0])
    end = int(temp[1])
    # 呼叫function，標記線段
    segment(list2, start, end)
    for j in range(size):
        if list1[j] == True or list2[j] == True:
            list1[j] = True
# 利用迴圈找出各列索引為True的輸出總覆蓋的長度
while index < size:
    if list1[index] == True:
        counter += 1
    index +=1
print(f"{counter}")

:::

### 4. 血緣關係
`資料結構` `函式與遞迴`
:::info
**本題演算法設計參考：**
1. 宣告一個List，紀錄每個成員的child
2. 宣告以下變數
- 紀錄最長血緣距離
- 紀錄每個成員是否為其他人的小孩
- 紀錄每個成員有多少小孩
3. 設計一個function，計算從該node出發的最大深度，也就是與該成員的最長血緣距離
- 如果該成員沒有child，回傳血緣距離為0
- 如果該成員有一個child，遞迴呼叫往下找，回傳血緣距離
- 如果該成員有兩個以上child，遞迴呼叫往下找，各自得到最長的血緣距離後比較，回傳較長血緣距離
4. 使用者輸入家族成員總數
5. 使用者輸入各node的親子關係
6. 找到root
7. 呼叫function，計算根節點的最大深度
8. 與目前最長血緣深度比較，取較大值印出

:::

:::spoiler 參考程式碼

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)

# 與目前最長血緣深度比較，取較大值印出
blood_distance = max(deepest, blood_distance)
print(f"{blood_distance}")

:::

## 105年10月
### 1. 三角形辨別
:::info
**本題演算法設計參考：**
1. 請使用者輸入三個線段長度
2. 從小到大依序排列三個線段
3. 判斷以下條件：
- a^2^ + b^2^ < c^2^：輸出銳角三角形
- a^2^ + b^2^ = c^2^：輸出直角三角形
- a^2^ + b^2^ > c^2^：輸出鈍角三角形
:::

:::spoiler 參考程式碼

in1 = input().split()
	
# 依序排列
temp.sort()
a = int(temp[0])
b = int(temp[1])
c = int(temp[2])
print(f"{a} {b} {c}")
	
#判斷三角形類型
if (a + b) <= c:
	print("No") #無法構成三角形
		continue;
if a*a + b*b > c*c:
	print("Acute")

elif a*a + b*b == c*c:
	print("Right")
else:
	print("Obtuse")

:::

### 2. 最大和
:::info
本題演算法設計參考：
1. 請使用者輸入數字
2. 紀錄N群數字中，最大的數字
3. 計算全部最大數字的加總
4. 找出哪些最大數字，可以被整除加總

:::

:::spoiler 參考程式碼

# 請使用者輸入數字
temp = input("Enter N, M> ").split()
#N個數字
N = int(temp[0])
#每群M個正整數
M = int(temp[1])
number = []

for i in range(0, N):
	temp = input("").split()
	temp_list = []
	for j in range(0, M):
		temp_list.append(int (temp[j]))
	number.append(temp_list)

#紀錄N群數字中，最大的數字
BIG = []
for i in range(0,N):
	BIG.append(0)
	
for i in range(0, N):
	BIG[i] = int(number[i][0])
	for j in range(0, M):
		if int(number[i][j]>BIG[i]):
			BIG[i] = int(number[i][j])
total = 0

#計算全部最大數字的加總
for i in range(0, N):
	total = total + BIG[i]

print(total)

#找出哪些最大數字，可以被整除加總
flag = False
for i in range(0, N):
	if total % BIG[i] == 0:
		flag = True
		print(f'{BIG[i]}', end='')
if flag == False:
	print("-1")

:::

### 3. 定時K彈
`環狀鏈結串列`

:::info
**本題演算法設計參考：**
1. 建立環狀鏈結串列，包括玩家號碼跟指標
2. 紀錄爆炸次數，初始值為0
3. 遊戲開始
- 當累加器加到m次時，就從環狀串列中刪除這個號碼
- 累加器歸零、總人數少1
- 剩下一人時，輸出這位幸運者的號碼
:::

:::success
可運用這個類別宣告技巧來建立環狀鏈結串列，參考[《Python物件與類別》](https://hackmd.io/@howkii-studio/object_class#none_property)
:::

:::spoiler 參考程式碼

pos = []
temp = input().split()
n = int(temp[0])
m = int(temp[1])
k = int(temp[2])


class Struct(object):
	pass
node = Struct()

#建立環狀鏈結串列
for i in range(n-1):
	temp = []
	node.data = i+1
	node.next = i+1
	temp.append(node.data)
	temp.append(node.next)
	pos.append(temp)

temp = []
node.data = n
node.next = 0
temp.append(node.data)
temp.append(node.next)
pos.append(temp)

#爆炸次數歸零
explode = 0
pre = 0
now = 0
counter = 0

#開始進行遊戲
while explode < k:
	counter += 1
	if counter == m:
		pos[pre][1] = pos[now][1]
		counter = 0
		n -= 1
		explode += 1
	pre = now
	now = pos[now][1]

print(f'{pos[now][0]}')

:::

### 4. 棒球遊戲
:::info
**本題演算法設計參考：**
1. 請使用者輸入每位打者打擊結果、目前局數
2. 宣告變數紀錄每個打序的壘包推進、壘上狀態、出局數狀態
3. 記錄每局的打序造成的壘包推進
- 如果打擊結果為"FO"或"GO"或"SO"，則紀錄為0
- 如果打擊結果為"1B"，則紀錄為1
- 如果打擊結果為"2B"，則紀錄為2
- 如果打擊結果為"3B"，則紀錄為3
- 如果非以上結果，則為HR，紀錄為4
4. 遊戲開始，帶入打擊結果與局數
- 如果是三出局，壘上清空
- 如果是全壘打，分數加上壘上人數、壘上清空
- 如果是一壘安打
- 如果三壘有人就加一分
- 打者上一壘
- 如果是二壘安打
- 如果是二、三壘上有人就加一分
- 如果一壘有人，就推進到三壘
- 打者上二壘
- 如果是三壘安打
- 如果一、二、三壘有人就加一分
- 打者上三壘
5. 輸出目前局數的得分
:::

## 106年3月
### 1. 秘密差
:::info
**本題演算法設計參考：**
1. 使用list儲存使用者輸入的整數
2. 判斷整數位數總長度是奇數還是偶數
- 如果是奇數：把奇數位元跟偶數位元各自加總
- 如果是偶數：把奇數位元跟偶數位元各自加總
3. 把各自加總結果相減，取絕對值，輸出結果
:::

:::spoiler 參考程式碼

x = input("Please enter the integer(<1000 digits)> ")
odd = 0
even = 0

# 如果第一個字元是奇位數
if (len(x) %2) != 0:
	for i in range(len(x)):
		if i % 2 == 0:
			odd += int(x[i])  #奇位數的數字加總
		else:
			even += int(x[i]) #偶位數的數字加總
# 如果第一個字元是偶位數
else:
	for i in range(len(x)):
		if i % 2 == 0:
			even += int(x[i]) #偶位數的數字加總
		else:
			odd += int(x[i])  #奇位數的數字加總
#輸出秘密差
print(abs(odd - even))

:::

### 2. 小群體
`流程控制：條件判斷`

:::info
**本題演算法設計參考：**
1. 建立團體
2. 找到群體的源頭
3. 繼續找沒有被拜訪的成員且不在其他小群體的人，找出其他小群體
:::

:::spoiler 參考程式碼

# 建立團體
n = int(input())

friend_NO=[]
temp = input().split()
for i in range(n):
	friend_NO.append(int(temp[i]))

visit = []
for i in range(n):
	visit.append(0)

i = 0
counter = 0		 # 紀錄小群體的數量
success = False  # 紀錄是否找到小群體

while success == False:
	head = i
	counter += 1
	
	# 找到該群體的源頭
	while friend_NO[i] != head and visit[i] == 0:
		visit[i] = 1
		i = friend_NO[i]
	
	visit[i] = 1
	success = True
	
	# 繼續找沒有被拜訪的成員且不在其他小群體的人，找出其他小群體
	for i in range(n):
		if visit[i] == 0:
			success = False
			break

print(counter)

:::

### 3. 數字龍捲風

### 4. 基地台

:::info
**本題演算法設計參考：**
1. 讀取服務點數目
2. 讀取基地台數量
3. 讀取各個服務點位置，存入`list`P
4. 依據`list`P所記錄服務點的距離資訊，由小到大排序
5. 使用二分搜尋法找出符合題意的最小直徑
- 符合題意：是否可覆蓋所有據點
- 輸入：直徑
- 輸出：
- 可以：回傳Y
- 不可：回傳N
- 最小直徑為1、最大直徑為無條件捨去（服務站最遠距離/基地台個數)+1
- 答案介於最小路徑跟最大路徑之間，使用二分搜尋法找
6. 輸出答案
:::

## 106年10月
### 1. 邏輯運算子

### 2. 交錯字串<a id=k-string></a>
:::info
本題演算法設計參考如下：

1. 使用變數紀錄以下事項：
- `isPreLower`: 前一個字元是否小寫，設為True；反之，設為False
- `upperNo`: 連續大寫的字元總數
- `lowerNo`:連續小寫的字元總數
- `alternating_len`: 目前交錯的字串長度
- `longest`: 最長交錯的子字串長度，初始值為0
2. 請使用者輸入k值跟字串
3. 從左到右掃描字串，處理第一個字元
- 如果第一個字元是大寫
- `isPreLower`設定False
- `upperNo` = 1
- 如果k值是1
- alternating_len` = 1
- `longest` = 1
- 如果第一個字元是小寫
- isPreLower`設定True
- `lowerNo` = 1
- 如果k值是1
- alternating_len` = 1
- `longest` = 1
4. 處理第二個字元以後
- 每次取得`alternating_len`時，必須跟`longest`比較大小，存到`longest`
- 無論大小寫字母，當連續大寫的字元總數大於k，超過的部分不列入`alternating_len`
- 根據這四種情況進行
- 前一個字元是大寫，目前字元是大寫
- 前一個字元是小寫，目前字元是大寫
- 前一個字元是小寫，目前字元是小寫
- 前一個字元是大寫，目前字元是小寫
:::

::: spoiler 參考程式碼

k = int(input("Please enter K value(Integer)> "))
strings = input("Please enter the string> ")
'''
`isPreLower`: 前一個字元是否小寫，設為True；反之，設為False
`upperNo`: 連續大寫的字元總數
`lowerNo`:連續小寫的字元總數
`alternating_len`: 目前交錯的字串長度
`longest`: 最長交錯的子字串長度，初始值為0
'''
isPreLower = None
upperNo = 0
lowerNo = 0
alternating_len = 0
longest = 0

# 處理字串第一個字元
# 如果第一個字是大寫字母
if strings[0].isupper() == True:
	isPreLower = False
	upperNo = 1
	if k==1:
		alternating_len = 1
		longest = 1
		
# 如果第一個字是小寫字母
else:
	isPreLower = True
	lowerNo= 1
	if k==1:
		alternating_len = 1
		longest = 1

# 處理字串第二個以後的字元
for i in range(1, len(strings)):
	# 前一個字元是大寫，目前字元是大寫
	if (isPreLower == False and strings[i].isupper() == True):
		upperNo += 1
		lowerNo = 0
		if upperNo == k:
			alternating_len += k
			longest = max(alternating_len, longest)
		#當連續大寫的字元總數大於k，超過的部分不列入計算
		if upperNo > k:
			alternating_len = k
			
	# 前一個字元是小寫，目前字元是大寫
	elif (isPreLower == True and strings[i].isupper() == True):
		if lowerNo < k:
			alternating_len = 0
		upperNo = 1
		lowerNo = 0
		#當連續大寫的字元總數大於k，超過的部分不列入計算
		if k == 1:
			alternating_len += 1
			longest = max(alternating_len, longest)
		isPreLower = False
			
	# 前一個字元是小寫，目前字元是小寫
	elif (isPreLower == True and strings[i].islower() == True):
		upperNo = 0
		lowerNo += 1
		if lowerNo == k:
			alternating_len += k
			longest = max(alternating_len, longest)
		if lowerNo > k:
			alternating_len = k

	# 前一個字元是大寫，目前字元是小寫
	elif (isPreLower == False and strings[i].islower() == True):
		#當連續大寫的字元總數小於k，目前交錯字串長度數值歸零
		if upperNo < k:
			alternating_len = 0
		upperNo = 0
		lowerNo = 1
		if k == 1:
			alternating_len += 1
			longest = max(alternating_len, longest)
		isPreLower = True
		
print(f"{longest}")

:::

### 3. 樹狀圖分析
:::info
**本題演算法設計參考如下：**
1. 請使用者輸入，讀取Node數量
2. 請使用者輸入，每個節點有幾個child、child編號
3. 計算每個Node的最大高度（深度）
4. 最大高度者的Node，即為Root，印出該Node編號
5. 印出Root的最大高度
:::

::: spoiler 參考程式碼

global root			  #根節點編號
global sum_of_highest #高度的總和
global max_height	  #最大高度

root = 0
sum_of_highest = 0
max_height = 0

def node_height(data, no):
	height = 0
	if data[no-1][1] ==	0:
		return 0
	else:
		for i in range(2, data[no-1][1]+2):
			temp = node_height(data, data[no-1][i])+1
			height = max(temp, height)
		return height

n = int(input(''))
data = []*100
for i in range(n):
	subnode = input().split()
	num_of_child = int(subnode[0])
	row = []
	row.append(i+1)				#列編號
	row.append(num_of_child)	#每列Child數量
	
	if num_of_child > 0:
		for j in range(2, num_of_child+2):
			row.append(int(subnode[j-1]))
	data.append(row)

for i in range(1 ,n+1):
	height = node_height(data, i)
	if height > max_height:
		max_height = height
		root = i
	sum_of_highest += height

print(root)
print(sum_of_highest)
		

:::

### 4. 物品堆疊


::: info
**本題演算法設計參考如下：**
1. 建立一個`list`，逐一加入物體資料
2. 將消耗能量由小到大排序
3. 計算各物體的消耗能量
4. 輸出最小能量消耗值
:::

::: spoiler 參考程式碼

items = []
mininum = 0
sum_of_weight = 0

n = int(input()) # sum of objects
weight = input().split()
frequency = input().split() #Count of use

for i in range(0, len(weight)):
    temp = []
    temp.append(int(weight[i]))
    temp.append(int(frequency[i]))
    items.append(temp)

for i in range(n-1):
    for j in range(n-1-i):
        if items[j][0]*items[j+1][1] > items[j+1][0]*items[j][1]:
	    items[j], items[j+1] = items[j+1], items[j]

for i in range(n-1):
    sum_of_weight += items[i][0]
    mininum += sum_of_weight * items[i+1][1]

print(mininum)
			

:::

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