第 14 周作業講解

第 14 周作業講解

2024 - 無聊的小明 (遞迴解)

解題思路

看個例子：

排列 123
紀錄「可使用的數字」
一開始三個數字都可使用
選擇一個數字後就不能再使用
- 選擇 1 後可使用的數字就剩 2 3
每一層的選法都是從當前可使用的數字中小的開始選
選到沒有數字可以使用時就輸出

Image Not Showing Possible Reasons

The image file may be corrupted
The server hosting the image is unavailable
The image path is incorrect
The image format is not supported

Learn More →

遞迴問題：

大問題：排列 n 個可使用的數字
小問題：把一個數字選出來後，排列剩下的 n - 1 個數字
終止條件：沒有可使用的數字時，直接輸出
- 為了能輸出所選擇的數字，我們還要按照順序紀錄「目前選了哪些數字」

程式框架

使用一個陣列來記錄可以使用的數字
- usable[3] 表示 3 這個數字可不可以使用
使用另一個陣列來記錄目前所選擇的數字
宣告一個遞迴函數，傳入「目前要排第幾位數字」和「最多可以選幾個數字」
- 這樣判端終止條件比較方便
- 為了方便，位數從左到右分別是 0、1、2、3…

bool usable[10] = {0};        // 可以使用的數字
int current_number[10] = {0}; // 目前所選擇的數字

void permutate(int cur_bit, int max_n)  {
}

判斷終止條件

如果目前已經選了 n 個數字，那就可以直接輸出了，因為一定沒有數字可以選了
輸出時，如果第 0 位 (最左邊的數字) 是 0，就跳過不輸出，直接 return
將 current_number 中的數字一個個輸出

if (cur_bit == max_n) {
    if (current_number[0] == 0)
        return;

    for (int i = 0; i < max_n; i++)
        cout << current_number[i];
    cout << endl;
    return;
}

拆分問題

從 0 開始找，如果當前的數字可以使用，就把它放到已選的數字中，並且標記爲不可使用
傳入下一層的函數，繼續排列後面的數字
下一層排完後，把當前的數字重新標記爲可以使用

for (int i = 0; i < 10; i++) {
    if (usable[i]) {
        current_number[cur_bit] = i;      // 放入目前所選擇的數字中
        usable[i] = false;                // 標記為不可使用

        permutate(cur_bit + 1, max_n);    // 排下一位

        usable[i] = true;                 // 重新標記為可以使用
    }
}

完整程式碼












































#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool usable[10] = {0};
int current_number[10] = {0};

void permutate(int cur_bit, int max_n) {
    if (cur_bit == max_n) {
        if (current_number[0] == 0)
            return;
        
        for (int i = 0; i < max_n; i++)
            cout << current_number[i];
        cout << endl;
        return;
    }

    for (int i = 0; i < 10; i++) {
        if (usable[i]) {
            current_number[cur_bit] = i;
            usable[i] = false;

            permutate(cur_bit + 1, max_n);

            usable[i] = true;
        }
    }
}

int main() {
    int n;
    cin >> n;

    for (int i = 0; i < n; i++) {
        int t;
        cin >> t;
        usable[t] = true;    // 標記爲可以使用
    }

    permutate(0, n);         // 排第 0 位，最多排 n 個數字
}

2024 - 無聊的小明 (STL解)

解題思路

標準函式庫中的 next_permutation 函數可以把一個 vector 中的數字轉成下一個排列，例如輸入的 vector 是 {2, 1, 3}，呼叫該函數可以把這個 vector 變成 {2, 3, 1}
- 如果當前的排列是最後一個排列（如：{3, 2, 1}），該函數會回傳 false
標準函式庫中的 sort 函數可以把 vector 由小排到大

搭配上面提到的兩個函數，我們可以構思出這樣的解法：

先把輸入由小到大排
不斷的輸出 vector 中的值並將它排成下一個排列
重複直到 next_permutation 回傳 false

程式框架

sort(a.begin(), a.end());

do {
    if (a[0] == 0)
        continue;

    for (auto t : a)
        cout << t;
    cout << endl;
} while (next_permutation(a.begin(), a.end()));

完整程式碼

























#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> a(n);
    for (auto &t : a)
        cin >> t;

    sort(a.begin(), a.end());

    do {
        if (a[0] == 0)
            continue;

        for (auto t : a)
            cout << t;
        cout << endl;
    } while (next_permutation(a.begin(), a.end()));
}

448 - 麻將排序問題

解題思路

用數字來表示牌
- 排序只在乎大小關係，所以每張牌的數字你想怎麼定都可以，只要大小關係對了就行
可以把餅（Ｂ）、條（Ｔ）、萬（Ｗ）當成單位:
- 1B = 1
- 1T = 10
- 1W = 100
大字 EE, SS, WW, NN, CC, FF, BB 就分別是 1000 ~ 7000
排序時就將牌名轉成數字後做比較

程式框架

根據上面的邏輯，寫出一個函數來轉換牌名與數字：

int getLevel(string &str) {
    int level = 0;
    if (isdigit(str[0])) {
        int d = str[0] - '0';
        switch (str[1]) {
            case 'T':
                d *= 10;
                break;
            case 'W':
                d *= 100;
                break;
        }
        level = d;
    } else {                // 大字
        int d = 1;
        switch (str[0]) {
            case 'E':
                break;
            case 'S':
                d = 2;
                break;
            case 'W':
                d = 3;
                break;
            case 'N':
                d = 4;
                break;
            case 'C':
                d = 5;
                break;
            case 'F':
                d = 6;
                break;
            case 'B':
                d = 7;
                break;
        }
        level = d * 1000;
    }
    return level;
}

而在排序時，可以使用 STL 的 sort 函數，為了讓他按照我們的意思排序，我們要自訂一個比較函數，用來比較兩個字串：

bool cmp(string &a, string &b) {
    return getLevel(a) < getLevel(b);
}

這個比較函數回傳值的意義可以想成：當他回傳 true 時，a 在前、b 在後的順序是正確的
如果他回傳 false，代表 b 應該要放在 a 前面

那在呼叫 sort 函數時，把我們的 cmp 放第三個參數傳進去即可

sort(cards.begin(), cards.end(), cmp);

完整程式碼








































































#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

int getLevel(string &str) {
    int level = 0;
    if (isdigit(str[0])) {
        int d = str[0] - '0';
        switch (str[1]) {
            case 'T':
                d *= 10;
                break;
            case 'W':
                d *= 100;
                break;
        }
        level = d;
    } else {
        int d = 1;
        switch (str[0]) {
            case 'E':
                break;
            case 'S':
                d = 2;
                break;
            case 'W':
                d = 3;
                break;
            case 'N':
                d = 4;
                break;
            case 'C':
                d = 5;
                break;
            case 'F':
                d = 6;
                break;
            case 'B':
                d = 7;
                break;
        }
        level = d*1000;
    }
    return level;
}

bool cmp(string &a, string &b) {
    return getLevel(a) < getLevel(b);
}

int main() {
    int n;
    cin >> n;

    vector<string> cards;
    cards.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> cards[i];
    }

    sort(cards.begin(), cards.end(), cmp);

    for (int i = 0; i < n; i++) {
        cout << cards[i];
        if (i != n - 1)
            cout << ' ';
    }
    cout << endl;
}