系列與本頁目錄
- 總覽
- 環境設置:把工具鏈準備好
- 09/10|課程介紹與環境暖身
- 09/17|C++ 基礎(Ch 1)
- 09/24|流程控制與函式基礎(Ch 2、Ch 3)
- 10/01|參數傳遞與函式重載(Ch 4)
- 10/08|陣列(Ch 5)
- 10/15|結構與類別(Ch 5–6)
- 10/22|類別與建構子(Ch 6–7)
- 10/29|vector 與運算子重載入門(Ch 7)
- 11/05|期中上機考(範圍 Ch 1–6)
- 11/12|運算子重載、friend 與 string(Ch 8、Ch 9)
- 11/19|指標、動態記憶體與 C 風格字串(Ch 9、Ch 10)
- 11/26|分離編譯與命名空間(Ch 11)
- 12/03|檔案輸入輸出(Ch 12)
- 12/10|繼承(Ch 14)
- 12/17|期末筆試(範圍 Ch 1–12、Ch 14)
- 12/24|期末上機考(範圍 Ch 1–12、Ch 14)
- 附錄:編譯選項、Makefile、錯誤訊息與名詞速查
← 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 |
這週要會什麼
陣列宣告 → 索引與越界 → 用迴圈掃描 → 陣列與函式 → 部分填滿 → 搜尋與排序 → 二維陣列陣列是什麼
白話說:陣列就是一排編號的格子,每一格放同一種型別的資料。宣告 int a[5]; 就是要了五個連續的整數格子,編號 0 到 4。
a[0] a[1] a[2] a[3] a[4]
┌─────┬─────┬─────┬─────┬─────┐
a │ 3 │ 1 │ 4 │ 1 │ 5 │
└─────┴─────┴─────┴─────┴─────┘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 { ... }; 同一個道理)。
初始化的幾種寫法:
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)。
用迴圈掃陣列
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 forfor (int x : a) 讀作「對 a 裡的每一個元素 x」。注意:x 是複製品,改 x 不會改到陣列;要改就寫 for (int& x : a) x *= 2;——這個 & 跟 10/01 的參考參數是同一個,x 不是複製品,而是陣列裡那一格的別名。
用 const int N 而不是直接寫 5:陣列大小改成 10 時只要改一個地方,迴圈條件自動跟著對。
陣列傳進函式
陣列傳進函式時不會複製整個陣列,傳的是「第一格的位址」——位址就是那格記憶體的門牌號碼(細節等 11/19 講指標再展開)。函式拿到的是第一格的門牌,不是整排格子的影本——它照門牌找得到第一格、也改得動裡面的值,但沒人告訴它這排總共有幾格。後果有三個:
- 函式可以改到原陣列(就算沒寫
&)。 - 函式不知道陣列多長,所以一定要額外傳長度。
- 函式裡不能對陣列參數用 range-based for:
for (int x : a)會編譯失敗,訊息是'begin' was not declared in this scope。原因就是第 2 點——編譯器不知道該在哪裡停。函式裡一律寫for (int i = 0; i < n; i++)。
#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;
}輸出:
15
30const int a[] 就是 10/01 的 const——對讀者和編譯器宣告「只讀不寫」,手滑寫進去會直接編譯失敗。參數列裡的 [] 寫了大小也沒用(編譯器會忽略它,反而騙了讀程式的人),所以一律留空;這跟雷區 ② 的「宣告陣列時大小必須是常數」是兩回事。
為什麼不能回傳區域陣列
同一個原因還會咬你一口:陣列不能直接回傳。這樣寫會出事:
int* makeArray() { // int* 是「存放位址」的型別,叫指標,11/19 才正式教
int a[5] = {1, 2, 3, 4, 5};
return a; // 陣列名字單獨出現時值就是第一格的位址,所以型別是 int*
} // 但 a 在函式結束的瞬間就消失了編譯器會給 warning: address of local variable 'a' returned,執行結果是垃圾值或當掉——區域陣列在函式結束時就被回收,回傳的位址指向一塊已經不屬於你的記憶體。標準作法是由呼叫端準備好陣列,函式只負責填:
#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;
}輸出:
0 1 4 9 16另一種作法是用 new 在「函式結束也不會消失」的地方配置記憶體,那要等到指標那一節才會教。
部分填滿的陣列
陣列大小必須是常數(雷區 ②),可是要讀幾筆資料常常執行時才知道——只好先開夠大的 100 格,實際可能只用 47 格。做法是另外用一個變數記住有效長度:容量(總共幾格)和目前長度(用了幾格)是兩個不同的數字,傳進函式時兩個都要傳。
#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;
}輸出:
10 20 30參數列裡 used 前面那個 & 就是 10/01 的傳參考:push 改掉「用了幾格」要讓 main 看得見,所以必須傳參考;capacity、value 只是讀進來看,傳值就夠。a 沒寫 & 也改得到則是另一回事——陣列傳的是第一格位址,兩者別混著記。
本週練習題 Q1–Q3 用的就是這個模式:宣告 a[100]、讀進 n 個,之後每個迴圈的上界都是 n 而不是 100。
搜尋與排序
線性搜尋
#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;
}輸出:
2 -1回傳 -1 代表「找不到」是很常見的約定,因為 -1 不可能是合法索引。
選擇排序(selection sort)
每一輪找出剩下元素中最小的,換到前面。
#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;
}輸出:
1 2 4 5 8過程長這樣:
{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)
相鄰兩兩比較,把大的往後推。
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。這兩種排序都是
進階:氣泡排序可以多一個
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 格的位址。它是 sort 會沒分。
二維陣列
白話說:二維陣列就是「表格」,g[i][j] 是第 i 列第 j 行;走訪要用巢狀迴圈,外層跑列、內層跑行。
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}; 也合法,只是分組好讀得多)。
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 列從哪裡開始——這就是為什麼傳進函式時,第一維可以留空、第二維(以及之後每一維)的大小必須寫死:
#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;
}輸出:
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 個整數,反轉後輸出。
輸入:
5
1 2 3 4 5
輸出:
5 4 3 2 1參考解答
#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 起算)。
輸入:
6
3 9 2 9 1 4
輸出:
max = 9 at index 1參考解答
#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 為奇數取正中間,偶數取中間兩數的平均,保留一位小數)。
輸入:
4
7 1 3 9
輸出:
median = 5.0參考解答
#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),用 * 畫出長條圖。
輸入:
6
55 62 78 85 91 88
輸出:
0- 59: *
60- 69: *
70- 79: *
80- 89: **
90-100: *參考解答
#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)與一個
輸入:
2 3
1 2 3
4 5 6
輸出:
1 4
2 5
3 6參考解答
#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),接著讀入
輸入:
2 2 2
1 2
3 4
5 6
7 8
輸出:
19 22
43 50參考解答
#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;
}矩陣相乘的定義:
實驗課題型加練
以下三題的題型取自去年(2025)第 5、6 週實驗課的課堂練習(今年的投影片還沒出,題目可能會換):二維陣列當座位表、井字棋、還有「排序過程逐步印出」——要求印出每一輪,是為了確認你是自己寫排序而不是呼叫 sort。題目不是我原創的:練的東西跟去年那幾題一樣,但規則細節、輸出格式、範例資料和解答都是我自己重寫的,不是原題。Q10 的題型取自歷年考古題(範圍與欄寬改過),Q11 是我自己出的補充題。
Q7. 電影院訂票系統
座位是 10 × 10 的二維陣列,左上角是 [0][0]、右下角是 [9][9];四個角落是柱子,不開放(印成 #)。反覆讀入「列 行」,能訂就登記成 O 並印 booked (列, 行);位置已被訂、是角落或超出範圍就印 cannot book (列, 行)。讀到 -1 結束,最後印出整張座位表(空位印 .)。
輸入:
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...#參考解答
#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。
輸入: 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參考解答
#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 會被拒絕):
. . .
. . .
. . .
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 個整數(允許負數與重複)。這次請排成由大到小:氣泡排序每完成一輪就印一次陣列;選擇排序每實際交換一次就印一次。最後印出排好的結果。兩種排序各寫一個函式。
輸入:
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輸入:
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參考解答
#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,三位數放得下)。
輸入: 6
輸出:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1參考解答
#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 個整數,依「最大、最小、次大、次小、…」的順序印出。請先排序再用兩個索引從兩端往中間走。
輸入:
7
4 -3 9 0 7 2 -8
輸出: 9 -8 7 -3 4 0 2參考解答
#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) 擋住不要重複印。這種「排序後兩端夾」的手法後面很多題都會再用到。
載入留言中…