遞迴分割簡例 II

 讓我們逐步分析這個程式，以理解如何透過遞迴找到列表中的最大值。

程式結構

這段程式的目標是實現 findMax 函式，透過「分而治之」的方式，在不使用內建的 max 函式下找出列表 d 中的最大值。

def findMax(d):
    if len(d) == 1:
        return d[0]  # 返回單一元素，而非列表
    
    m = len(d) // 2
    lMax = findMax(d[:m])
    rMax = findMax(d[m:])
    
    if lMax > rMax:
        return lMax
    else:
        return rMax

# 測試
d = [1, 3, 5, 7, 8, 6, 4, 2, 21, 13, 15, 17, 18, 16, 14, 12]
print(findMax(d))  # 預期輸出: 21

程式詳解

1. 基礎情況（遞迴的終止條件）

   if len(d) == 1:
       return d[0]
   

   當 d 的長度為 1 時，說明這個子列表已經被分割到最小了（只有一個元素），這時直接返回這個元素即可。這一行是遞迴的「終止條件」，避免遞迴無限進行。

2. 分割列表

   m = len(d) // 2
   

   這行將列表 d 的長度除以 2，並取整數部分來得到中間索引 m。接下來，d 會被分成兩個子列表：

   • d[:m]：包含 d 的前半部分。
   • d[m:]：包含 d 的後半部分。

3. 遞迴呼叫 findMax 函式

   lMax = findMax(d[:m])
   rMax = findMax(d[m:])
   

   程式分別對 d 的前半部分和後半部分再次遞迴呼叫 findMax。每次呼叫 findMax 都會進一步將列表分成更小的部分，直到每部分只剩一個元素。lMax 和 rMax 分別保存前半部分和後半部分的最大值。

4. 比較左右部分的最大值

   if lMax > rMax:
       return lMax
   else:
       return rMax
   

   程式比較 lMax 和 rMax，返回其中較大的值。這一步驟會逐層向上返回每個分支中的最大值，直到得到整個列表的最大值。

遞迴過程示例

以 d = [1, 3, 5, 7, 8, 6, 4, 2, 21, 13, 15, 17, 18, 16, 14, 12] 為例，這個列表經過遞迴分割及比較的過程如下：

1. 列表被分割成 [1, 3, 5, 7, 8, 6, 4, 2] 和 [21, 13, 15, 17, 18, 16, 14, 12]。
2. 對於 [1, 3, 5, 7, 8, 6, 4, 2]，繼續分割成 [1, 3, 5, 7] 和 [8, 6, 4, 2]，如此重複直到每個子列表僅含一個元素。
3. 分割過程結束後，開始向上比較每一層中的最大值：
   • 例如，在 [1, 3, 5, 7] 這一層中，找到的最大值是 7；在 [8, 6, 4, 2] 這一層中，找到的最大值是 8。
   • 接著在更高一層中比較 7 和 8，得到 8。
4. 最後，將左右兩半的最大值 8 和 21 比較，最終返回最大值 21。

執行結果

最終輸出為：

21

這個 findMax 函式使用了「分而治之」的遞迴方法，通過逐層分割並比較左右子列表中的最大值，最終得到整個列表的最大值。

遞迴分割簡例I

 def div2(d):

    print(d)

    global c

    c +=1

    if len(d)<=1:

        return d

    m = len(d)//2

    d1 = d[:m]

    div2(d1)

    d2 = d[m:]

    div2(d2)

d = [1,3,5, 7, 8, 6, 4, 2]

c=0

div2(d)

print(c)

# result:

# [1, 3, 5, 7, 8, 6, 4, 2]

# [1, 3, 5, 7]

# [1, 3]

# [1]

# [3]

# [5, 7]

# [5]

# [7]

# [8, 6, 4, 2]

# [8, 6]

# [8]

# [6]

# [4, 2]

# [4]

# [2]

# 15




div2 函式是一個遞迴函式，主要作用是將一個列表 d 不斷分割成更小的子列表，直到每個子列表只有一個元素為止。具體流程如下：

函式內部流程

1. 全域變數 c：

   • c 是在函式外部定義的全域變數，用來計算 div2 函式被呼叫的次數。
   • 每當 div2 被呼叫時，c 的值都會加 1，最後的 c 值就代表總共呼叫了多少次 div2 函式。

2. 遞迴分割：

   • 如果列表 d 的長度小於或等於 1（if len(d) <= 1），則表示該子列表已經分割到最小，不需要再分割，因此直接返回該列表作為遞迴的終止條件。
   • 如果 d 的長度大於 1，則將其分為兩部分：
     • d1 是 d 的前半部分（d[:m]）。
     • d2 是 d 的後半部分（d[m:]）。
   • 接著，函式會分別對 d1 和 d2 再次遞迴呼叫 div2，不斷分割直到每個子列表只剩下一個元素。

3. 列印語句：

   • print(d) 的作用是在每次呼叫 div2 時，列印出當前的列表 d，方便觀察每次遞迴的分割過程。

為什麼 c 最終為 15？

以 d = [1, 3, 5, 7, 8, 6, 4, 2] 這個列表為例，包含 8 個元素。這個函式會對整個列表進行遞迴分割，直到每個子列表只有一個元素。以下是遞迴分割的過程：

1. 初始呼叫 [1, 3, 5, 7, 8, 6, 4, 2]，分割成 [1, 3, 5, 7] 和 [8, 6, 4, 2]
2. 呼叫 [1, 3, 5, 7]，分割成 [1, 3] 和 [5, 7]
3. 呼叫 [1, 3]，分割成 [1] 和 [3]（達到基礎情況，不再分割）
4. 呼叫 [5, 7]，分割成 [5] 和 [7]（達到基礎情況）
5. 呼叫 [8, 6, 4, 2]，分割成 [8, 6] 和 [4, 2]
6. 呼叫 [8, 6]，分割成 [8] 和 [6]（達到基礎情況）
7. 呼叫 [4, 2]，分割成 [4] 和 [2]（達到基礎情況）

數一數所有的呼叫次數，包括每次分割和達到基礎情況的呼叫，總共是 15 次，這就是為什麼 c 最後的值是 15。

• div2 函式演示了遞迴分割列表的過程。
• c 計算了所有遞迴呼叫的總次數，在這個例子中為 15 次。

雙向螺旋矩陣

 import math

n1 = int(input())

for i in range(n1):

  m,d1 = map(int,input().split())

  n = m**2

  if d1==1:

    d=[[0]*m for _ in range(m)]

    

    k = 1

    r,c = 0,0

    dirn = 0

    dirs = [[0,1],[1,0],[0,-1],[-1,0]] 

    

    while k<=n:

      d[r][c]=k

      k+=1

      

      nr,nc = r+dirs[dirn][0],c+dirs[dirn][1]

      if  nr<m and nc<m and d[nr][nc]==0 :

          r,c = nr,nc

      else:

          dirn=(dirn+1)%4

          r,c = r+dirs[dirn][0],c+dirs[dirn][1]

    

    for row in d:

      formatted_row = " ".join(str(num).rjust(5) if num!=0 else " "*5  for num in row)

      print(formatted_row)

    print()

  else:

    d=[[0]*m for _ in range(m)]

    

    k = 1

    r,c = 0,0

    dirn = 0

    dirs = [[1,0],[0,1],[-1,0],[0,-1]] 

    

    while k<=n:

      d[r][c]=k

      k+=1

      

      nr,nc = r+dirs[dirn][0],c+dirs[dirn][1]

      if  nr<m and nc<m  and d[nr][nc]==0 :

          r,c = nr,nc

      else:

          dirn=(dirn+1)%4

          r,c = r+dirs[dirn][0],c+dirs[dirn][1]

    

    for row in d:

      formatted_row = " ".join(str(num).rjust(5) if num!=0 else " "*5  for num in row)

      print(formatted_row)

    print()

質數日

 def is_leap(year):

    # 檢查是否為閏年

    return (year % 4 == 0 and year % 100 != 0) or (year % 400 == 0)

def is_prime(n):

    # 檢查 n 是否為質數

    if n < 2:

        return False

    if n % 2 == 0:

        return n == 2

    for i in range(3, int(n**0.5) + 1, 2):

        if n % i == 0:

            return False

    return True

# 定義每個月的天數

def days_in_month(year, month):

    if month in [4, 6, 9, 11]:

        return 30

    elif month == 2:

        return 29 if is_leap(year) else 28

    else:

        return 31

prime_dates = []

# 範圍是2000年到2999年

for year in range(2000, 3000):

    for month in range(1, 13):

        for day in range(1, days_in_month(year, month) + 1):

            # 將日期格式化為 YYYYMMDD

            date_number = int(f"{year}{month:02d}{day:02d}")

            # 檢查是否為質數

            if is_prime(date_number):

                prime_dates.append(date_number)

# 列出所有質數日並輸出總數

for prime_date in prime_dates:

    print(prime_date)

print("質數日總數:", len(prime_dates))

# 執行結果：

# .

# .

# .

# 29990119

# 29990123

# 29990131

# 29990327

# 29990503

# 29990603

# 29990621

# 29990707

# 29990713

# 29990717

# 29990801

# 29990903

# 29990927

# 29990929

# 29991001

# 29991019

# 29991109

# 29991113

# 29991119

# 29991211

# 質數日總數: 21934

有括號的表達式

 處理含有括號的表達式，同時考慮運算優先順序（乘除優先於加減），可以將中序表達式轉換為後序表達式。括號會影響運算順序，因此需要按照括號優先的規則來處理。

中序轉後序的演算法（含括號）

1. 數字：直接加入後序輸出序列。
2. 左括號 (：推入運算符堆疊。
3. 右括號 )：將運算符堆疊中的符號依次彈出，直到遇到左括號 (，並將左括號丟棄。
4. 運算符（例如 +, -, *, /）：
   • 比較該運算符與堆疊頂端運算符的優先順序。
   • 如果堆疊頂部的運算符優先順序較高或相等，則將堆疊頂端的運算符彈出並加入輸出序列。
   • 將當前運算符推入堆疊。
5. 清理堆疊：當讀完所有的項目後，將堆疊中剩餘的運算符依次彈出並加入輸出序列。

以下是完整的 Python 程式碼來實現這個過程：

程式碼

# 輸入數學表達式，例如："( 1 + 2 ) * 3"
expression = input("輸入數學表達式，例如 '( 1 + 2 ) * 3': ")

# 步驟 1：把數字和符號分開
tokens = []
for i in expression.split():
    if i.isdigit():           # 如果 i 是數字
        tokens.append(int(i))  # 把數字轉為 int 並加入 tokens
    else:
        tokens.append(i)       # 把符號直接加到 tokens

# 儲存後序表達式的結果
output = []
# 儲存運算符的堆疊
operators = []

# 定義運算符的優先順序
precedence = {'+': 1, '-': 1, '*': 2, '/': 2}

# 步驟 2：轉換為後序表達式
for token in tokens:
    if type(token) == int:       # 如果是數字
        output.append(token)     # 直接加入輸出
    elif token == '(':           # 左括號
        operators.append(token)  # 推入堆疊
    elif token == ')':           # 右括號
        # 把堆疊中的運算符彈出，直到遇到左括號
        while operators[-1] != '(':
            output.append(operators.pop())
        operators.pop()          # 丟掉左括號
    else:                        # 如果是運算符
        # 當堆疊中的運算符優先順序比當前運算符高或相等，彈出它們
        while (operators and operators[-1] != '(' and
               precedence[operators[-1]] >= precedence[token]):
            output.append(operators.pop())
        operators.append(token)  # 把當前運算符推入堆疊

# 把剩下的運算符都彈出
while operators:
    output.append(operators.pop())

# 後序表達式已生成
print("後序表達式:", output)

# 步驟 3：計算後序表達式的結果
stack = []

for token in output:
    if type(token) == int:   # 如果是數字，推入堆疊
        stack.append(token)
    else:                    # 如果是運算符，取出兩個數字計算
        b = stack.pop()      # 堆疊頂部的數字為 b
        a = stack.pop()      # 再取出一個數字為 a
        if token == '+':
            stack.append(a + b)
        elif token == '-':
            stack.append(a - b)
        elif token == '*':
            stack.append(a * b)
        elif token == '/':
            stack.append(a / b)  # 確保除數不為 0

# 最後堆疊中只剩一個結果，即為最終計算結果
result = stack[0]
print("結果:", result)

程式說明

1. 解析輸入：將輸入表達式按空格分開，分成數字和符號，存入 tokens 列表中。

2. 轉換為後序表達式：

   • 數字直接加入 output 列表。
   • 左括號 ( 直接推入 operators 堆疊。
   • 右括號 ) 會觸發彈出 operators 堆疊中的運算符，直到遇到左括號為止。
   • 當運算符出現時，根據優先順序彈出堆疊中的運算符，直到當前運算符具有最高優先順序。

3. 計算後序表達式：

   • 用堆疊來計算後序表達式。遇到數字時推入堆疊，遇到運算符時彈出兩個數字並計算結果，再把結果推回堆疊。
   • 最後堆疊中唯一的數字即為結果。

範例執行

輸入：

( 1 + 2 ) * 3

執行過程：

1. 解析 tokens 為 [ '(', 1, '+', 2, ')', '*', 3 ]
2. 轉換為後序表達式：[ 1, 2, '+', 3, '*' ]
3. 後序計算：
   • 1 + 2 = 3
   • 3 * 3 = 9

輸出：

後序表達式: [1, 2, '+', 3, '*']
結果: 9