10/08|陣列(Ch 5)

中山大學 C 程式設計自學指南 Ch 5:陣列宣告與走訪、陣列傳進函式、部分填滿的陣列、搜尋與排序、二維陣列,附本週練習題與參考解答。

發布
更新
字數
6,480
閱讀
約 16 分鐘
瀏覽
111
系列與本頁目錄
  1. 總覽
  2. 環境設置:把工具鏈準備好
  3. 09/10|課程介紹與環境暖身
  4. 09/17|C++ 基礎(Ch 1)
  5. 09/24|流程控制與函式基礎(Ch 2、Ch 3)
  6. 10/01|參數傳遞與函式重載(Ch 4)
  7. 10/08|陣列(Ch 5)
  8. 10/15|結構與類別(Ch 5–6)
  9. 10/22|類別與建構子(Ch 6–7)
  10. 10/29|vector 與運算子重載入門(Ch 7)
  11. 11/05|期中上機考(範圍 Ch 1–6)
  12. 11/12|運算子重載、friend 與 string(Ch 8、Ch 9)
  13. 11/19|指標、動態記憶體與 C 風格字串(Ch 9、Ch 10)
  14. 11/26|分離編譯與命名空間(Ch 11)
  15. 12/03|檔案輸入輸出(Ch 12)
  16. 12/10|繼承(Ch 14)
  17. 12/17|期末筆試(範圍 Ch 1–12、Ch 14)
  18. 12/24|期末上機考(範圍 Ch 1–12、Ch 14)
  19. 附錄:編譯選項、Makefile、錯誤訊息與名詞速查
  1. 陣列是什麼
  2. 用迴圈掃陣列
  3. 陣列傳進函式
  4. 為什麼不能回傳區域陣列
  5. 部分填滿的陣列
  6. 搜尋與排序
  7. 線性搜尋
  8. 選擇排序(selection sort)
  9. 氣泡排序(bubble sort)
  10. 為什麼不讓你用 std::sort
  11. 二維陣列
  12. 本週重點回顧
  13. 本週練習題

← 10/01|參數傳遞與函式重載(Ch 4) | 回總覽 | 10/15|結構與類別(Ch 5–6) →

對應課本習題:Ch5: 4, 8, 10, 14, 17

這幾題各要用到什麼(動手前先看)

主課的上機考幾乎就是這些題目,所以每一題都自己寫過。下表是每題需要的東西(我的歸納,不是題目本文)與本系列對應的練習:

課本題號 要用到的東西 先練
Ch5-4 讀入一串字元,統計幾個母音各出現幾次、按字母序印成兩欄——計數陣列+部分填滿 Q4
Ch5-8 模擬:幾千次隨機分配生日、用陣列記有沒有撞到——陣列+rand(09/24) Q4、09/24 Q16
Ch5-10 代號與庫存各一個陣列,選單反覆購買到結束——陣列存狀態+迴圈選單 Q7 訂票系統
Ch5-14 二維陣列存表格資料,逐列算距離找最接近的一列——二維陣列、sqrt Q5、Q6、Q10
Ch5-17 統計首位數字出現的次數——計數陣列+09/24 的讀檔範例 Q4

這週要會什麼

Text
陣列宣告 → 索引與越界 → 用迴圈掃描 → 陣列與函式 → 部分填滿 → 搜尋與排序 → 二維陣列

陣列是什麼

白話說:陣列就是一排編號的格子,每一格放同一種型別的資料。宣告 int a[5]; 就是要了五個連續的整數格子,編號 0 到 4。

Text
        a[0]  a[1]  a[2]  a[3]  a[4]
      ┌─────┬─────┬─────┬─────┬─────┐
   a  │  3  │  1  │  4  │  1  │  5  │
      └─────┴─────┴─────┴─────┴─────┘
C++
int a[5] = {3, 1, 4, 1, 5};
cout << a[0] << ' ' << a[4] << '\n';   // 3 5
a[2] = 100;                            // 改第三格

= {3, 1, 4, 1, 5} 的大括號跟 if/for 的不是同一回事:這裡它不是程式區塊,而是「一串初始值」,由左到右塞進 a[0]、a[1]…。整行是一個宣告敘述,所以收尾的 } 後面還要加分號(跟 09/24 的 enum { ... }; 同一個道理)。

初始化的幾種寫法:

C++
int a[5] = {3, 1, 4, 1, 5};   // 完整給
int b[5] = {1, 2};            // 沒寫到的自動補 0 → {1,2,0,0,0};所以 int c[5] = {}; 就是全 0
int d[]  = {1, 2, 3};         // 不寫大小,編譯器自己數成 3
int e[5];                     // 沒初始化 → 垃圾值(寫在函式裡時;全域陣列會自動歸零)

雷區 ①:索引 0 到 n-1,而且越界不會有人擋你
int a[5]; 合法索引是 a[0] ~ a[4],a[5] 不存在。但 C++ 不檢查陣列邊界:

C++
int a[5] = {};
a[10] = 999;      // 編譯得過、可能不會當掉,但你已經踩到別人的記憶體

常見症狀有三種:*** stack smashing detected ***: terminated;Segmentation fault(踩得太遠);什麼都不發生,但另一個變數的值莫名其妙變了(最可怕的一種,因為你會去懷疑無辜的程式碼)。寫迴圈時務必確認條件是 i < n 而不是 i <= n。

雷區 ②:陣列大小必須是常數

C++
int n;
cin >> n;
int a[n];        // 標準 C++ 不允許(g++ 有擴充所以編得過,但別依賴)

正解有兩種:宣告一個夠大的固定陣列(const int MAX = 1000; int a[MAX];),或用後面會教的 vector(10/29)與 new(11/19)。

用迴圈掃陣列

C++
const int N = 5;
int a[N] = {3, 1, 4, 1, 5};

int sum = 0;
for (int i = 0; i < N; i++) sum += a[i];      // 標準寫法(+= 與 i++ 見 09/17)

for (int x : a) cout << x << ' ';             // C++11 range-based for

for (int x : a) 讀作「對 a 裡的每一個元素 x」。注意:x 是複製品,改 x 不會改到陣列;要改就寫 for (int& x : a) x *= 2;——這個 & 跟 10/01 的參考參數是同一個,x 不是複製品,而是陣列裡那一格的別名。

用 const int N 而不是直接寫 5:陣列大小改成 10 時只要改一個地方,迴圈條件自動跟著對。

陣列傳進函式

陣列傳進函式時不會複製整個陣列,傳的是「第一格的位址」——位址就是那格記憶體的門牌號碼(細節等 11/19 講指標再展開)。函式拿到的是第一格的門牌,不是整排格子的影本——它照門牌找得到第一格、也改得動裡面的值,但沒人告訴它這排總共有幾格。後果有三個:

  1. 函式可以改到原陣列(就算沒寫 &)。
  2. 函式不知道陣列多長,所以一定要額外傳長度。
  3. 函式裡不能對陣列參數用 range-based for:for (int x : a) 會編譯失敗,訊息是 'begin' was not declared in this scope。原因就是第 2 點——編譯器不知道該在哪裡停。函式裡一律寫 for (int i = 0; i < n; i++)。
C++
#include <iostream>
using namespace std;

int sumArray(const int a[], int n) {   // const:保證不修改
    int s = 0;
    for (int i = 0; i < n; i++) s += a[i];
    return s;
}

void doubleAll(int a[], int n) {       // 沒有 const:打算修改
    for (int i = 0; i < n; i++) a[i] *= 2;
}

int main() {
    int a[5] = {1, 2, 3, 4, 5};
    cout << sumArray(a, 5) << '\n';    // 15
    doubleAll(a, 5);
    cout << sumArray(a, 5) << '\n';    // 30
    return 0;
}

輸出:

Text
15
30

const int a[] 就是 10/01 的 const——對讀者和編譯器宣告「只讀不寫」,手滑寫進去會直接編譯失敗。參數列裡的 [] 寫了大小也沒用(編譯器會忽略它,反而騙了讀程式的人),所以一律留空;這跟雷區 ② 的「宣告陣列時大小必須是常數」是兩回事。

為什麼不能回傳區域陣列

同一個原因還會咬你一口:陣列不能直接回傳。這樣寫會出事:

C++
int* makeArray() {           // int* 是「存放位址」的型別,叫指標,11/19 才正式教
    int a[5] = {1, 2, 3, 4, 5};
    return a;                // 陣列名字單獨出現時值就是第一格的位址,所以型別是 int*
}                            // 但 a 在函式結束的瞬間就消失了

編譯器會給 warning: address of local variable 'a' returned,執行結果是垃圾值或當掉——區域陣列在函式結束時就被回收,回傳的位址指向一塊已經不屬於你的記憶體。標準作法是由呼叫端準備好陣列,函式只負責填:

C++
#include <iostream>
using namespace std;

void fillSquares(int a[], int n) {      // 函式不製造陣列,只填內容
    for (int i = 0; i < n; i++) a[i] = i * i;
}

int main() {
    int a[5];                            // 陣列由呼叫端宣告
    fillSquares(a, 5);
    for (int i = 0; i < 5; i++) {
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}

輸出:

Text
0 1 4 9 16

另一種作法是用 new 在「函式結束也不會消失」的地方配置記憶體,那要等到指標那一節才會教。

部分填滿的陣列

陣列大小必須是常數(雷區 ②),可是要讀幾筆資料常常執行時才知道——只好先開夠大的 100 格,實際可能只用 47 格。做法是另外用一個變數記住有效長度:容量(總共幾格)和目前長度(用了幾格)是兩個不同的數字,傳進函式時兩個都要傳。

C++
#include <iostream>
using namespace std;

const int MAX = 100;

// used = 目前用了幾格,capacity = 總共有幾格
void push(int a[], int& used, int capacity, int value) {
    if (used < capacity) a[used++] = value;   // 先拿目前的 used 當索引,再把 used 加 1
}

int main() {
    int a[MAX];
    int used = 0;                 // 一格都還沒用

    push(a, used, MAX, 10);
    push(a, used, MAX, 20);
    push(a, used, MAX, 30);

    for (int i = 0; i < used; i++) {      // 上界是 used,不是 MAX
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}

輸出:

Text
10 20 30

參數列裡 used 前面那個 & 就是 10/01 的傳參考:push 改掉「用了幾格」要讓 main 看得見,所以必須傳參考;capacity、value 只是讀進來看,傳值就夠。a 沒寫 & 也改得到則是另一回事——陣列傳的是第一格位址,兩者別混著記。

本週練習題 Q1–Q3 用的就是這個模式:宣告 a[100]、讀進 n 個,之後每個迴圈的上界都是 n 而不是 100。

搜尋與排序

線性搜尋

C++
#include <iostream>
using namespace std;

// 找 target:找到回傳「索引」,找不到回傳 -1
int search(const int a[], int n, int target) {
    for (int i = 0; i < n; i++)
        if (a[i] == target) return i;
    return -1;
}

int main() {
    int a[5] = {3, 1, 4, 1, 5};
    cout << search(a, 5, 4) << ' ' << search(a, 5, 9) << '\n';
    return 0;
}

輸出:

Text
2 -1

回傳 -1 代表「找不到」是很常見的約定,因為 -1 不可能是合法索引。

選擇排序(selection sort)

每一輪找出剩下元素中最小的,換到前面。

C++
#include <iostream>
using namespace std;

void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;                          // 先假設剩下的裡面 a[i] 最小
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;    // 找到更小的就記住索引
        if (minIdx != i) {
            int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
        }
    }
}

int main() {
    int a[5] = {5, 1, 4, 2, 8};
    selectionSort(a, 5);
    for (int i = 0; i < 5; i++) {
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}

輸出:

Text
1 2 4 5 8

過程長這樣:

Text
{5,1,4,2,8}  i=0:後面最小是 1,跟 a[0] 交換 → {1,5,4,2,8}
             i=1:後面最小是 2,跟 a[1] 交換 → {1,2,4,5,8}
             i=2、i=3:minIdx == i,已經就位,不交換

int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t; 是三個敘述擠在同一行——C++ 只看分號、不看你怎麼斷行,一行寫幾個敘述都可以。這三步就是 10/01 swapValues 的交換手法:先把 a[i] 存進暫存的 t,才不會在搬動時把它蓋掉。外層只跑到 i = n-2,因為前 n-1 格都挑定之後,剩下的最後一格必然已經是最大的,不用再挑。

氣泡排序(bubble sort)

相鄰兩兩比較,把大的往後推。

C++
void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {               // 前面比後面大就交換
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

把上面那個程式的 selectionSort(a, 5); 換成 bubbleSort(a, 5);,輸出一模一樣是 1 2 4 5 8——排序法不同、結果相同,差別只在過程。輪到第 i 輪時,前面已經跑過 i 輪,最後面 i 格都是最大的那幾個、確定就位了,不用再比,所以內層上界是 n - 1 - i 而不是 n - 1。這兩種排序都是 O(n2)O(n^2),這是描述演算法快慢的通用寫法,意思是資料量 10 倍、時間約 100 倍。

進階:氣泡排序可以多一個 bool swapped,某一輪完全沒交換就代表已經排好,直接 break 提早結束。

為什麼不讓你用 std::sort

實務上會直接寫 sort(a, a + n);——sort 跟 09/24 用過的 max、min 住在同一個函式庫,所以檔案最上面要多一行 #include <algorithm>,忘了會得到 error: 'sort' was not declared in this scope。兩個引數是「開頭」與「結尾的下一格」:a 是第一格的位址、a + n 是第 n 格的位址。它是 O(nlog⁡n)O(n \log n),資料一多就把手寫版甩開——但實驗課要的是手寫版,目的是練陣列操作,交作業用 sort 會沒分。

二維陣列

白話說:二維陣列就是「表格」,g[i][j] 是第 i 列第 j 行;走訪要用巢狀迴圈,外層跑列、內層跑行。

C++
int g[3][4] = {
    {1,  2,  3,  4},
    {5,  6,  7,  8},
    {9, 10, 11, 12}
};
cout << g[1][2] << '\n';        // 7:第 1 列第 2 行

初始化時每一組內層大括號就是一列,由上而下對應第 0、1、2 列,外層那組包住整個陣列。

二維陣列在記憶體裡其實是攤平的:int g[3][4] 是 12 個連續的整數,一列接一列排好(所以寫成一長串 int g[3][4] = {1,2,3,4,5,6,7,8,9,10,11,12}; 也合法,只是分組好讀得多)。

Text
   g[0][0..3]      g[1][0..3]      g[2][0..3]
 ┌──┬──┬──┬──┐  ┌──┬──┬──┬──┐  ┌──┬──┬──┬──┐
 │ 1│ 2│ 3│ 4│  │ 5│ 6│ 7│ 8│  │ 9│10│11│12│
 └──┴──┴──┴──┘  └──┴──┴──┴──┘  └──┴──┴──┴──┘

所以 g[i][j] 的實際位置是第 i * 4 + j 個格子,那個 4 就是第二維。函式只拿到第一格的位址,你不告訴它 4,它就算不出第 i 列從哪裡開始——這就是為什麼傳進函式時,第一維可以留空、第二維(以及之後每一維)的大小必須寫死:

C++
#include <iostream>
using namespace std;

void printGrid(const int g[][4], int rows) {   // 第一維留空、第二維寫死
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < 4; j++) {
            if (j > 0) cout << ' ';
            cout << g[i][j];
        }
        cout << '\n';
    }
}

int main() {
    int g[3][4] = {
        {1,  2,  3,  4},
        {5,  6,  7,  8},
        {9, 10, 11, 12}
    };
    printGrid(g, 3);      // 直接傳陣列名,第二維編譯器已經知道了
    return 0;
}

輸出:

Text
1 2 3 4
5 6 7 8
9 10 11 12

印表格時很多人圖方便寫成 cout << g[i][j] << '\t';,這樣每列尾端會多一個 tab。自己看沒差,但實驗課如果是自動比對輸出就會被判錯——用上面 if (j > 0) cout << ' '; 的寫法才安全(Q5、Q6 解答也是這樣寫)。

本週重點回顧

  • 索引 0 到 n-1,迴圈用 i < n,越界沒人擋你。
  • 陣列參數必配一個長度參數;只讀就加 const,[] 不寫大小。
  • 函式改得到原陣列,但不能回傳區域陣列——呼叫端備陣列,函式只負責填。
  • 部分填滿:迴圈上界用目前長度,不是容量。
  • 二維陣列參數的第二維必須寫死。
  • 排序要自己手寫(交作業用 std::sort 沒分);搜尋找不到就回傳 -1。

本週練習題

Q1. 讀入與反轉
讀入 n(n ≤ 100)與 n 個整數,反轉後輸出。

Text
輸入:
5
1 2 3 4 5
輸出:
5 4 3 2 1
參考解答
C++
#include <iostream>
using namespace std;

int main() {
    const int MAX = 100;
    int a[MAX], n;                  // 兩個宣告寫在一起:a 是陣列、n 是普通整數
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    for (int i = 0; i < n / 2; i++) {        // 只要跑一半
        int t = a[i];
        a[i] = a[n - 1 - i];
        a[n - 1 - i] = t;
    }
    for (int i = 0; i < n; i++) {
        if (i > 0) cout << ' ';
        cout << a[i];
    }
    cout << '\n';
    return 0;
}

int a[MAX], n; 裡的 [MAX] 只跟緊鄰在它前面的名字有關,所以 n 是普通整數、不是陣列。

Q2. 最大值與其索引
讀入 n(1 ≤ n ≤ 100)與 n 個整數,輸出最大值以及它第一次出現的索引(從 0 起算)。

Text
輸入:
6
3 9 2 9 1 4
輸出:
max = 9 at index 1
參考解答
C++
#include <iostream>
using namespace std;

int main() {
    const int MAX = 100;
    int a[MAX], n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    int best = 0;                        // 先假設第 0 格最大
    for (int i = 1; i < n; i++)
        if (a[i] > a[best]) best = i;    // 用 > 而非 >=,才會保留「第一次出現」

    cout << "max = " << a[best] << " at index " << best << '\n';
    return 0;
}

Q3. 排序後求中位數
讀入 n(1 ≤ n ≤ 100)與 n 個整數,手寫排序後輸出中位數(n 為奇數取正中間,偶數取中間兩數的平均,保留一位小數)。

Text
輸入:
4
7 1 3 9
輸出:
median = 5.0
參考解答
C++
#include <iostream>
#include <iomanip>
using namespace std;

void bubbleSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++)
        for (int j = 0; j < n - 1 - i; j++)
            if (a[j] > a[j + 1]) {
                int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t;
            }
}

int main() {
    const int MAX = 100;
    int a[MAX], n;
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    bubbleSort(a, n);

    double median;
    if (n % 2 == 1) median = a[n / 2];
    else            median = (static_cast<double>(a[n / 2 - 1]) + a[n / 2]) / 2.0;   // 先轉 double 再相加

    cout << "median = " << fixed << setprecision(1) << median << '\n';
    return 0;
}

偶數的情況先把其中一個轉成 double 再相加,不是只在最後除以 2.0:兩個 int 先相加可能溢位(兩個 15 億相加就爆了,結果會是負數),之後再怎麼除都救不回來。n ≥ 1 的限制也不是多寫的——n = 0 時 a[n / 2] 讀的是沒填過的格子。

Q4. 分數長條圖
讀入 n 與 n 個 0–100 的分數,統計各區間人數(0–59、60–69、70–79、80–89、90–100),用 * 畫出長條圖。

Text
輸入:
6
55 62 78 85 91 88
輸出:
  0- 59: *
 60- 69: *
 70- 79: *
 80- 89: **
 90-100: *
參考解答
C++
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    int n, score;
    int count[5] = {};                    // 全部初始化為 0
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> score;
        if (score < 60)      count[0]++;
        else if (score < 70) count[1]++;
        else if (score < 80) count[2]++;
        else if (score < 90) count[3]++;
        else                 count[4]++;
    }
    const int lo[5] = {0, 60, 70, 80, 90};
    const int hi[5] = {59, 69, 79, 89, 100};
    for (int i = 0; i < 5; i++) {
        cout << setw(3) << lo[i] << '-' << setw(3) << hi[i] << ": ";
        for (int j = 0; j < count[i]; j++) cout << '*';
        cout << '\n';
    }
    return 0;
}

int count[5] = {}; 這行很重要:計數用的陣列一定要歸零,否則加到垃圾值上面。

Q5. 矩陣轉置
讀入 n、m(皆 ≤ 50)與一個 n×mn \times m 的矩陣,輸出它的轉置(m×nm \times n)。

Text
輸入:
2 3
1 2 3
4 5 6
輸出:
1 4
2 5
3 6
參考解答
C++
#include <iostream>
using namespace std;

const int MAX = 50;

int main() {
    int a[MAX][MAX], n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> a[i][j];

    for (int j = 0; j < m; j++) {          // 轉置=把迴圈順序對調
        for (int i = 0; i < n; i++) {
            if (i > 0) cout << ' ';
            cout << a[i][j];
        }
        cout << '\n';
    }
    return 0;
}

Q6. 矩陣相乘(加分題/進階)
第一行讀入 n、m、p(皆 ≤ 50),接著讀入 n×mn \times m 矩陣 A 與 m×pm \times p 矩陣 B,輸出 A×BA \times B。不熟二維陣列的話,先把 Q5 練熟再回來。

Text
輸入:
2 2 2
1 2
3 4
5 6
7 8
輸出:
19 22
43 50
參考解答
C++
#include <iostream>
using namespace std;

const int MAX = 50;

int main() {
    int A[MAX][MAX], B[MAX][MAX], C[MAX][MAX];
    int n, m, p;
    cin >> n >> m >> p;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++) cin >> A[i][j];
    for (int i = 0; i < m; i++)
        for (int j = 0; j < p; j++) cin >> B[i][j];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < p; j++) {
            C[i][j] = 0;                     // 累加之前一定要歸零
            for (int k = 0; k < m; k++)      // k 掃過「A 的第 i 列」和「B 的第 j 行」
                C[i][j] += A[i][k] * B[k][j];
        }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < p; j++) {
            if (j > 0) cout << ' ';
            cout << C[i][j];
        }
        cout << '\n';
    }
    return 0;
}

矩陣相乘的定義:Cij=∑kAik×BkjC_{ij} = \sum_{k} A_{ik} \times B_{kj},也就是「A 的第 i 列」跟「B 的第 j 行」對應相乘再相加。

實驗課題型加練
以下三題的題型取自去年(2025)第 5、6 週實驗課的課堂練習(今年的投影片還沒出,題目可能會換):二維陣列當座位表、井字棋、還有「排序過程逐步印出」——要求印出每一輪,是為了確認你是自己寫排序而不是呼叫 sort。題目不是我原創的:練的東西跟去年那幾題一樣,但規則細節、輸出格式、範例資料和解答都是我自己重寫的,不是原題。Q10 的題型取自歷年考古題(範圍與欄寬改過),Q11 是我自己出的補充題。

Q7. 電影院訂票系統
座位是 10 × 10 的二維陣列,左上角是 [0][0]、右下角是 [9][9];四個角落是柱子,不開放(印成 #)。反覆讀入「列 行」,能訂就登記成 O 並印 booked (列, 行);位置已被訂、是角落或超出範圍就印 cannot book (列, 行)。讀到 -1 結束,最後印出整張座位表(空位印 .)。

Text
輸入:
2 3
2 3
0 0
9 5
-1
輸出:
booked (2, 3)
cannot book (2, 3)
cannot book (0, 0)
booked (9, 5)
   0123456789
0  #........#
1  ..........
2  ...O......
3  ..........
4  ..........
5  ..........
6  ..........
7  ..........
8  ..........
9  #....O...#
參考解答
C++
#include <iostream>
using namespace std;

const int N = 10;

void printSeats(const char seats[][N]) {
    cout << "   ";
    for (int c = 0; c < N; c++) cout << c;
    cout << '\n';
    for (int r = 0; r < N; r++) {
        cout << r << "  ";
        for (int c = 0; c < N; c++) cout << seats[r][c];
        cout << '\n';
    }
}

bool isCorner(int r, int c) {
    return (r == 0 || r == N - 1) && (c == 0 || c == N - 1);
}

int main() {
    char seats[N][N];
    for (int r = 0; r < N; r++)
        for (int c = 0; c < N; c++)
            seats[r][c] = isCorner(r, c) ? '#' : '.';

    int r, c;
    while (true) {
        cin >> r;
        if (r == -1) break;
        cin >> c;
        if (r < 0 || r >= N || c < 0 || c >= N || seats[r][c] != '.') {
            cout << "cannot book (" << r << ", " << c << ")\n";
            continue;
        }
        seats[r][c] = 'O';
        cout << "booked (" << r << ", " << c << ")\n";
    }
    printSeats(seats);
    return 0;
}

三個重點:用 char 陣列存座位狀態,一格一個字元,印表格最方便;「不能訂」的三種情況(越界、已訂、角落)先判斷越界,否則 seats[r][c] 本身就越界了;讀 -1 要在讀第二個數之前檢查,不然會多吃一個數。

Q8. 井字棋
3 × 3 棋盤的格子編號 0–8。兩人輪流輸入格子編號,第一手下 O、第二手下 X,依此輪流;下到已有棋子的格子印 occupied, choose again 並重新輸入(手數不變)。遊戲開始與每一手之後都印出盤面,每一手前面印 turn 手數: 棋子 -> 格子;有人連成一線印 O wins 或 X wins,九格下滿沒人贏印 tie。

Text
輸入: 4 0 4 2 6 3 8 5
輸出(節錄後兩手):
turn 6: X -> 8
X . O
O O .
X . X
turn 7: O -> 5
X . O
O O O
X . X
O wins
參考解答
C++
#include <iostream>
using namespace std;

void printBoard(const char b[]) {
    for (int i = 0; i < 9; i++) {
        cout << b[i];
        cout << ((i % 3 == 2) ? '\n' : ' ');
    }
}

// 回傳 'O' 或 'X' 表示誰連線;沒有人就回傳 ' '
char winner(const char b[]) {
    const int lines[8][3] = {{0,1,2},{3,4,5},{6,7,8},   // 三列
                             {0,3,6},{1,4,7},{2,5,8},   // 三行
                             {0,4,8},{2,4,6}};          // 兩條對角線
    for (int i = 0; i < 8; i++) {
        char a = b[lines[i][0]], c = b[lines[i][1]], d = b[lines[i][2]];
        if (a == c && c == d && a != '.') return a;
    }
    return ' ';
}

int main() {
    char board[9];
    for (int i = 0; i < 9; i++) board[i] = '.';
    printBoard(board);

    int turn = 1;
    while (turn <= 9) {
        char mark = (turn % 2 == 1) ? 'O' : 'X';
        int pos;
        cin >> pos;
        if (pos < 0 || pos > 8 || board[pos] != '.') {
            cout << "occupied, choose again\n";
            continue;                          // 回合數不變
        }
        board[pos] = mark;
        cout << "turn " << turn << ": " << mark << " -> " << pos << '\n';
        printBoard(board);
        char w = winner(board);
        if (w != ' ') {
            cout << w << " wins\n";
            return 0;
        }
        turn++;
    }
    cout << "tie\n";
    return 0;
}

完整輸出(輸入的第三個 4 會被拒絕):

Text
. . .
. . .
. . .
turn 1: O -> 4
. . .
. O .
. . .
turn 2: X -> 0
X . .
. O .
. . .
occupied, choose again
turn 3: O -> 2
X . O
. O .
. . .
turn 4: X -> 6
X . O
. O .
X . .
turn 5: O -> 3
X . O
O O .
X . .
turn 6: X -> 8
X . O
O O .
X . X
turn 7: O -> 5
X . O
O O O
X . X
O wins

八條連線(三列、三行、兩對角)寫成一個 lines[8][3] 常數表,winner 只要跑一個迴圈,比寫八個 if 乾淨得多,也是二維陣列「當查表用」的典型例子。盤面用一維 char board[9] 存,印的時候每三個換行,i % 3 == 2 就是「這一列的最後一格」。

Q9. 排序過程逐步印出
第一個輸入是一個字母選排序法(b 氣泡、s 選擇),第二個輸入是數量 n(1 ≤ n ≤ 100),接著 n 個整數(允許負數與重複)。這次請排成由大到小:氣泡排序每完成一輪就印一次陣列;選擇排序每實際交換一次就印一次。最後印出排好的結果。兩種排序各寫一個函式。

Text
輸入:
s 6
5 9 1 9 -3 4
輸出:
swap 0 <-> 1: 9 5 1 9 -3 4
swap 1 <-> 3: 9 9 1 5 -3 4
swap 2 <-> 3: 9 9 5 1 -3 4
swap 3 <-> 5: 9 9 5 4 -3 1
swap 4 <-> 5: 9 9 5 4 1 -3
sorted: 9 9 5 4 1 -3
Text
輸入:
b 4
1 3 0 2
輸出:
pass 1: 3 1 2 0
pass 2: 3 2 1 0
pass 3: 3 2 1 0
sorted: 3 2 1 0
參考解答
C++
#include <iostream>
using namespace std;

const int MAX = 100;

void printArray(const int a[], int n) {
    for (int i = 0; i < n; i++) cout << a[i] << (i + 1 < n ? " " : "\n");
}

// 由大到小;每完成一輪就印一次
void bubbleSort(int a[], int n) {
    for (int pass = 1; pass < n; pass++) {
        for (int j = 0; j + 1 < n - (pass - 1); j++)
            if (a[j] < a[j + 1]) { int t = a[j]; a[j] = a[j + 1]; a[j + 1] = t; }
        cout << "pass " << pass << ": ";
        printArray(a, n);
    }
}

// 由大到小;每實際交換一次就印一次
void selectionSort(int a[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int maxIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] > a[maxIdx]) maxIdx = j;
        if (maxIdx != i) {
            int t = a[i]; a[i] = a[maxIdx]; a[maxIdx] = t;
            cout << "swap " << i << " <-> " << maxIdx << ": ";
            printArray(a, n);
        }
    }
}

int main() {
    char method;
    int n, a[MAX];
    cin >> method >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
    if (method == 'b') bubbleSort(a, n);
    else               selectionSort(a, n);
    cout << "sorted: ";
    printArray(a, n);
    return 0;
}

跟正文的兩個排序只差兩件事:比較的方向反過來(正文是由小到大,這裡把 < 換成 >),以及在對的位置多一行 printArray——氣泡排序的「一輪」是外層迴圈跑完一次,選擇排序的「一次交換」是內層找完最大值之後。printArray 抽成函式是因為要印很多次;if (maxIdx != i) 讓「最大值剛好已經在該放的位置」的那輪不印。

Q10. 巴斯卡三角形
讀入 N(1 ≤ N ≤ 12),印出前 N 列的巴斯卡三角形:每列頭尾是 1,中間每個數是「左上 + 正上」。每個數用 setw(4) 印(第 12 列最大的數是 462,三位數放得下)。

Text
輸入: 6
輸出:
   1
   1   1
   1   2   1
   1   3   3   1
   1   4   6   4   1
   1   5  10  10   5   1
參考解答
C++
#include <iostream>
#include <iomanip>
using namespace std;

int main() {
    const int MAX = 12;
    int n;
    cin >> n;
    if (n < 1 || n > MAX) {
        cout << "invalid\n";
        return 0;
    }
    int tri[MAX][MAX] = {};                 // 全部先歸零
    for (int r = 0; r < n; r++) {
        tri[r][0] = tri[r][r] = 1;          // 每列頭尾都是 1
        for (int c = 1; c < r; c++)
            tri[r][c] = tri[r - 1][c - 1] + tri[r - 1][c];   // 左上 + 正上
    }
    for (int r = 0; r < n; r++) {
        for (int c = 0; c <= r; c++) cout << setw(4) << tri[r][c];
        cout << '\n';
    }
    return 0;
}

先把整張表算好再印,比「邊算邊印」好想:tri[r][c] = tri[r-1][c-1] + tri[r-1][c] 就是題目的定義。int tri[MAX][MAX] = {}; 是二維陣列全部歸零的寫法。

Q11. 最大最小交替輸出
讀入 n(1 ≤ n ≤ 100)與 n 個整數,依「最大、最小、次大、次小、…」的順序印出。請先排序再用兩個索引從兩端往中間走。

Text
輸入:
7
4 -3 9 0 7 2 -8
輸出: 9 -8 7 -3 4 0 2
參考解答
C++
#include <iostream>
using namespace std;

int main() {
    const int MAX = 100;
    int n, a[MAX];
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];

    // 選擇排序(由小到大)
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++)
            if (a[j] < a[minIdx]) minIdx = j;
        int t = a[i]; a[i] = a[minIdx]; a[minIdx] = t;
    }

    // 兩根手指:hi 從最後往前、lo 從最前往後,輪流印
    int lo = 0, hi = n - 1;
    while (lo <= hi) {
        cout << a[hi];
        if (lo < hi) cout << ' ' << a[lo];
        lo++; hi--;
        if (lo <= hi) cout << ' ';
    }
    cout << '\n';
    return 0;
}

排好之後答案就在陣列兩端,hi 從尾巴往前、lo 從頭往後,兩根手指交錯(lo <= hi 時繼續)。n 是奇數時最後只剩中間一個,if (lo < hi) 擋住不要重複印。這種「排序後兩端夾」的手法後面很多題都會再用到。


← 10/01|參數傳遞與函式重載(Ch 4) | 回總覽 | 10/15|結構與類別(Ch 5–6) →

最後更新 2026.09.12

Comments

留言

支援 Markdown、程式碼高亮(```cpp)與 LaTeX($E=mc^2$),Ctrl + Enter 送出。頭像會用你的 e-mail 去 Gravatar 找,e-mail 本身不會公開。

載入留言中…

Esc

輸入關鍵字,例如「線段樹」「Makefile」「面試」。

↑ ↓ 選擇Enter 開啟