APCS實作題分析

作答策略:

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

105年3月

1. 成績指標

難度: :star:
單元範圍:容器資料型別 資料排序 控制流程:判斷條件

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 請使用者輸入學生人數,定義成績list的長度
  2. 請使用者輸入成績,以成績list儲存
  3. 呼叫sort()進行成績list排序,並且依序將元素印出
  4. 條件判斷:
    • 檢查最低成績是否及格,如果是,表示全部都及格
      • 輸出best case
      • 印出最低及格者成績
      • 結束迴圈
    • 或者,檢查最高成績是否不及格,如果是,表示全部人都不及格
      • 印出最高不及格者成績
      • 印出worst case
      • 結束迴圈
    • 其他情況
      • 掃描成績list,找出最高不及格者
      • 掃描成績list,找出最低及格者
      • 結束迴圈
參考程式碼
#請使用者輸入學生人數,定義成績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. 矩陣轉換

矩陣 容器資料型別 控制流程:迴圈 函式

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 設計function: 旋轉矩陣
    • 使用臨時的陣列儲存旋轉過程
  2. 設計function: 翻轉矩陣
    • 使用臨時的陣列儲存翻轉過程
  3. 讓使用者輸入三個數字
    • 矩陣列數
    • 矩陣行數
    • 矩陣操作步驟數量
  4. 讓使用者輸入矩陣內容
    • 每列的值
  5. 讓使用者依序輸入操作代號,但是倒過來執行
    • 根據操作動作代號呼叫function(0:旋轉, 1:翻轉)
  6. 輸出原始矩陣內容
參考程式碼
# 設計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. 線段覆蓋長度

函式與遞迴

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 宣告兩個list,分別儲存兩個線段資訊,用True,False紀錄
  2. 設計一個function,標記線段資訊
  3. 請使用者輸入線段數量
  4. 請使用者根據線段數量,依序輸入起點、終點座標值,用空格隔開
  5. 呼叫function,標記線段
  6. 利用while迴圈找出各列索引為True的數量,輸出總覆蓋的長度
參考程式碼
# 宣告兩個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. 血緣關係

資料結構 函式與遞迴

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 宣告一個List,紀錄每個成員的child
  2. 宣告以下變數
    • 紀錄最長血緣距離
    • 紀錄每個成員是否為其他人的小孩
    • 紀錄每個成員有多少小孩
  3. 設計一個function,計算從該node出發的最大深度,也就是與該成員的最長血緣距離
    • 如果該成員沒有child,回傳血緣距離為0
    • 如果該成員有一個child,遞迴呼叫往下找,回傳血緣距離
    • 如果該成員有兩個以上child,遞迴呼叫往下找,各自得到最長的血緣距離後比較,回傳較長血緣距離
  4. 使用者輸入家族成員總數
  5. 使用者輸入各node的親子關係
  6. 找到root
  7. 呼叫function,計算根節點的最大深度
  8. 與目前最長血緣深度比較,取較大值印出
參考程式碼
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. 三角形辨別

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 請使用者輸入三個線段長度
  2. 從小到大依序排列三個線段
  3. 判斷以下條件:
    • a2 + b2 < c2:輸出銳角三角形
    • a2 + b2 = c2:輸出直角三角形
    • a2 + b2 > c2:輸出鈍角三角形
參考程式碼
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. 最大和

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 請使用者輸入數字
  2. 紀錄N群數字中,最大的數字
  3. 計算全部最大數字的加總
  4. 找出哪些最大數字,可以被整除加總
參考程式碼
# 請使用者輸入數字 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彈

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

環狀鏈結串列

本題演算法設計參考:

  1. 建立環狀鏈結串列,包括玩家號碼跟指標
  2. 紀錄爆炸次數,初始值為0
  3. 遊戲開始
    • 當累加器加到m次時,就從環狀串列中刪除這個號碼
    • 累加器歸零、總人數少1
    • 剩下一人時,輸出這位幸運者的號碼

可運用這個類別宣告技巧來建立環狀鏈結串列,參考《Python物件與類別》

參考程式碼
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. 棒球遊戲

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

本題演算法設計參考:

  1. 請使用者輸入每位打者打擊結果、目前局數
  2. 宣告變數紀錄每個打序的壘包推進、壘上狀態、出局數狀態
  3. 記錄每局的打序造成的壘包推進
    • 如果打擊結果為"FO"或"GO"或"SO",則紀錄為0
    • 如果打擊結果為"1B",則紀錄為1
    • 如果打擊結果為"2B",則紀錄為2
    • 如果打擊結果為"3B",則紀錄為3
    • 如果非以上結果,則為HR,紀錄為4
  4. 遊戲開始,帶入打擊結果與局數
    • 如果是三出局,壘上清空
    • 如果是全壘打,分數加上壘上人數、壘上清空
    • 如果是一壘安打
      • 如果三壘有人就加一分
      • 打者上一壘
    • 如果是二壘安打
      • 如果是二、三壘上有人就加一分
      • 如果一壘有人,就推進到三壘
      • 打者上二壘
    • 如果是三壘安打
      • 如果一、二、三壘有人就加一分
      • 打者上三壘
  5. 輸出目前局數的得分

106年3月

1. 秘密差

本題演算法設計參考:

  1. 使用list儲存使用者輸入的整數
  2. 判斷整數位數總長度是奇數還是偶數
    • 如果是奇數:把奇數位元跟偶數位元各自加總
    • 如果是偶數:把奇數位元跟偶數位元各自加總
  3. 把各自加總結果相減,取絕對值,輸出結果
參考程式碼
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. 小群體


流程控制:條件判斷

本題演算法設計參考:

  1. 建立團體
  2. 找到群體的源頭
  3. 繼續找沒有被拜訪的成員且不在其他小群體的人,找出其他小群體
參考程式碼
# 建立團體 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. 基地台

本題演算法設計參考:

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

106年10月

1. 邏輯運算子

2. 交錯字串

本題演算法設計參考如下:

  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
    • 根據這四種情況進行
      • 前一個字元是大寫,目前字元是大寫
      • 前一個字元是小寫,目前字元是大寫
      • 前一個字元是小寫,目前字元是小寫
      • 前一個字元是大寫,目前字元是小寫
參考程式碼
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. 樹狀圖分析


本題演算法設計參考如下:

  1. 請使用者輸入,讀取Node數量
  2. 請使用者輸入,每個節點有幾個child、child編號
  3. 計算每個Node的最大高度(深度)
  4. 最大高度者的Node,即為Root,印出該Node編號
  5. 印出Root的最大高度
參考程式碼
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. 物品堆疊

本題演算法設計參考如下:

  1. 建立一個list,逐一加入物體資料
  2. 將消耗能量由小到大排序
  3. 計算各物體的消耗能量
  4. 輸出最小能量消耗值
參考程式碼
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檢定應試指南