# APCS實作題2016年3月第1題：成績指標

> 第1版：2023年2月7日
> 第2版：2023年6月6日，加上使用氣泡排序法的程式碼
> 作者：王一哲
> 題目來源：[2016年3月5日實作題第1題](https://apcs.csie.ntnu.edu.tw/wp-content/uploads/2020/10/APCS-%E5%AF%A6%E4%BD%9C%E9%A1%8C-2016.03.05.pdf)
> [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=b964)

<br />

## 題目

### 問題描述

一次考試中，於所有及格學生中獲取最低分數者最為幸運，反之，於所有不及格同學中，獲取最高分數者，可以說是最為不幸，而此二種分數，可以視為成績指標。

請你設計一支程式，讀入全班成績(人數不固定)，請對所有分數進行排序，並分別找出不及格中最高分數，以及及格中最低分數。

當找不到最低及格分數，表示對於本次考試而言，這是一個不幸之班級，此時請你印出：「worst case」；反之，當找不到最高不及格分數時，請你印出「best case」。

註：假設及格分數為 60，每筆測資皆為 0~100 間整數，且筆數未定。
<br />

### 輸入格式

第一行輸入學生人數，第二行為各學生分數(0~100 間)，分數與分數之間以一個空白間格。每一筆測資的學生人數為 1~20 的整數。
<br />

### 輸出格式

每筆測資輸出三行。
第一行由小而大印出所有成績，兩數字之間以一個空白間格，最後一個數字後無空白；
第二行印出最高不及格分數，如果全數及格時，於此行印出 best case；
第三行印出最低及格分數，當全數不及格時，於此行印出 worst case。
<br />

### 範例一：輸入

10
0 11 22 33 55 66 77 99 88 44

### 範例一：正確輸出

0 11 22 33 44 55 66 77 88 99
55
66

（說明）不及格分數最高為 55，及格分數最低為 66。
<br />

### 範例二：輸入

1
13

### 範例二：正確輸出

13
13
worst case

（說明）由於找不到最低及格分，因此第三行須印出「worst case」。
<br />

### 範例三：輸入

2
73 65

### 範例三：正確輸出

65 73
best case
65

（說明）由於找不到不及格分，因此第二行須印出「best case」。
<br />

### 評分說明

輸入包含若干筆測試資料，每一筆測試資料的執行時間限制(time limit)均為 2 秒，依正確通過測資筆數給分。
<br />

## Python 程式碼

### 方法1，使用氣泡排序法

def bubble(data):
    num = len(data)
    for i in range(num-1):
        for k in range(num-i-1):
            if data[k] > data[k+1]:
                data[k], data[k+1] = data[k+1], data[k]
    return data

N = int(input()) # 輸入學生人數 (1 ~ 20)
scores = list(map(int, input().split())) # 輸入分數，並用半型空格分隔 (1 ~ 100)
scores = bubble(scores) # 使用氣泡排序法由小到大排序

high, low = -1, 101
# 第一行：印出由小到大排列後的成績，並用半型空格分隔
for i in range(N):
    if i < N-1: print(scores[i], end=" ")
    else: print(scores[i])
    # 以上2行可以合併為 print(scores[i], end="\n" if i == N-1 else " ")
    if scores[i] < 60 and scores[i] > high: high = scores[i]
    if scores[i] >= 60 and scores[i] < low: low = scores[i]

# 第二行：印出最高不及格分數，如果全數及格時，於此行印出 best case
if high != -1: print(high)
else: print("best case")

# 第三行：印出最低及格分數，當全數不及格時，於此行印出 worst case
if low != 101: print(low)
else: print("worst case")

<br />

1. 第1 ~ 7行：自訂氣泡排序法函式 bubble，由小到大排序分數。
2. 於 ZeroJudge 測試結果，花費時間約為 27 ms，使用記憶體最多約為 3.4 MB。
<br />

氣泡排序法有兩層 for 迴圈，運作時每次會取相鄰的兩個元素比較大小，如果要由小到大排序，當左側元素大於右側元素時，將兩個元素的位置交換，當外層的 for 迴圈第一次運作完畢時，最大的元素會被移到最右側；外層的 for 迴圈第二次運作時，就不需要比較最右側的元素。假設串列內容為 \[6, 5, 4, 3, 2, 1\]，如果要使用氣泡排序法將資料由小到大排序，函式運作每次運作時i、j的值及串列的內容如下：

1. i = 0
j = 0: [5, 6, 4, 3, 2, 1]
j = 1: [5, 4, 6, 3, 2, 1]
j = 2: [5, 4, 3, 6, 2, 1]
j = 3: [5, 4, 3, 2, 6, 1]
j = 4: [5, 4, 3, 2, 1, 6]
2. i = 1
j = 0: [4, 5, 3, 2, 1, 6]
j = 1: [4, 3, 5, 2, 1, 6]
j = 2: [4, 3, 2, 5, 1, 6]
j = 3: [4, 3, 2, 1, 5, 6]
3. i = 2
j = 0: [3, 4, 2, 1, 5, 6]
j = 1: [3, 2, 4, 1, 5, 6]
j = 2: [3, 2, 1, 4, 5, 6]
4. i = 3
j = 0: [2, 3, 1, 4, 5, 6]
j = 1: [2, 1, 3, 4, 5, 6]
5. i = 4, j = 0: [1, 2, 3, 4, 5, 6]

<br /><br />

### 方法2，使用 sort 排序

N = int(input()) # 輸入學生人數 (1 ~ 20)
scores = list(map(int, input().split())) # 輸入分數，並用半型空格分隔 (1 ~ 100)
scores.sort() # 預設為由小到大，若要由大到小則要加上 reverse = True 

high, low = -1, 101
# 第一行：印出由小到大排列後的成績，並用半型空格分隔
for i in range(N):
    if i < N-1: print(scores[i], end=" ")
    else: print(scores[i])
    # 以上2行可以合併為 print(scores[i], end="\n" if i == N-1 else " ")
    if scores[i] < 60 and scores[i] > high: high = scores[i]
    if scores[i] >= 60 and scores[i] < low: low = scores[i]

# 第二行：印出最高不及格分數，如果全數及格時，於此行印出 best case
if high != -1: print(high)
else: print("best case")

# 第三行：印出最低及格分數，當全數不及格時，於此行印出 worst case
if low != 101: print(low)
else: print("worst case")

<br />

1. 第3行：使用 Python 內建的 sort 工具排序，效率優於氣泡排序法。
2. 於 ZeroJudge 測試結果，花費時間約為 20 ms，使用記憶體最多約為 3.3 MB。

<br /><br />

## C++ 程式碼

### 方法1，使用氣泡排序法

#include <iostream>
using namespace std;

// 印出陣列用的自訂函式 
void printA(int *a, int s) {
    for(int i=0; i<s; i++) {
        if(i < s-1) cout << a[i] << " ";
        else cout << a[i] << endl;
        // 以上2行可以合併為 cout << a[i] << " \n"[i == s-1];
    }
}

// 氣泡排序法 
void bubble(int data[], int num) {
    int t;
    for(int i=0; i<num-1; i++) {
        for(int j=0; j<num-i-1; j++) {
            if(data[j] > data[j+1]) {
                t = data[j];
                data[j] = data[j+1];
                data[j+1] = t;
            }
        }
    }
}

int main(int argc, char* argv[]) {
    int n, high = -1, low = 101, scores[20] = {};

    cin >> n; // 讀取資料    
    for(int i=0; i<n; i++) cin >> scores[i];
    
    bubble(scores, n); // 由小到大排序 
    
    // 找出最高不及格分數 
    for(int i=0; i<n; i++) {
        if(scores[i] < 60) {
            high = scores[i];
        } else {
            break;
        }
    }
    
    // 找出最低及格分數 
    for(int i=n-1; i>=0; i--) {
        if(scores[i] >= 60) {
            low = scores[i];
        } else {
            break;
        }
    }
    
    // 印出排序後的成績 
    printA(scores, n);
    
    // 印出最高不及格分數，若無則印出 best case 
    if(high != -1) {
        cout << high << endl;
    } else {
        cout << "best case" << endl;
    }
    
    // 印出最低及格分數，若無則印出 worst case 
    if(low != 101) {
        cout << low << endl;
    } else {
        cout << "worst case" << endl;
    }
    
    return 0;
}

<br />

1. 第12 ~ 24行：自訂函式，使用氣泡排序法由小到大排序資料。
2. 於 ZeroJudge 測試結果，花費時間約為 2 ms，使用記憶體最多，為 324 KB。

<br /><br />

### 方法2，使用 STL sort 工具排序

#include <iostream>
#include <algorithm>
using namespace std;

// 印出陣列用的自訂函式 
void printA(int *a, int s) {
    for(int i=0; i<s; i++) {
        if(i < s-1) cout << a[i] << " ";
        else cout << a[i] << endl;
        // 以上2行可以合併為 cout << a[i] << " \n"[i == s-1];
    }
}

// 由小到大排序用的比較方式 
bool cmp(int a, int b) {
    return a < b;
}

int main(int argc, char* argv[]) {
    int n, high = -1, low = 101, scores[20] = {};

    cin >> n; // 讀取資料    
    for(int i=0; i<n; i++) cin >> scores[i];
    
    sort(scores, scores+n, cmp); // 由小到大排序 
    
    // 找出最高不及格分數 
    for(int i=0; i<n; i++) {
        if(scores[i] < 60) {
            high = scores[i];
        } else {
            break;
        }
    }
    
    // 找出最低及格分數 
    for(int i=n-1; i>=0; i--) {
        if(scores[i] >= 60) {
            low = scores[i];
        } else {
            break;
        }
    }
    
    // 印出排序後的成績 
    printA(scores, n);
    
    // 印出最高不及格分數，若無則印出 best case 
    if(high != -1) {
        cout << high << endl;
    } else {
        cout << "best case" << endl;
    }
    
    // 印出最低及格分數，若無則印出 worst case 
    if(low != 101) {
        cout << low << endl;
    } else {
        cout << "worst case" << endl;
    }
    
    return 0;
}

<br />

1. 使用 STL sort 工具排序，因為預設為由小到大排序，可以刪除第15 ~ 17行，第25行改為 **sort(scores, scores+n);** 。
2. 於 ZeroJudge 測試結果，花費時間約為 3 ms，使用記憶體最多，為 324 KB。

<br /><br />

---

###### tags:`APCS`、`Python`、`C++`