月球乘法和 Recamán 序列是相對少見的數學計算方法，理解其運算規則對於特定領域的開發至關重要。Van Eck 序列和費氏數列則較為常見，但在特定條件下的變形應用，例如非連續費氏數列和斐波那契字串，則需要更深入的理解和實作技巧。本文提供的 Python 函式，能有效處理這些特殊數學問題，並提供清晰的程式碼解析，有助於讀者快速理解和應用。對於需要處理大量數值計算或字串操作的場景，這些演算法能提供高效的解決方案。
3.22 月球乘法（Lunar Multiplication）問題解析與實作
月球乘法是一種特殊的運算規則，其中兩個數字的乘法結果等於它們的最小值，加法結果等於它們的最大值。本文將介紹如何實作一個函式，接受兩個 n 位整數 a 和 b，並傳回它們的月球乘法結果。
演算法解析
月球乘法的演算法相對簡單，主要步驟如下：
- 將輸入的兩個數字 a 和 b 轉換為字串並反轉，以便從最低位數字開始運算。
- 對 b 的每個數字，與 a 的對應數字進行月球乘法（取最小值），並將結果存入一個列表中。
- 使用月球加法（取最大值）將列表中的結果累加，得到最終結果。
程式碼實作
def multiply_by_lunar(a, b):
'''
月球乘法函式
'''
def add_in_lunar(x, y):
'''
月球加法輔助函式
'''
x_reversed = str(x)[::-1]
y_reversed = str(y)[::-1]
sum_reversed = ''
max_len = max(len(x_reversed), len(y_reversed))
for i in range(max_len):
sum_reversed += max(x_reversed[i:i+1], y_reversed[i:i+1]) if i < len(x_reversed) and i < len(y_reversed) else (x_reversed[i:i+1] if i < len(x_reversed) else y_reversed[i:i+1])
return int(sum_reversed[::-1])
a_reversed = str(a)[::-1]
b_reversed = str(b)[::-1]
numbers = []
answer = 0
for i in range(len(b_reversed)):
d = ''
for j in range(len(a_reversed)):
d += min(a_reversed[j], b_reversed[i])
numbers.append('0' * i + d)
for num in numbers:
answer = add_in_lunar(answer, int(num))
return answer
程式碼解析：
add_in_lunar函式：實作月球加法，接受兩個數字 x 和 y，將它們反轉後逐位比較，取最大值累加。multiply_by_lunar函式：首先將輸入的 a 和 b 反轉，然後對 b 的每個數字進行月球乘法，將結果存入numbers列表。- 使用
add_in_lunar將numbers中的結果進行月球加法累加，得到最終結果。
測試範例
| a | b | Expected Output | |
-|
-|
–| | 10 | 21 | 110 | | 170 | 76 | 1760 | | 45 | 96 | 455 | | 8 | 7 | 7 |
Recamán 序列的第 n 項計算
Recamán 序列是一種遞迴序列，其第 n 項的計算依賴於前面的項。本文將介紹如何實作一個函式，接受一個正整數 n，並傳回 Recamán 序列的第 n 項。
演算法解析
- 初始化序列的第一項為 0，並使用一個集合記錄已使用的元素。
- 從 1 到 n，迭代計算序列的下一項。如果
a_{n-1} - n為負數或已存在於序列中，則使用a_{n-1} + n作為下一項。 - 將計算出的下一項加入序列並標記為已使用。
程式碼實作
def Nth_term_of_recaman_sequence(n):
'''
計算 Recamán 序列的第 n 項
'''
seq = [0]
seen = {0}
for i in range(1, n+1):
prev = seq[-1]
next_term = prev - i
if next_term < 0 or next_term in seen:
next_term = prev + i
seq.append(next_term)
seen.add(next_term)
return seq[n]
程式碼解析：
- 初始化
seq為包含第一項 0 的列表，seen為包含 0 的集合。 - 在迴圈中計算
next_term，如果不符合條件則使用替代公式。 - 將
next_term新增到seq和seen中。
測試範例
| n | Expected Output | |
–|
–| | 17 | 25 | | 83 | 72 | | 919 | 756 | | 632 | 308 |
本章介紹了兩個有趣的數學問題及其 Python 解法，分別是月球乘法和 Recamán 序列的計算。這些問題展示了不同數學規則在程式設計中的應用，並提供了相應的程式碼範例和詳細解析。
3.24 Van Eck 序列
Van Eck 序列是一種由正整數構成的序列，第一項為 0。該序列的生成規則是：對於當前項，詢問在其之前是否出現過相同的數字。如果之前未出現過，則下一項為 0；如果之前出現過，則下一項為當前項與其前一次出現位置之間的距離。
演算法說明
- 初始化序列的第一項為 0。
- 建立一個字典來儲存序列中每個值的最新索引。
- 從索引 0 到 n-1 進行迭代：
- 取得序列中的前一項。
- 檢查前一項是否在字典中出現過。
- 如果出現過，計算當前索引與前一次索引的差值，並將差值加入序列中。
- 如果未出現過，將 0 加入序列中。
- 更新字典中前一項的最新索引。
- 傳回序列的第 n 項，即
sequence[n-1]。
Python 程式碼實作
def find_nth_term_in_van_eck_sequence(n):
"""
傳回 Van Eck 序列的第 n 項。
"""
# 初始化序列和字典
sequence = [0]
value_to_latest_index = {}
for i in range(n):
# 取得前一項
previous_value = sequence[i]
if previous_value in value_to_latest_index:
# 計算差值
difference = i - value_to_latest_index[previous_value]
sequence.append(difference)
else:
# 未出現過，加入 0
sequence.append(0)
# 更新字典
value_to_latest_index[previous_value] = i
# 傳回第 n 項
return sequence[-1]
程式碼解析：
- 初始化序列和字典：首先，初始化 Van Eck 序列的第一項為 0，並建立一個空字典
value_to_latest_index用於儲存每個值的最新索引。 - 迭代生成序列：透過迴圈，從索引 0 到 n-1 生成 Van Eck 序列。在每次迭代中，檢查前一項是否在字典中出現過，並根據結果計算下一項的值。
- 更新字典：每次迭代結束後，更新字典中前一項的最新索引，以便後續查詢。
- 傳回結果：最終傳回生成的 Van Eck 序列的第 n 項。
測試範例
根據給定的輸入範例，測試 find_nth_term_in_van_eck_sequence 函式：
n = 258，預期輸出：3n = 25，預期輸出：4n = 2，預期輸出：1n = 2089，預期輸出：0
這些測試範例驗證了函式的正確性。
3.25 非連續費氏數列
根據 Zeckendorf 定理，任何正整數都可以唯一地表示為若干個非連續費氏數的總和。任務是編寫一個函式，輸入一個正整數 n，傳回一個由非連續費氏數構成的列表，使得這些數字的總和等於 n，並且列表中的數字按降序排列。
演算法說明
- 生成費氏數列，直到生成的費氏數大於輸入的正整數 n 為止。
- 將生成的費氏數列按降序排序。
- 從排序後的費氏數列中選取非連續的費氏數，使得它們的總和等於 n。
Python 程式碼實作
def sort_desc(arr):
"""
將陣列按降序排序。
"""
for i in range(1, len(arr)):
curr = arr[i]
j = i - 1
while j >= 0 and curr > arr[j]:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = curr
return arr
def get_non_consecutive_fibonacci_numbers_summing_to_n(n):
"""
傳回總和為 n 的非連續費氏數列表。
"""
prev = 0
curr = 1
fib_nums = [prev, curr]
selected_fib_nums = []
curr_sum = prev + curr
# 生成費氏數列
while curr_sum <= n:
fib_nums.append(curr_sum)
prev, curr = curr, curr + prev
curr_sum = prev + curr
# 按降序排序費氏數列
fib_nums = sort_desc(fib_nums)
sum_of_fib_nums = 0
for num in fib_nums:
if sum_of_fib_nums + num <= n:
selected_fib_nums.append(num)
sum_of_fib_nums += num
return selected_fib_nums
程式碼解析：
- 生成費氏數列：首先，初始化兩個變數
prev和curr分別為 0 和 1，然後進入迴圈，不斷生成新的費氏數，直到生成的費氏數大於 n 為止。 - 排序費氏數列：使用插入排序法將生成的費氏數列按降序排列。
- 選取非連續費氏數：遍歷排序後的費氏數列，將滿足條件（即當前總和加上該費氏數不大於 n）的費氏數加入結果列表中，並更新總和。
測試範例
根據給定的輸入範例，測試 get_non_consecutive_fibonacci_numbers_summing_to_n 函式：
n = 53，預期輸出：[34, 13, 5, 1]n = 25，預期輸出：[21, 3, 1]n = 31，預期輸出：[21, 8, 2]n = 3009，預期輸出：[2584, 377, 34, 13, 1]
這些測試範例驗證了函式的正確性。
斐波那契字串的第 k 個字元
斐波那契字串是一種類別似於普通斐波那契數列的序列，但不同之處在於，它不是將前兩個數字相加，而是將它們連線起來。該序列的第一項是 0，第二項是 01（作為字串）。每個後續項都是透過連線前兩個項獲得的。例如，第三項是透過連線第一項和第二項獲得的，結果是 010。類別似地，第四項是透過連線第二項和第三項獲得的，結果是 01001，依此類別推。本挑戰需要一個函式，該函式接受輸入整數 k，並傳回斐波那契字串的第 k 個字元，其中序列是由字元 0 和 1 組成的字串。
演算法
直接生成序列直到第 k 個位置並提取該元素是一種簡單的方法。然而，這種方法會導致時間和空間複雜度增加。為了找到第 k 個字元，使用了公式 3.8 和 3.9，其中 phi 表示黃金比例。
程式碼實作
import decimal
def sqrt(num):
decimal.getcontext().prec = 165
return decimal.Decimal(num).sqrt()
def floor(x):
return int(x - 1) if x < 0 else int(x)
def fibonacci_word(k):
# 計算黃金比例
root_5 = sqrt(5)
phi = (1 + root_5) / 2
x = floor((k + 2) * phi / (1 + (phi * 2)))
y = floor((k + 1) * phi / (1 + (phi * 2)))
# 傳回第 k 個字元
return '0' if x - y == 0 else '1'
程式碼解密：
import decimal: 匯入decimal模組，用於進行高精確度的十進位制運算。sqrt(num)函式: 用於計算一個數字的平方根，並設定精確度為 165 位，以確保計算黃金比例時的準確性。floor(x)函式: 用於對數字進行向下取整，處理正負數的情況。fibonacci_word(k)函式:- 首先計算黃金比例
phi。 - 然後使用公式計算
x和y的值，這些值與斐波那契字串的第 k 個字元相關。 - 最後根據
x - y的值傳回第 k 個字元（0 或 1）。
- 首先計算黃金比例
二維網格中最多的點在一條線上
給定一個二維整數網格上的點列表，寫一個函式，傳回在同一條線上的最多點數。
演算法
該演算法接受一個二維整數網格點的列表作為輸入，並傳回透過這些點的直線上的最大點數。首先檢查輸入列表的長度是否小於 3，如果是，則傳回列表的長度。否則，遍歷列表中的每一對不同的點，計算透過這些點的直線的斜率，並使用字典跟蹤每個斜率的頻率。同時跟蹤重複點的數量。最後，透過將當前最大點數與重複點數相加，並與前一個最大值比較，傳回直線上的最大點數。
程式碼實作
def calculate_gcd(a, b):
'''
計算兩個整數 a 和 b 的最大公約數
'''
while b != 0:
a, b = b, a % b
return a
def count_points_on_line(points):
n = len(points)
# 如果點少於三個，它們總是在一條線上
if n < 3:
return n
max_points_on_line = 0
i = 0
while i < n:
slope_count = {} # 用於跟蹤斜率及其頻率的字典
num_duplicates = 1
cur_max_points_on_line = 0
j = i + 1
# 與其他點比較以計算斜率
while j < n:
if points[i] == points[j]:
num_duplicates += 1
else:
dx = points[j][0] - points[i][0]
dy = points[j][1] - points[i][1]
if dx == 0:
slope = float('inf') # 使用無窮大表示垂直線
else:
gcd = calculate_gcd(dy, dx)
slope = (dy // gcd, dx // gcd) # 簡化斜率
slope_count[slope] = slope_count.get(slope, 0) + 1
cur_max_points_on_line = max(cur_max_points_on_line, slope_count[slope])
j += 1
max_points_on_line = max(max_points_on_line, cur_max_points_on_line + num_duplicates)
i += 1
return max_points_on_line
程式碼解密：
calculate_gcd(a, b)函式: 用於計算兩個整數的最大公約數，用於簡化斜率。count_points_on_line(points)函式:- 首先檢查點的數量是否少於 3，如果是，直接傳回點的數量。
- 使用雙重迴圈遍歷每一對點，計算它們之間的斜率，並統計每個斜率出現的頻率。
- 使用字典
slope_count跟蹤斜率及其頻率，並更新當前最大點數cur_max_points_on_line。 - 同時統計重複點的數量
num_duplicates。 - 最後更新全域性最大點數
max_points_on_line，並傳回結果。
