陣列與基本算法

陣列（Array）是一種用來儲存「多個同類型資料」的資料結構。你可以把它想像為一排連續的格子，每個格子放一個值，而每個格子都有自己的位置編號（索引 index）。

• 同類型：同一個陣列內通常放相同類型資料（例如全部是整數、全部是文字）。
• 有次序：每個值都有固定位置，可用索引直接取出或修改。
• 可配合循環：用 i 由 1 行到 N，就能逐格處理。

在本課的偽代碼慣例中，索引通常由 1 開始（例如 A[1] 至 A[N]）。

當資料的「數量」會改變（例如學生人數由 5 變成 30），用 h1、h2、h3… 這種獨立變量的方式會迅速失控。陣列的好處是：你只需要一個名字（例如 array[ ]），就能表示一整組資料。

• 可擴展：N 改變時，只需改 N 的值，循環仍然可用。
• 易維護：不用逐個變量改名或逐個加/刪程式碼。
• 易套用常見算法：加總、平均、搜尋、最大/最小值等都可用同一種循環模式。

索引是「位置編號」，不是「值」。例如 A[3] 表示第 3 格的內容。若 N 表示陣列中有效資料的數量，常見有效索引範圍就是 1 至 N。

• 越界（out of range）是最常見錯誤：當 i < 1 或 i > N 時，A[i] 沒有意義。
• N 通常是「已輸入/有效」的項目數，而不是陣列的最大容量。
• 檢查 loop 範圍時，要特別留意是否應該到 N 或 N-1（例如排序檢查需要比較 i 與 i+1，所以 i 最多到 N-1）。

簡單口訣：凡是會用到 A[i+1] 或 A[i-1] 的情況，都要先確認 i 的上下限。

處理陣列的典型寫法是：用一個計數變量 i，從 1 逐步走到 N，每一圈處理一格。

例如「逐格輸入」：

例如「逐格輸出」：

理解這個模式後，大部分陣列題目都可以視為在循環中加入不同的處理（例如累加、比較、計數）。

• 把索引當成值：例如把 i 的大小誤以為是 A[i] 的大小。
• 忘記初始化：例如 total 未先設為 0 就開始累加。
• 混淆 N 的意義：N 是有效資料量；若刪除或插入後，N 需要更新。
• 把同一個陣列同時當作不同意義：例如 A 同時代表「分數」又代表「分數」，會令程式可讀性變差。

建議做法：先在草稿上寫清楚「A[ ] 代表甚麼、N 代表甚麼、i 的範圍是多少」，再開始寫偽代碼。

• Read N values into array A：代表要用循環輸入 A[1]…A[N]。
• Find the position of X in A：多數是線性搜尋（由 1 掃到 N）。
• Update N after deletion/insertion：代表 N 會改變，之後所有循環上限也要跟着改。
• Show/trace the values of variables：代表你需要逐步追蹤 i、A[i]、total 等變量的變化。

輸入陣列的目標是：把一連串的數值依次存入 A[1]、A[2]…A[N]。最安全、最清晰的寫法是用循環逐格輸入。

其中 N 代表要輸入的資料個數；i 只是「位置指標」，每次 +1 代表走到下一格。

• A[ ]：用來存放一組資料（例如分數、分數）。A[i] 代表第 i 個資料。
• N：有效資料數量（通常由輸入得出，或題目指定）。
• i：循環計數變量，用來「指向」目前正在處理的那一格。

清楚分工可以避免兩個常見錯誤：① 把 i 當成資料值；② 把 N 當成最後一個索引以外的值（例如誤寫到 N+1）。

輸出陣列通常有兩種目的：

• 顯示結果：例如把所有值逐個輸出，讓使用者看到。
• 方便驗證：例如除錯或追蹤題目時，確認輸入是否正確存入。

常見寫法：

若題目只要求輸出值，不要求索引，也可以只輸出 A[i]。關鍵是：輸出順序通常跟索引順序一致。

有些題目會指明輸入範圍（例如 0 至 100）。這種情況下，你需要在存入 A[i] 前先檢查，否則無效值會污染後續計算。

注意：驗證時常會用暫存變量 x，驗證通過後才把 x 寫入 A[i]。

• "Store"／"Read"：表示要把輸入存入陣列。
• "Display"／"Output"：表示要輸出（有時要指定格式）。
• "for each element"：通常就是 設 i 由 1 至 N。
• "the i-th value"：通常就是 A[i]。

做法：先圈出題目中的關鍵字（N、i-th、position、value），再配對到最常見的陣列循環模板。

計算加總時，最重要的是「累加器」變量（常用 total / sum）。它的功能是：把已處理過的元素總和一直保存起來。

每一圈循環把 A[i] 加入 total，因此循環結束後，total 就是 A[1] 到 A[N] 的總和。

初始化（例如 total ← 0）是為了確保累加從正確的起點開始。若 total 未初始化，它可能包含未知值，導致結果錯誤。

• 加總：起點應為 0（加法的單位元）。
• 計數：起點應為 0（還未符合任何項目）。
• 最大值：起點多數用 A[1]（避免遇到負數時出錯）。

假設 N = 3，A[1]=3、A[2]=5、A[3]=2。追蹤 total 的變化：

因此總和為 10。做追蹤題時，這種「每圈寫一行」的方法最不易漏步。

• 把加總寫成覆蓋：錯誤例子 total ← A[i]（這樣最後只會得到最後一格的值）。
• 循環範圍錯：漏掉 A[1] 或 A[N]，例如 設 i 由 2 至 N 或 設 i 由 1 至 N-1（除非題目指定）。
• 把索引當作值：錯誤例子 total ← total + i。
• total 在循環內重設：如果每圈都 total ← 0，結果永遠只會是單一元素。

很多題目會要求「只加某些元素」，例如只加正數、只加偶數、只加大於平均的值。做法是在累加前加上一個 if。

時間複雜度仍然是 O(N)，因為最多只掃描每個元素一次。

平均值（average）最基本的定義是：所有數值的總和 ÷ 數值個數。若總和為 sum，而項目數為 N，則 average = sum / N。

因此，平均題目幾乎必定包含兩步：① 先求 sum；② 再除以 N。

這樣寫有兩個好處：清晰、容易追蹤。考試時亦較容易在每一步填入正確答案。

有些同學會誤寫成每圈都 average ← (average + A[i]) / N。這樣不但難以理解，而且結果通常不正確，因為平均值不是逐步用固定 N 去除就能得到。

正確做法是：把總和累積完成後，再做一次除法。

若程式語言或題目設定使用整數除法，sum / N 可能會被截斷小數（例如 7 / 2 變成 3）。考試的偽代碼通常視為可以得到小數，但仍要留意題目是否要求：

• 輸出到多少位小數（例如 1 位、2 位）。
• 是否需要四捨五入（rounding）。
• 是否只需要整數平均（例如向下取整）。

答題時最穩妥是：按題目要求寫明輸出格式，例如 OUTPUT average (2 d.p.)。

平均必須在 N > 0 的情況下才有意義。若題目允許 N 可能為 0（例如沒有輸入任何數），就要先處理：

在大部分課內練習，N 會由題目保證為正整數；但在書寫完整算法時，知道這個邏輯更嚴謹。

線性搜尋（Linear Search）是最基本的搜尋方法：由第一格開始，逐格比較，直到找到目標值 X 或掃描完所有元素。

• 不需要陣列已排序。
• 最壞情況要比較 N 次（當 X 不在陣列內，或在最後一格）。
• 概念簡單，最常出現在基礎算法題。

常見要求是「找出 X 出現的位置（position）」。若找到，回傳索引；若找不到，回傳 0（或 -1，視題目慣例）。

重點：找到後可以「早停」（退出循還），避免多做無謂比較。

如果題目只問「是否存在」，可以用 found（True/False）標記：

這種寫法能清楚表達結果，不需要額外使用 pos。

若 X 在陣列內出現多次，題目通常會指明要找哪一個：

• 第一個出現位置：一找到就 退出循還（最常見）。
• 最後一個出現位置：不 退出循還，讓 pos 不斷更新，最後留下最後一次的索引。
• 所有出現位置：用 count 或把索引逐個輸出。

答題前要先看清楚題目用語，例如 first occurrence、last occurrence、all positions。

• 忘記把 pos 初始化為 0（或 found 初始化為 FALSE）。
• 找到後仍繼續掃描：若題目要第一個位置，會導致輸出最後一個位置。
• 比較條件寫錯：把 = 寫成 ≠，或把 X 與 i 比較。
• 循環範圍錯：少掃一格會令某些情況找不到。

簡單檢查法：想一想 X 在 A[1]、A[N] 以及完全不存在的三種情況，算法是否都合理。

計數題的核心是：設一個計數器 count，初值為 0；每當遇到符合條件的元素，就把 count 加 1。

條件（condition）可以是：

• 等於某值：A[i] = X（例如數 5 出現次數）。
• 比較大小：A[i] ≥ 60（例如數及格人數）。
• 多重條件：例如 10 ≤ A[i] ≤ 20，或 (A[i] 為偶數) AND (A[i] > 0)。

寫多重條件時，要留意 AND/OR 的邏輯與括號，避免優先次序出錯。

假設 A = [2, 5, 5, 1]（N=4），要數 5 出現次數：

最後 count = 2。考試追蹤題可用同樣方式逐行寫出變化。

若題目要統計每個分數/字母的出現次數，通常會用另一個「計數陣列」freq[ ]。例如分數 0–100：freq[0] 至 freq[100]。

概念是：看到值 v，就令 freq[v] 加 1。這是計數題的自然延伸。

• count 未初始化為 0。
• 每圈把 count 重設（例如放在循環內）。
• 條件寫反或漏括號，令符合條件的元素被忽略。
• 把 count ← count + A[i]（這變成加總，不是計數）。

找最大值（或最小值）的標準方法是「冠軍思想」：先假設第一格是目前最大值，之後逐格比較，若發現更大就更新。

若陣列內可能包含負數，用 0 作初值會出錯（例如 A 全是負數時，最大值仍會被錯誤地留在 0）。用 A[1] 作初值能保證初值一定是陣列中的有效元素。

同理：找最小值時也應以 A[1] 為初值。

題目常要求輸出最大值出現的位置。做法是同時保存 maxPos：

輸出時可以同時輸出 max 和 maxPos。

若最大值出現多次：

• >：只在找到更大才更新，所以會保留「第一次出現」的位置。
• ≥：當遇到相同最大值也更新，所以會得到「最後一次出現」的位置。

要選哪一個，視乎題目要求。題目沒有說明時，通常保留第一次出現較常見。

• N=1 時循環範圍要合理：設 i 由 2 至 N 會自然不執行，max 仍為 A[1]。
• 把比較方向寫錯：找最大值卻用 <。
• 忘記更新位置：max 更新了但 maxPos 沒更新。
• 把 max 初始化為 0：在全負數情況會錯。

若題目說陣列已按遞增（ascending）排序，通常意思是：對所有 i（1 ≤ i < N），都有 A[i] ≤ A[i+1]。

• 若要求嚴格遞增（strictly increasing），則是 A[i] < A[i+1]（不允許相等）。
• 若題目沒有特別說明，最常見是「非遞減」（允許相等）即 ≤。

要判斷是否遞增排序，不需要做排序，只要逐對比較相鄰元素即可。若任何一對違反次序，就不是排序。

注意循環只到 N-1，因為會用到 A[i+1]。

一旦找到一對違規（A[i] > A[i+1]），結果已確定為 FALSE，繼續掃描沒有額外價值，因此可以立即停止。這能減少不必要的比較。

在最壞情況（已排序）仍需比較 N-1 次；但若早期已發現違規，可大幅節省時間。

有些題目會要求指出最早違規的位置 i。做法是保存 errorPos：

此時 errorPos = i 代表 A[i] 與 A[i+1] 這一對出問題。

• 循環寫到 N：會令 i=N 時要比較 A[N+1]，造成越界。
• 比較方向寫反：A[i] < A[i+1] 時誤判為未排序。
• sorted 初值忘記設為 TRUE：會導致永遠是 FALSE。
• 題目要求遞減（descending）卻用遞增的比較：遞減時應檢查 A[i] < A[i+1] 是否成立（或等價地檢查 A[i] ≥ A[i+1]）。

在一般陣列中，元素位置是連續的；要刪除第 P 個元素（A[P]），通常做法是把 P 後面的元素逐格向左移一格，覆蓋掉 A[P]。

刪除後，有效資料個數 N 需要減 1。

循環到 N-1，是因為 i=N 時會用到 A[N+1]（越界）。

移位完成後，原本的 A[N] 會被複製到 A[N-1]，而 A[N] 仍然存在但已不再屬於「有效資料」。

• 因此，之後所有處理都應該只遍歷 1…N（更新後的 N）。
• 若需要把 A[N] 清空，通常不是必需，除非題目要求。

• P=1：代表刪除第一格，所有元素都要向左移。
• P=N：代表刪除最後一格，設 i 由 N 至 N - 1 不會執行，直接 N ← N - 1 即可。

所以標準寫法自然涵蓋這些情況，無需另外分開多段程式。

• 移位方向寫錯：把 A[i+1] ← A[i]（這會向右搬，與刪除相反）。
• 循環上限寫到 N：會用到 A[N+1]。
• 忘記更新 N：刪除後仍用舊 N 會導致把「無效尾巴」也當成資料。
• 沒有檢查 P 範圍：P 越界會令結果不可預期。

要在第 P 個位置插入新值 x（令 x 成為新的 A[P]），必須先把原本從 P 到 N 的元素整段向右移一格，騰出 A[P] 這個空位。

插入後，有效資料個數 N 需要加 1。

重點：移位必須由右向左（DOWNTO），否則會覆蓋尚未搬走的資料。

• P=1：插入到最前，所有元素都向右移一格。
• P=N+1：等同「加到尾端」（append），FOR 循環不會執行，直接 A[N] ← x。

因此，上述標準偽代碼同樣可以自然處理這些情況。

真實陣列通常有固定容量（例如最多 100 個元素）。若 N 已等於容量，插入會失敗。部分題目會要求你先檢查：

如果題目沒有提及容量限制，一般可假設有足夠空間。

• 移位方向錯：由左向右搬會把資料覆蓋掉。
• N 加 1 的位置不當：若先用舊 N 作為右端，可能少搬一格。
• P 的有效範圍應為 1…N+1：不少同學誤以為只能 1…N。
• 忘記最後把 A[P] 設為 x：只搬位但沒填入新值。

• 加總：看到 total/sum ← 0 及 total ← total + A[i]。
• 平均：先加總，最後才除以 N。
• 搜尋：看到 IF A[i] = X THEN found/pos…，多數會有 退出循還。
• 計數：看到 count ← count + 1（通常放在 IF 內）。
• 最大/最小：先用 A[1] 作初值，再用比較更新。
• 排序檢查：比較 A[i] 與 A[i+1]，循環到 N-1。
• 刪除：A[i] ← A[i+1]（向左移），最後 N ← N - 1。
• 插入：A[i] ← A[i-1]（向右移），先 N ← N + 1。

• (1) 先列清楚：輸入是甚麼？輸出是甚麼？（例如 N、A[ ]、X、P）
• (2) 再決定循環範圍：1…N、2…N、1…N-1 或 N DOWNTO …？
• (3) 最後才寫細節：IF 條件、更新變量、是否需要早停。

若能先把「變量角色」講清楚，整段算法通常就不會亂。

追蹤題要做的是：按程式執行順序逐步更新變量值。最實用的方法是做表：每一圈寫下 i、A[i]、以及關鍵變量（total / count / max / pos）。

遇到 IF：先判斷條件真/假，再決定是否更新變量。遇到 退出循還：立刻停止後續循環。

• 初始化是否正確？（total=0、count=0、max=A[1]、found=FALSE）
• 循環範圍是否正確？（有冇漏 A[1] 或 A[N]？有冇越界 A[i+1]？）
• 更新語句是否正確？（加總用 +A[i]、計數用 +1、移位方向正確嗎？）

很多錯誤其實都集中在這三類。

本頁大多數算法都屬於「單次掃描」：只需由 1 到 N 掃一次，因此時間複雜度通常是 O(N)。

刪除與插入因為需要移位，最壞情況也要搬動接近 N 個元素，仍然是 O(N)。理解這點有助你明白：為何這些算法都以循環為核心。