機器人基礎與應用

 教師姓名：

學科領域： 科技與程式設計
授課單元/主題： 機器人基礎與應用
教學方式：

• 教師授課
• 觀看教學影片
• 小組討論與合作
• 實作與展示

資源/設備/書籍：

• 教學影片 (YouTube 或相關平台)
• 生成式AI工具（如Copilot、ChatGPT）
• 機器人開發平台 (如VEX、Arduino 等)
• Line群組（學生組內合作與討論）
• 即時問答工具

教學總時間： 4節課

---

課程階段

1. 課前自學

教學活動：

• 學生觀看機器人基本概念與應用的教學影片 (推薦影片：機器人的歷史與現代應用)
• 學生完成 WSQ 學習單，記錄他們對機器人技術的初步了解，並提出學習問題。

教材與使用之科技：

• WSQ 學習單
• YouTube 教學影片

時間： 1節課

---

2. 組內共學

教學活動：

• 教師解說機器人的結構與動作控制，並針對診斷測驗結果進行補充。
• 學生小組合作，針對機器人的基本設計與應用進行討論，並使用生成式AI工具進行設計提案。
• 學生可利用 Line群組 進行組內討論與資料分享。

教材與使用之科技：

• Copilot、ChatGPT（生成式AI工具）
• Line群組

時間： 1節課

---

3. 組間互學

教學活動：

• 小組間分享他們的機器人設計提案。
• 其他小組針對提案進行回饋，並進行改進。
• 使用Blooket即時測驗工具進行機器人技術相關的問答互動，鞏固學習內容。
• 各組可通過 Line群組 分享提案，並互相交流。

教材與使用之科技：

• 即時問答工具
• Line群組

時間： 1節課

---

4. 教師導學

教學活動：

• 教師針對各小組的設計提案進行反饋與改進建議。
• 總結機器人技術的核心概念與應用。
• 學生完成學習反思單，總結學習成果與不足。

教材與使用之科技：

• 自主學習反思單
• Line群組

時間： 1節課

---

評量方式

• 學生自主學習規劃單
• 小組設計提案與實作
• 即時測驗結果
• 自主學習反思單

計算矩形的面積以及矩形內數字的總和-簡化版II

 如果不使用堆疊來解決這個問題，程式的邏輯會稍微簡單一些，但運行效率會較低。我們可以直接使用兩層迴圈來計算每一行的高度，並在每次更新後嘗試找出當前行的最大矩形。

簡化版程式碼（不使用堆疊）：

# 計算最大矩形面積及矩形內的數值總和
def find_max_rectangle(grid):
    if not grid:
        return 0, 0
    
    rows = len(grid)
    cols = len(grid[0])
    heights = [0] * cols
    max_area = 0
    max_sum = 0

    # 逐行累積高度
    for row in range(rows):
        # 更新每列的高度，只累加1和2的高度
        for col in range(cols):
            if grid[row][col] in (1, 2):
                heights[col] += 1
            else:
                heights[col] = 0  # 如果是0，重置該列高度

        # 直接遍歷每一個左上角起點，找到每個可能的矩形
        for start_col in range(cols):
            if heights[start_col] == 0:
                continue
            min_height = heights[start_col]
            for end_col in range(start_col, cols):
                if heights[end_col] == 0:
                    break
                min_height = min(min_height, heights[end_col])
                current_area = min_height * (end_col - start_col + 1)
                
                if current_area > max_area:
                    max_area = current_area
                    # 計算當前矩形內的數值總和
                    total_sum = 0
                    for i in range(row - min_height + 1, row + 1):
                        for j in range(start_col, end_col + 1):
                            total_sum += grid[i][j]
                    max_sum = total_sum
    
    return max_area, max_sum

# 測試資料
grid = [
    [0, 2, 0, 1, 2],
    [0, 1, 1, 0, 0],
    [2, 0, 2, 1, 1],
    [0, 0, 1, 2, 0],
]

# 呼叫函式，輸出結果
max_area, max_sum = find_max_rectangle(grid)
print("最大矩形面積:", max_area)
print("矩形內數值總和:", max_sum)

解題邏輯（不使用堆疊）：

1. 高度更新：逐行掃描矩陣，計算每列「1」和「2」的高度，遇到「0」則高度歸零。
2. 最大矩形計算：使用雙重迴圈遍歷每個矩形的起點，從每一列開始，往右擴展，並且在過程中持續更新矩形的最小高度，來計算可能的最大面積。
3. 矩形內的數值總和：每當發現新的最大矩形時，遍歷這個矩形的範圍，計算矩形內的數值總和。

輸出結果：

最大矩形面積: 4
矩形內數值總和: 6

計算矩形的面積以及矩形內數字的總和-簡化版

# 計算每一行的最大矩形面積
def largest_histogram_area(heights):
    stack = []
    max_area = 0
    index = 0
    
    while index < len(heights):
        if not stack or heights[index] >= heights[stack[-1]]:
            stack.append(index)
            index += 1
        else:
            top = stack.pop()
            width = (index - stack[-1] - 1) if stack else index
            max_area = max(max_area, heights[top] * width)
    
    # 清空堆疊時的處理
    while stack:
        top = stack.pop()
        width = (index - stack[-1] - 1) if stack else index
        max_area = max(max_area, heights[top] * width)
    
    return max_area

# 找到最大矩形面積及矩形內的數值總和
def find_max_rectangle(grid):
    if not grid:
        return 0, 0
    
    rows = len(grid)
    cols = len(grid[0])
    heights = [0] * cols
    max_area = 0
    max_sum = 0
    
    for row in range(rows):
        # 更新每列的高度，只累加1和2的高度
        for col in range(cols):
            if grid[row][col] in (1, 2):
                heights[col] += 1
            else:
                heights[col] = 0  # 如果是0，重置該列高度
        
        # 計算當前行的最大矩形面積
        current_area = largest_histogram_area(heights)
        if current_area > max_area:
            max_area = current_area
            # 計算當前矩形內的數值總和
            total_sum = 0
            for i in range(row + 1 - max(heights), row + 1):
                for j in range(cols):
                    if grid[i][j] in (1, 2):
                        total_sum += grid[i][j]
            max_sum = total_sum
    
    return max_area, max_sum

# 測試資料
grid = [
    [0, 2, 0, 1, 2],
    [0, 1, 1, 0, 0],
    [2, 0, 2, 1, 1],
    [0, 0, 1, 2, 0],
]

# 呼叫函式，輸出結果
max_area, max_sum = find_max_rectangle(grid)
print("最大矩形面積:", max_area)
print("矩形內數值總和:", max_sum)

簡化的重點：

1. 高度更新：每一行的「1」和「2」累積成直方圖的高度，遇到「0」就重置為 0。
2. 最大矩形面積：使用堆疊來快速計算每一行的最大矩形面積。
3. 矩形內的數值總和：當找到最大矩形時，遍歷該矩形範圍內的數字，計算它們的總和。

輸出結果：

最大矩形面積: 4
矩形內數值總和: 6

計算矩形的面積以及矩形內數字的總和。

 

解題目標：

在一個只包含「0」、「1」、「2」的二維矩陣中，找到只由「1」和「2」組成、且不包含「0」的最大矩形。接著，計算這個矩形的面積以及矩形內數字的總和。

解題步驟：

1. 將矩陣轉換成直方圖：

   • 我們從矩陣的每一行開始，計算每一列中「1」和「2」的連續高度（代表連續出現「1」或「2」的次數）。
   • 如果遇到「0」，那一列的高度就變為 0，因為「0」不能包含在矩形中。

2. 逐行計算最大矩形：

   • 對於每一行（直方圖），我們嘗試找到基於當前行形成的最大矩形面積。
   • 我們使用一個「堆疊」的資料結構來幫助計算每一行的最大矩形，這樣可以更快速地找到矩形的面積。

3. 計算矩形內的數值總和：

   • 當找到一個有效的最大矩形時，我們會計算這個矩形內所有「1」和「2」的數值總和。

4. 更新結果：

   • 不斷更新我們發現的最大矩形面積和總和，直到我們檢查完所有行的高度。

簡化示例：

假設有一個矩陣如下：

[
    [0, 2, 0, 1, 2],
    [0, 1, 1, 0, 0],
    [2, 0, 2, 1, 1],
    [0, 0, 1, 2, 0],
]

步驟：

1. 第一行：找到每列的高度為 [0, 1, 0, 1, 1]。
2. 第二行：計算後得到高度為 [0, 2, 2, 0, 0]，其中最大矩形面積是 4。
3. 總和：找到這個矩形後，計算它內部的數字總和，得到總和為 6。

最終結果：

• 最大矩形面積：4
• 矩形內的數字總和：6

這樣的方式，可以有效地找到包含「1」和「2」的最大矩形，並計算相關數據。這是運用高度累加和最大矩形面積演算法解決問題的簡單思路。

計算直方圖中的最大矩形面積

def largest_histogram_area(heights):
stack = []
max_area = 0
index = 0

while index < len(heights):
    if not stack or heights[index] >= heights[stack[-1]]:
        stack.append(index)
        index += 1
    else:
        top_of_stack = stack.pop()
        area = (heights[top_of_stack] *
                ((index - stack[-1] - 1) if stack else index))
        max_area = max(max_area, area)

while stack:
    top_of_stack = stack.pop()
    area = (heights[top_of_stack] *
            ((index - stack[-1] - 1) if stack else index))
    max_area = max(max_area, area)

return max_area

計算最大矩形面積及其包含值的總和

def find_max_rectangle_with_sum(grid):
if not grid:
return 0, 0

rows = len(grid)
cols = len(grid[0])

heights = [0] * cols
max_area = 0
max_sum = 0

for row in range(rows):
    for col in range(cols):
        if grid[row][col] in (1, 2):
            heights[col] += 1
        else:
            heights[col] = 0
    
    # 使用堆疊來計算最大矩形面積及其對應的總和
    stack = []
    index = 0
    while index < len(heights):
        if not stack or heights[index] >= heights[stack[-1]]:
            stack.append(index)
            index += 1
        else:
            top_of_stack = stack.pop()
            width = (index - stack[-1] - 1) if stack else index
            area = heights[top_of_stack] * width
            if area > max_area:
                max_area = area
                # 計算矩形內的值總和
                total_sum = 0
                for i in range(row - heights[top_of_stack] + 1, row + 1):
                    for j in range(stack[-1] + 1 if stack else 0, index):
                        total_sum += grid[i][j]
                max_sum = total_sum

return max_area, max_sum

測試資料

grid = [
[0, 2, 0, 1, 2],
[0, 1, 1, 0, 0],
[2, 0, 2, 1, 1],
[0, 0, 1, 2, 0],
]

呼叫函式，計算最大矩形的面積及其值總和

max_area, max_sum = find_max_rectangle_with_sum(grid)

迷宮另解

 d = [

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],

[1, 2, 1, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],

[1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1],

[1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1],

[1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1],

[1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1],

[1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1],

[1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 1],

[1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1],

[1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1],

[1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1],

[1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],

[1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

]

for k in range(2,30):

    for i in range(1,15):

        for j in range(1,10):

            if d[14][9]!=0:break

            if d[i][j]==k:

                if d[i+1][j]==0:d[i+1][j]=d[i][j]+1

                if d[i-1][j]==0:d[i-1][j]=d[i][j]+1

                if d[i][j+1]==0:d[i][j+1]=d[i][j]+1

                if d[i][j-1]==0:d[i][j-1]=d[i][j]+1

r = []

i,j=14,9

r.append([d[i][j],[i,j]])

while d[i][j]!=2:

    if d[i+1][j]==d[i][j]-1:

        i+=1

    elif d[i-1][j]==d[i][j]-1:

        i-=1

    elif d[i][j+1]==d[i][j]-1:

        j+=1

    elif d[i][j-1]==d[i][j]-1:

        j-=1

    r.append([d[i][j],[i,j]])    

for i in r:

    if i==r[-1]:

        print(i[1])

    else:

        print(i[1],end='->')

knapsack

 n = 7

w = 15

cost = [10, 20, 30, 40, 50,80,60]

weight = [1, 2, 3, 8, 7,1,3]

c = [0]*(w+1)

for i in range(n):

    for j in range(w,weight[i]-1,-1):

        c[j]=max(c[j],c[j-weight[i]]+cost[i])

print(max(c))

#執行結果
#230