解題 SOP

1. 題幹理解
2. 算法設計
3. 算法實作
4. 程式除錯

理解題幹

閱讀題目時，留意：

• 題幹情境
• 可利用資源
• 輸出要求
• 算法提示

算法設計

• 整理閱讀題目時的想法
• 歸納出邏輯緊密的解方
• 若算法過於複雜
  • 拿紙筆視覺化想法
  • 以人腦處理小規模測資

算法實作

• 把邏輯上的算法數學化
• 寫 code ！

題幹理解

Neoj No. 987

算法設計

1. 接收所有位置相對應的座號
2. 接收被叫到的座號
3. 找到被叫到座號的人相對應之位置
4. 找到所有在此位置之大字上的位置
5. 找到這些位置相對應座號中的最大值

算法實作

1. 接收二整數 \(m, n\)
2. 接收一整數矩陣 \(M_{m\times n}\)
3. 接收一整數 \(k\)
4. 找到 \(k\) 在 \(M_{m\times n}\) 中的位置 \((r, c)\)
5. 找出 \((r, c)\) 大十字中之最大值

\(\text{Let }S\text{ the set of numbers that}\)
\(\text{sit on the cross of }(r, c)\text{ in }M_{m\times n}\)

\(S=\{M_{ij}\}\text{, where}i, j\in N\text{ must satisfy}\)

• \((i, j)\ne(r, c)\)
• \((i=r, 0\le j<n)\lor(j=c, 0\le i<m)\)

Write Code!

#include <iostream>

using namespace std;

int main() {
    /* Reading input */
    int m, n, target, nums[100][100];
    cin >> m >> n;
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < n; ++j)
            cin >> nums[i][j];
    cin >> target;

    /* Finding (r, c) of the target */
    int r, c;
    for (int i = 0; i < m; ++i) {
        bool found = false;
        for (int j = 0; j < n; ++j)
            if (nums[i][j] == target) {
                r = i, c = j, found = true;
                break;
            }
        if (found) break;
    }

    /* Finding the max. among the numbers of those who have to stand up */
    int maxNum = 0;
    for (int i = 0; i < m; ++i) // column
        if (i != r) maxNum = max(maxNum, nums[i][c]);   
    for (int j = 0; j < m; ++j) // row
        if (j != c) maxNum = max(maxNum, nums[r][j]); 
    
    cout << maxNum << '\n';
    return 0;
}

Source Code

題幹理解

Neoj No. 938

算法設計

1. 接收迷宮資訊
2. 接收起始座標
3. 接收心中指示
4. 驗證心中指示
   • 若合法則執行
   • 不合法則撤銷，並輸出 Ooops!!!
5. 輸出最終座標

算法實作

• 接收三整數 \(x, y, z\)
• 接收 \(xyz\) 個整數 \(a_i\)
  • \(0\le i<xyz\land i\in \mathbb Z\)
  • \(a_i\in\{0, 1\}\)
  • \(a_i\) 對應 (\(i\mod x, \lfloor{i\over x}\rfloor \mod y, \lfloor {i\over xy}\rfloor\))
• 接收三整數 \(q,w,e\)
  • \(0\le q<x, 0\le w<y, 0\le e<z\)
• 接收一整數 \(m\)
  • \(1\le m\le 100\)
• 接收 \(m\) 個整數 \(k_i\)
  • \(0\le i<m\land i\in\mathbb Z\)
  • \(k_i\in\{1,2,3,4,5,6\}\)

(續上頁)

• 每接收一個 \(k_i\) ，驗證相對應指令的可行性
  • 可行：照做
  • 不可行：撤銷並印出 "Ooops!!!"
• 輸出最終位置

Write Code!

#include <iostream>

using namespace std;

bool isWall[100][100][100];
char input[1000001];

int main() {
    
    int x, y, z, q, w, e, m;
    cin >> x >> y >> z;

    cin >> input;

    int n = x*y*z;
    for (int i = 0; i < n; ++i)
        isWall[i % x][(i/x) % y][i / (x*y)] = static_cast<bool>(input[i] - '0');
    
    cin >> q >> w >> e >> m;

    for (int i = 0; i < m; ++i) {
        int k, newX = q, newY = w, newZ = e;
        cin >> k;

        if      (k == 1) ++newX;
        else if (k == 2) --newX;
        else if (k == 3) --newY;
        else if (k == 4) ++newY;
        else if (k == 5) ++newZ;
        else if (k == 6) --newZ;    

        // cout << "(" << newX << "," << newY << "," << newZ << ")" << endl;

        if (newX < 0 || newX >= x || newY < 0 || newY >= y || newZ < 0 || newZ >= z || isWall[newX][newY][newZ]) {
            cout << "Ooops!!!" << endl;
            continue;
        }

        q = newX, w = newY, e = newZ;
    }

    cout << q << " " << w << " " << e << endl;
}

Source Code