這題其實包含兩部分：
上面是 時間複雜度分析（PROGRAM-1），
下面是 堆疊（Stack）結構與應用題（十進制轉二進制）。
以下分別給出標準作答與解析?
---
?【第一部分】PROGRAM-1 時間複雜度分析（10 分）
n = int(input())
k = 0
counter = 0
for i in range(1, n//2):
k = k + 1
for j in range(1, n, pow(2, k)):
counter = counter + 1
print(counter)
?外層迴圈：
for i in range(1, n//2) → 約執行 n/2 次。
?內層迴圈：
for j in range(1, n, pow(2, k))
→ 每次迴圈間隔為 2^k，執行次數約為 n / 2^k。
?總執行次數（counter 累加次數）：
T(n) = \sum_{k=1}^{n/2} \frac{n}{2^k}
T(n) < n \sum_{k=1}^{\infty} \frac{1}{2^k} = n(1) = O(n)
✅ 結論：時間複雜度為 O(n)
空間複雜度僅用到常數變數（k, counter），為 O(1)。
---
?【第二部分】堆疊資料結構與十進制轉二進制（15 分）
?堆疊（Stack）的定義與特性
1. 一種**後進先出（LIFO, Last In First Out）**的線性資料結構。
2. 只能在一端（稱為頂端 Top）進行「推入 (Push)」與「彈出 (Pop)」操作。
3. 應用於：函式呼叫、括號匹配、逆序轉換、遞迴模擬等。
---
?堆疊應用：十進制轉二進制
原理：
將十進制數反覆除以 2，取餘數並依「反向順序」輸出。
使用堆疊可自然地將餘數逆序。
步驟：
1️⃣ 不斷取餘數 n % 2 並 push 入堆疊。
2️⃣ 當 n == 0 時停止。
3️⃣ 不斷取出（pop）堆疊元素，依序組成二進位字串。
---
?程式示範（Python 版）
def dec_to_bin(n):
stack = []
while n > 0:
stack.append(n % 2) # push
n //= 2
bin_str = ''
while stack:
bin_str += str(stack.pop()) # pop
return bin_str or '0'
# 範例
num = int(input("輸入十進位數："))
print(dec_to_bin(num))
例：
輸入 13 → 堆疊過程：[1, 0, 1, 1] → 輸出 "1101"
✅ 時間複雜度 O(log n)（因為每次除以2），
✅ 空間複雜度 O(log n)（堆疊儲存餘數）。
---
?【完整答案摘要】
題目 核心答案
PROGRAM-1 時間複雜度 O(n)
堆疊定義 後進先出（LIFO），操作限於一端（push/pop）
應用程式功能 將十進制轉換為二進制
方法 反覆除2取餘 → push → 逆序 pop 輸出
轉換範例 13 → 1101
時間/空間複雜度 O(log n) / O(log n)
---
要我幫你把這份答案整理成「考試卷可直接誦寫的 20 行正式答題稿」版本嗎？（條列＋說明混排版）
阿摩線上測驗
登入
