矩形切割正方形與Leibniz三角形計算

在幾何演算法中，矩形切割成正方形是一個常見問題，目標是找到最小切割次數。我們可以利用遞迴和動態規劃來解決這個問題，透過記錄已計算的結果來避免重複計算，並有效地探索所有可能的切割方案。Leibniz 三角形是數論中的一個有趣結構，與 Pascal 三角形類別似，但計算方式相反。透過遞迴計算，我們可以有效地取得三角形中任意位置的值。Collatz 猜想是一個著名的數學難題，我們可以利用廣度優先搜尋演算法計算從一個數字到另一個數字所需的 Collatz 距離，透過逐層探索數字的變換軌跡來找到目標數字。最後，三數之和問題在演算法設計中也相當常見，透過雙指標技術，我們可以在已排序的列表中高效地判斷是否存在三個數字的和等於目標值。

將矩形切割成正方形的最小切割次數

在處理矩形切割成正方形的問題時，我們需要考慮如何以最少的切割次數達成目標。給定一個矩形的長度 a 和寬度 b，我們的目標是計算出將其切割成正方形的最小切割次數。

演算法解析

1. 首先檢查矩形是否已經是正方形（即 a == b），如果是，則傳回 0，因為不需要進行任何切割。
2. 如果矩形的長或寬為 1，則傳回 max(a, b) - 1，因為在這種情況下，只能切割成一個正方形。
3. 使用一個字典 memo 來儲存已經計算過的結果，以避免重複計算。
4. 初始化答案為 (a - 1) * b，代表最大可能的切割次數。
5. 分別嘗試水平和垂直切割矩形，並遞迴計算切割後形成的兩個較小矩形的最小切割次數。
6. 對於每一次切割，計算總的切割次數（包括當前的切割），並更新答案如果找到更好的解決方案。
7. 將計算出的最小切割次數儲存到 memo 中，以供未來參考。

程式碼實作

def RectToSquares(a, b, memo={}):
    '''
    檢查給定的矩形是否已經是正方形
    '''
    if a == b:
        return 0

    if a == 1 or b == 1:
        return max(a, b) - 1

    key = (a, b)
    '''
    檢查是否已經計算過該輸入的答案
    '''
    if key in memo:
        return memo[key]

    '''
    初始化答案為最大可能的值
    '''
    answer = (a - 1) * b

    # 水平切割矩形
    for i in range(1, a // 2 + 1):
        '''
        遞迴計算兩個較小矩形的最小切割次數
        '''
        horizontal_cut = RectToSquares(a - i, b, memo)
        vertical_cut = RectToSquares(i, b, memo)
        total_cuts = horizontal_cut + vertical_cut + 1
        # 更新答案如果找到更好的解決方案
        answer = min(answer, total_cuts)

    # 垂直切割矩形
    for i in range(1, b // 2 + 1):
        '''
        遞迴計算兩個較小矩形的最小切割次數
        '''
        horizontal_cut = RectToSquares(a, i, memo)
        vertical_cut = RectToSquares(a, b - i, memo)
        total_cuts = horizontal_cut + vertical_cut + 1
        # 更新答案如果找到更好的解決方案
        answer = min(answer, total_cuts)

    # 將答案儲存到memo中
    memo[key] = answer
    return answer

內容解密：

1. RectToSquares函式：此函式負責計算將給定矩形切割成正方形的最小切割次數。它接受矩形的長度 a、寬度 b 以及一個用於儲存中間結果的字典 memo。
2. 基本情況處理：函式首先檢查矩形是否已經是正方形，或其長或寬是否為 1，並根據這些情況傳回相應的結果。
3. 使用memoization：透過儲存已經計算過的結果，避免了重複計算，從而提高了演算法的效率。
4. 初始化最大可能切割次數：將答案初始化為 (a - 1) * b，這代表了將矩形切割成單位正方形的最壞情況。
5. 水平和垂直切割嘗試：函式分別嘗試水平和垂直切割矩形，並遞迴計算由此產生的兩個較小矩形的最小切割次數。
6. 更新最小切割次數：對於每一次切割，函式計算總的切割次數，並在找到更優的解決方案時更新答案。
7. 結果儲存和傳回：最後，將計算出的最小切割次數儲存到 memo 中，並傳回該結果。

消除角落的最小點移除數

給定一組在二維整數網格上的點，定義一個「角落」是由三個點組成的特定結構。我們的任務是找出需要從給定點集中移除的最小點數，以消除所有角落。

演算法解析

1. 識別所有可能的角落結構。
2. 使用遞迴和memoization技術來找出移除最少點數以消除所有角落的方案。

程式碼實作

def MinCornerRemover(corners, memo):
    '''
    基本情況：如果角落列表為空，則不需要移除任何點
    '''
    if len(corners) == 0:
        return 0

    key = tuple(corners)
    '''
    檢查是否已經處理過當前的角落列表
    '''
    if key in memo:
        return memo[key]

    removals = len(corners)
    points_set = set()

    # 對每個角落進行處理
    for corner in corners:
        for point in corner:
            if point not in points_set:
                points_set.add(point)
                remaining_corners = [c for c in corners if point not in c]
                '''
                遞迴計算移除當前點後剩餘角落的最小移除點數
                '''
                removals = min(removals, 1 + MinCornerRemover(remaining_corners, memo))

    # 將結果儲存到memo中
    memo[key] = removals
    return removals

內容解密：

1. MinCornerRemover函式：此函式旨在找出從給定點集中移除的最小點數，以消除所有角落結構。
2. 基本情況：如果輸入的角落列表為空，則函式傳回 0，因為不需要移除任何點。
3. memoization技術：透過儲存已經處理過的角落列表的結果，避免了重複計算，提高了效率。
4. 遍歷所有角落和點：函式對每個角落中的每個點進行檢查，並遞迴計算移除該點後剩餘角落的最小移除點數。
5. 更新最小移除點數：在遍歷過程中，不斷更新最小移除點數，以確保最終傳回的是最優解。
6. 結果儲存：最後，將計算出的最小移除點數儲存到 memo 中，以供未來參考。

3.17 Leibniz 三角形

在 Pascal 三角形中，每個數字等於其上方兩個數字的總和，而在 Leibniz 三角形中，每個數字等於其下方兩個數字的總和。現在需要撰寫一個函式，輸入左側列的值，回傳最後一列指定位置的值。

演算法解析

Leibniz 三角形的計算過程如下：

1. 輸入兩個引數：LeftMost_Rows（代表 Leibniz 三角形左側列的值）和 positions（代表需要查詢的最後一列位置）。
2. 初始化一個空清單 result 來儲存查詢結果。
3. 初始化一個字典 memo 來儲存中間計算結果。
4. 使用提供的左側列值計算三角形的第一列，並將結果存入 memo。
5. 使用上一列的值計算三角形的剩餘值，每個值為下方兩個值的差。
6. 將計算結果存入 memo。
7. 從 memo 中取出最後一列的指定位置的值，並加入 result 清單。
8. 回傳 result 清單。

Python 程式碼實作

def Leibniz_triangle(LeftMost_Rows, positions):
    '''
    計算 Leibniz 三角形最後一列指定位置的值
    '''
    # 初始化儲存結果的清單
    result = []
    # 初始化儲存中間結果的字典
    memo = {}

    # 計算第一列的值並存入 memo
    for i in range(len(LeftMost_Rows)):
        memo[(i, 0)] = LeftMost_Rows[i]

    # 計算三角形的剩餘值
    for i in range(1, len(LeftMost_Rows)):
        for j in range(1, i + 1):
            # 每個值為上方值的差
            value = memo[(i - 1, j - 1)] - memo[(i, j - 1)]
            memo[(i, j)] = value

    # 取出最後一列指定位置的值
    last_row_index = len(LeftMost_Rows) - 1
    for pos in positions:
        if pos <= last_row_index:
            result.append(memo[(last_row_index, pos)])
        else:
            # 若位置超出範圍，處理錯誤或回傳特定值
            result.append(None)  # 或其他適當的錯誤處理

    return result

程式碼解析：

1. 初始化：建立 result 清單儲存結果，memo 字典儲存中間值。
2. 計算第一列：將輸入的左側列值存入 memo，對應索引 (i, 0)。
3. 遞迴計算三角形值：利用迴圈計算每個位置 (i, j) 的值，公式為 memo[(i - 1, j - 1)] - memo[(i, j - 1)]。
4. 取得最後一列的值：遍歷 positions，從 memo 取出對應的最後一列值並加入 result。
5. 回傳結果：最終回傳包含所有查詢結果的 result 清單。

使用範例

print(Leibniz_triangle([1, 2, 3], range(3)))  # [3, -1, 0]
print(Leibniz_triangle([4, 7, 9, 3], range(4)))  # [3, 6, -8, 7]
print(Leibniz_triangle([88, 90, 1, 0, 9], range(4)))  # [9, -9, 10, 78]
print(Leibniz_triangle([20, 95], range(2)))  # [95, -75]

結果分析：

• 正確輸出對應 Leibniz 三角形最後一列指定位置的值，符合預期結果。
• 正確處理了不同輸入長度和查詢位置的需求。

此實作完整展現了 Leibniz 三角形的計算邏輯與程式碼結構，能有效處理不同測試案例。

Collatzy Distance 問題與解法

問題描述

給定兩個正整數 start_num 和 goal_num，要求計算從 start_num 開始，透過 Collatz 猜想的公式（3*n + 1 和 n//2），到達 goal_num 所需的層數。

解法概述

使用廣度優先搜尋（BFS）演算法，從 start_num 開始逐層生成數字，直到找到 goal_num。每一層的數字都是透過對上一層的數字應用 Collatz 公式得到的。

演算法步驟

1. 初始化層數計數器 num_layers 為 0。
2. 將 start_num 作為第一層的初始數字，存入集合 curr_layer。
3. 當 goal_num 不在 curr_layer 中時，重複以下步驟：
   • 建立一個空集合 next_layer 用於存放下一層的數字。
   • 對 curr_layer 中的每個數字，計算其透過 Collatz 公式得到的兩個新數字（num//2 和 3*num + 1），並將它們加入 next_layer。
   • 將 curr_layer 更新為 next_layer。
   • 將 num_layers 加 1。
4. 當 goal_num 在 curr_layer 中時，傳回 num_layers。

Python 程式碼實作

def get_collatz_distance(start_num, goal_num):
    """
    計算從 start_num 到 goal_num 需要經過多少層 Collatz 序列。
    """
    num_layers = 0
    curr_layer = {start_num}
    
    while goal_num not in curr_layer:
        next_layer = set()
        for num in curr_layer:
            next_layer.update([num // 2, 3 * num + 1])
        curr_layer = next_layer
        num_layers += 1
    
    return num_layers

程式碼解析：

• 初始化層數計數器 num_layers 為 0，用於記錄到達 goal_num 需要的層數。
• 使用集合 curr_layer 儲存當前層的數字，初始時只包含 start_num。
• 在 while 迴圈中，不斷生成下一層數字，直到 goal_num 出現在當前層。
• 對當前層的每個數字，計算其透過 Collatz 公式得到的兩個新數字，並將它們加入下一層的集合中。
• 更新當前層為下一層，並將層數計數器加 1。
• 當 goal_num 被找到時，傳回累計的層數。

Sum of Two Squares 問題與解法

問題描述

給定一個正整數 n，要求找出兩個整數 a 和 b，使得 a^2 + b^2 = n。如果有多組解，傳回 a 最大的那一組解；如果無解，傳回 None。

解法概述

首先計算第一個數字的最大值為 (n/2)^0.5，然後遍歷可能的第二個數字（從 1 到第一個數字的最大值），檢查是否存在一對數字使得其平方和等於 n。

演算法步驟

1. 計算第一個數字的最大值。
2. 遍歷可能的第二個數字。
3. 對每個第二個數字，計算其平方與 n 的差值。
4. 檢查差值是否為某個數字的平方。
5. 如果是，傳回這對數字；否則繼續檢查下一個可能的第二個數字。
6. 如果遍歷完所有可能的第二個數字仍未找到解，傳回 None。

Python 程式碼實作

import math

def get_squares_summing_to_n(n):
    """
    找出兩個整數的平方和等於給定數字 n 的最大可能組合。
    """
    max_first_base = int(math.sqrt(n / 2))
    for second_base in range(1, max_first_base + 1):
        diff = n - second_base ** 2
        first_base = int(math.sqrt(diff))
        if first_base ** 2 == diff:
            return (first_base, second_base)
    return None

程式碼解析：

• 首先計算第一個數字的最大值，以限制搜尋範圍。
• 對每個可能的第二個數字，計算其平方與 n 的差值，並檢查差值是否為完全平方數。
• 如果找到一對數字使得其平方和等於 n，傳回這對數字。
• 使用整數平方根運算以提高效率，並避免浮點數運算可能帶來的誤差。

三數之和問題（Three Sum Problem）解析與實作

三數之和問題旨在判斷在一個已排序的正整數列表中，是否存在三個數字的和恰好等於給定的目標數字。本文將詳細解析該問題的演算法設計與 Python 實作，並探討其背後的邏輯與最佳化方法。

問題描述

給定一個已排序的正整數列表 numbers_list 和一個目標數字 goal，要求編寫一個函式 has_three_summers，若列表中存在三個數字使得其和等於 goal，則傳回 True，否則傳回 False。

演算法設計

為瞭解決三數之和問題，我們採用了一個高效的演算法，該演算法結合了遍歷列表和雙指標技術（Two Pointer Technique）。具體步驟如下：

1. 檢查列表長度：首先檢查輸入列表 numbers_list 的長度是否小於 3，若是，則直接傳回 False，因為不可能找到三個數字滿足條件。
2. 遍歷列表：逐一遍歷列表中的每個數字 x，並計算新的目標數字 new_goal = goal - x。
3. 雙指標技術：呼叫輔助函式 has_two_sum 來檢查剩餘列表（即 numbers_list[i+1:]）中是否存在兩個數字的和等於 new_goal。has_two_sum 函式採用雙指標技術，從列表的兩端開始向中間靠攏，以高效地尋找滿足條件的數字對。
   • 初始化兩個指標：start 指向列表起始位置，end 指向列表末尾。
   • 計算 start 和 end 所指數字的和 two_sum。
     • 若 two_sum 等於 new_goal，傳回 True。
     • 若 two_sum 小於 new_goal，則將 start 向右移動以增大和。
     • 若 two_sum 大於 new_goal，則將 end 向左移動以減小和。
   • 若遍歷完畢仍未找到滿足條件的數字對，則傳回 False。

程式碼實作

def has_two_sum(numbers, target):
    '''
    檢查列表中是否存在兩個數字的和等於目標數字。
    '''
    if len(numbers) < 2:
        return False
    
    start = 0
    end = len(numbers) - 1
    
    while start < end:
        two_sum = numbers[start] + numbers[end]
        if two_sum == target:
            return True
        elif two_sum < target:
            start += 1
        else:
            end -= 1
    
    return False

def has_three_summers(numbers_list, goal):
    '''
    檢查列表中是否存在三個數字的和等於目標數字。
    '''
    if len(numbers_list) < 3:
        return False
    
    for i in range(len(numbers_list)):
        x = numbers_list[i]
        new_goal = goal - x
        if has_two_sum(numbers_list[i+1:], new_goal):
            return True
    
    return False

內容解密：

1. has_two_sum 函式：該函式利用雙指標技術，在已排序的列表中高效地尋找兩個數字的和是否等於目標值。時間複雜度為 O(n)，其中 n 是列表長度。

   • 初始化兩個指標，一個在列表起始位置，另一個在末尾。
   • 根據當前兩數之和與目標值的比較結果，動態調整指標位置。

2. has_three_summers 函式：遍歷輸入列表，對每個元素呼叫 has_two_sum 檢查剩餘部分是否存在兩個數字的和等於新的目標值。

   • 整體時間複雜度為 O(n^2)，其中 n 是輸入列表的長度。

3. 最佳化與改進：該演算法已經相對高效，但對於極大規模的資料集，可以進一步最佳化，例如透過更高效的資料結構或演算法來減少不必要的計算。