tags: APCS

divideConquer

題目解析

這道題目要求在一個長度為 𝑛 的整數序列中,找出該序列中的最大值與最小值。題目特別要求使用分治法來解決這個問題。

解題方向

  • 分治法概念:
    • 分治法是一種算法設計範式,主要思想是將一個問題分成若干個子問題,對每個子問題進行求解,然後將子問題的解合併成整個問題的解。
    • 對於本題,我們可以將數列分成兩半,分別找到兩半中的最大值和最小值,然後將這兩個部分的最大最小值進行比較,從而得到整個數列的最大值和最小值。
  • 步驟:
    • 將數列不斷分割成左右兩部分,直到每部分只剩一個元素,此時最大值和最小值都為該元素本身。
    • 對每個分割後的部分,遞迴地求解其最大值和最小值。
    • 最後將左右兩部分的最大最小值進行比較,得出整個數列的最大最小值。

程式解析

程式中,我們定義了一個遞迴函數 search(arr, s, e)``,其中 arr 是輸入的整數序列,se` 分別代表序列的起始和結束位置(不包含結束位置)。

  • 基礎條件:
    • 當序列只有一個元素時,直接返回該元素作為最大值和最小值。
  • 遞迴分割:
    • 將序列分成左右兩部分,分別對左右兩部分遞迴求解最大最小值。
  • 合併結果:
    • 合併左右兩部分的結果,找出最小值和最大值。

完整程式碼

import sys def search(arr, s, e): # 基礎條件:序列只有一個元素 if s + 1 == e: return arr[s], arr[s] # 計算中間位置 m = (s + e) // 2 # 分別遞迴求解左右兩部分的最大最小值 left_min, left_max = search(arr, s, m) right_min, right_max = search(arr, m, e) # 當往上回傳時: # 合併結果,找出整個序列的最小值和最大值 return min(left_min, right_min), max(left_max, right_max) for s in sys.stdin: data = list(map(int, s.split())) result_min, result_max = search(data, 0, len(data)) print(result_min, result_max)