在 Python 開發中，演算法設計與程式碼實作至關重要。本文將探討一系列演算法，涵蓋數字處理、陣列操作、序列生成以及數學運算等方面，提供實用的 Python 程式碼範例，並輔以圖表和詳細解析，幫助讀者理解演算法的內部運作機制和應用場景。這些演算法涵蓋了常見的程式設計需求，例如計算獎勵分數、搜尋特定元素、生成數列以及最佳化數學運算等，對於提升程式碼效率和解決實際問題具有重要意義。
4.7 重複數字的獎勵計算
在這個挑戰中，我們需要計算一個整數中重複數字的獎勵分數。獎勵規則是根據連續重複的數字數量來計算的。
演算法
演算法透過遍歷整數的每個數字，並檢查它是否與前一個數字相同。如果相同，則增加重複計數；如果不同，則根據之前的重複計數計算獎勵分數，並重置計數。
程式碼實作
def calculate_score(n):
score = 0
count = 1
prev_digit = str(n)[0]
for digit in str(n)[1:]:
if prev_digit == digit:
count += 1
else:
if count > 1:
score += 10 ** (count - 2)
count = 1
prev_digit = digit
if count > 1:
score += 2 * 10 ** (count - 2)
return score
內容解密：
- 初始化
score為 0，用於儲存最終的獎勵分數。 - 初始化
count為 1，用於記錄當前數字的重複次數。 - 將整數
n轉換為字串，以便逐位檢查。 - 遍歷
n的每個數字，並與前一個數字比較。如果相同，則增加count；如果不同，則檢查count是否大於 1，如果是，則根據count計算獎勵分數，並重置count為 1。 - 在迴圈結束後，再次檢查最後一個數字的
count，如果大於 1，則計算獎勵分數，但此次獎勵分數需要加倍。 - 傳回最終的獎勵分數
score。
4.8 最近的第一個較小數字
給定一個正整數陣列，任務是為每個數字找到陣列中最近的第一個較小數字。如果沒有較小的數字，則保持原數字不變。
演算法
演算法使用巢狀迴圈遍歷輸入陣列的每個元素及其周圍元素。它透過比較當前元素與其左右兩側的元素來找到最近的第一個較小元素。如果左側或右側的元素較小，則選擇兩者中較小的那一個。同時，處理了當前元素沒有左側或右側元素的情況，將缺失的元素設為當前元素本身。
程式碼實作
def Nearest_first_smaller_number(array):
n = len(array)
nearest_smaller = []
for x, current_element in enumerate(array):
for y in range(1, n):
if x >= y:
left = array[x - y]
else:
left = current_element
if x + y < n:
right = array[x + y]
else:
right = current_element
if left < current_element or right < current_element:
nearest_smaller.append(left if left < right else right)
break
else:
nearest_smaller.append(current_element)
return nearest_smaller
內容解密：
- 初始化一個空列表
nearest_smaller用於儲存結果。 - 使用
enumerate遍歷輸入陣列array的每個元素及其索引。 - 對每個元素，使用巢狀迴圈檢查其左右兩側的元素，尋找第一個較小的元素。
- 如果找到較小的元素（無論是左側還是右側），則將其新增到
nearest_smaller中，並跳出內層迴圈。 - 如果在左右兩側都沒有找到較小的元素，則將當前元素本身新增到
nearest_smaller中。 - 傳回結果列表
nearest_smaller。
4.9 第一個被 K 個較小數字前置的元素
給定一個物件列表，任務是找出並傳回第一個被至少 K 個較小物件前置的元素。如果不存在這樣的元素，則傳回 None。
演算法
演算法遍歷列表中的每個元素，並檢查其前面是否有至少 K 個較小的元素。透過列表推導式建立一個子列表，包含當前元素之前的所有較小元素。然後檢查這個子列表的長度是否大於或等於 K。如果是，則傳回當前元素作為結果。如果遍歷完所有元素仍未找到符合條件的元素，則傳回 None。
程式碼實作
def first_preceded_by_k_smaller_number(items, k=1):
for index, item in enumerate(items):
smaller_items = [i for i in items[:index] if i < item]
if len(smaller_items) >= k:
return item
return None
內容解密：
- 使用
enumerate遍歷輸入列表items的每個元素及其索引。 - 對每個元素，使用列表推導式建立一個子列表
smaller_items，包含當前元素之前的所有較小元素。 - 檢查
smaller_items的長度是否大於或等於 K。如果是，則傳回當前元素作為結果。 - 如果遍歷完所有元素仍未找到符合條件的元素，則傳回 None。
4.10 Calkin-Wilf 序列的第 n 項
Calkin-Wilf 樹是一種根二元樹，其頂點與正有理數一一對應。樹的根對應於數字 1，對於任何有理數 a/b，其左子對應於數字 a/(a+b)，右子對應於數字 (a+b)/b。每個有理數在樹中恰好出現一次。當對 Calkin-Wilf 樹進行層序遍歷時，會產生一個有理數序列，稱為 Calkin-Wilf 序列。我們希望定義一個函式，接受一個正整數 n 作為輸入，並傳回 Calkin-Wilf 序列的第 n 項，即一個有理數。
演算法
該演算法使用廣度優先搜尋（BFS），這是一種圖遍歷演算法，用於生成 Calkin-Wilf 序列直到第 n 項。佇列資料結構用於儲存序列的二元樹表示的節點。該演算法透過計算當前節點的左右子節點並將它們新增到佇列中來生成序列中的每個項。最後，傳回序列的第 n 項。
Python 程式碼實作
def nth_term_calkin_wilf(n):
# 檢查佇列是否為空的函式
def is_empty(q):
return len(q) == 0
# 將專案新增到佇列的函式
def enqueue(q, item):
q.append(item)
return q
# 從佇列中移除專案的函式
def dequeue(q):
if not is_empty(q):
return q.pop(0)
# 初始化佇列與根節點 (1/1) 並將 n 減 1
n -= 1
queue = []
queue = enqueue(queue, (1, 1))
# 使用 BFS 生成 Calkin-Wilf 序列直到第 n 項
for _ in range(n):
# 從佇列中取出下一個節點
parent_num, parent_denom = dequeue(queue)
# 計算當前節點的左右子節點
left_child_num = parent_num
left_child_denom = parent_num + parent_denom
right_child_num = parent_num + parent_denom
right_child_denom = parent_denom
# 將左右子節點加入佇列
queue = enqueue(queue, (left_child_num, left_child_denom))
queue = enqueue(queue, (right_child_num, right_child_denom))
# 從佇列中取出最終節點
final_num, final_denom = dequeue(queue)
# 傳回 Calkin-Wilf 序列的第 n 項
if final_denom == 1:
return final_num
else:
return str(final_num) + '/' + str(final_denom)
程式碼解析：
is_empty、enqueue和dequeue函式：這些輔助函式用於操作佇列，分別檢查佇列是否為空、將元素加入佇列和從佇列中取出元素。- 初始化佇列：首先將根節點
(1, 1)（對應於有理數 1/1）加入佇列，並將輸入n減 1。 - BFS 主迴圈：重複
n次，每次從佇列中取出一個節點，計算其左右子節點，並將它們加入佇列。 - 傳回第 n 項：最後從佇列中取出一個節點，並根據其分母是否為 1 傳回適當格式的結果。
範例應用
若輸入 n = 10，輸出為 3/5，因為 Calkin-Wilf 序列的第 10 項是有理數 3/5。
4.11 反轉遞增子陣列
給定一個正整數陣列，任務是找到遞增子陣列的反轉。每個子序列必須是嚴格遞增的。
範例
對於輸入 [5, 7, 220, 33, 2, 6, 8, 1, 45]，輸出反轉遞增子陣列後的結果：[220, 7, 5, 33, 8, 6, 2, 45, 1]。
Python 程式碼實作
def reverse_ascending_subarrays(List_Numbers):
# 建立一個空串列來儲存遞增子串列
result = []
i = 0
while i < len(List_Numbers):
j = i + 1
# 向右掃描直到找到非遞增元素
while j < len(List_Numbers) and List_Numbers[j] > List_Numbers[j-1]:
j += 1
# 反轉當前遞增子串列並新增到結果中
result.extend(List_Numbers[i:j][::-1])
i = j
return result
程式碼解析：
- 雙指標技術：使用兩個指標
i和j，其中i用於指向子串列的起始位置，而j用於找到遞增子串列的結束位置。 - 反轉子串列：使用 Python 的切片和反轉功能
[::-1]將每個遞增子串列反轉。 - 合併結果：將反轉的子串列新增到最終結果串列中。
此演算法有效地識別輸入陣列中的所有遞增子陣列，將它們反轉，並按原始順序合併結果。
小整數冪次運算的最佳化實務
在進行大整數冪次運算時，無論是在時間還是記憶體方面，都會面臨巨大的挑戰。本章節將探討如何找到最小的正整數$x$和$y$，使得$a^x$和$b^y$在指定的容忍度內相互接近。這裡的「容忍度」定義了$a^x$和$b^y$之間的最大可接受差異。
演算法設計與實作
為瞭解決這個問題，我們採用貪婪演算法。該演算法的核心思想是透過迭代增加$x$和$y$的值，同時利用重複乘法來增加$a$和$b$的冪次，直到兩個冪次之間的差異小於或等於指定的容忍度。雖然這種方法不總能保證最優解，但在合理的效率下，它能夠找到一個相當好的解。
程式碼實作
def smallest_integer_powers(a, b, tolerance=100):
x, y = 1, 1
a_pow, b_pow = a, b
while True:
if a_pow > b_pow:
if tolerance <= b_pow / (a_pow - b_pow):
return x, y
y += 1
b_pow *= b
elif a_pow < b_pow:
if tolerance <= a_pow / (b_pow - a_pow):
return x, y
x += 1
a_pow *= a
else:
return x, y
內容解密：
- 初始化變數：
x和y分別初始化為1，代表$a$和$b$的初始指數。a_pow和b_pow分別初始化為$a$和$b$，代表$a^x和$b^y的初始值。 - 進入無限迴圈：迴圈持續進行，直到滿足特定的終止條件。
- 比較
a_pow和b_pow：根據a_pow和b_pow的大小關係，決定是增加x還是y，並更新對應的冪次值。 - 檢查容忍度條件：如果當前冪次差異在容忍度範圍內，則傳回當前的
x和y。 - 更新冪次值：根據比較結果，更新
a_pow或b_pow，並遞增對應的指數。
圖表說明
@startuml
skinparam backgroundColor #FEFEFE
skinparam componentStyle rectangle
title Python程式碼演算法設計與實作
package "資料視覺化流程" {
package "資料準備" {
component [資料載入] as load
component [資料清洗] as clean
component [資料轉換] as transform
}
package "圖表類型" {
component [折線圖 Line] as line
component [長條圖 Bar] as bar
component [散佈圖 Scatter] as scatter
component [熱力圖 Heatmap] as heatmap
}
package "美化輸出" {
component [樣式設定] as style
component [標籤註解] as label
component [匯出儲存] as export
}
}
load --> clean --> transform
transform --> line
transform --> bar
transform --> scatter
transform --> heatmap
line --> style --> export
bar --> label --> export
note right of scatter
探索變數關係
發現異常值
end note
@enduml此圖示呈現了演算法的核心邏輯流程，從初始化到比較、更新，最終傳回結果的整個過程。
嚴格遞增序列檢查演算法
演算法概述
本演算法旨在檢查給定的列表元素是否嚴格按照遞增順序排列。嚴格遞增意味著列表中不能包含重複的元素。演算法透過遍歷列表並比較相鄰元素來實作這一目標。
演算法步驟
- 初始化: 設定一個標誌變數（如
is_strictly_ascending）為True，假設列表是嚴格遞增的。 - 遍歷列表: 從列表的第一個元素開始，遍歷到倒數第二個元素。
- 比較相鄰元素: 對於每個元素，比較它與下一個元素的大小。如果當前元素大於或等於下一個元素，則將
is_strictly_ascending設定為False並離開迴圈。 - 傳回結果: 遍歷完成後，傳回
is_strictly_ascending的值。如果列表是嚴格遞增的，則傳回True；否則，傳回False。
Python 實作
def is_strictly_ascending(lst):
"""
檢查列表是否嚴格遞增。
Args:
lst (list): 要檢查的列表。
Returns:
bool: 如果列表嚴格遞增，則傳回 True；否則，傳回 False。
"""
is_strictly_ascending = True
for i in range(len(lst) - 1):
if lst[i] >= lst[i + 1]:
is_strictly_ascending = False
break
return is_strictly_ascending
內容解密：
- 函式
is_strictly_ascending接受一個列表lst作為輸入，並初始化一個布林變數is_strictly_ascending為True。 - 迴圈遍歷列表中的每個元素（除了最後一個），並比較當前元素與下一個元素的大小。
- 如果發現任何一對相鄰元素不符合嚴格遞增的條件（即當前元素大於或等於下一個元素），則將
is_strictly_ascending設定為False並離開迴圈。 - 最終傳回
is_strictly_ascending的值，指示列表是否嚴格遞增。
時間複雜度
該演算法的時間複雜度為 O(n)，其中 n 是列表中的元素數量。這是因為在最壞的情況下，演算法需要遍歷整個列表一次。
應用場景
此演算法可用於需要檢查序列是否嚴格遞增的各種場景，例如資料驗證、排序演算法的正確性檢查等。
