理解 C++ 面向物件抽象理論：以約瑟夫斯問題對比陣列、結構體與類別實作

前言

約瑟夫斯問題 (Josephus Problem) 是經典循環淘汰遊戲：N 人圍圈，每數到 M 者出列，求倖存者。本文以三種資料結構實作對比，展示面向物件抽象如何提升可讀性、可維護性與擴充性。

問題定義

• 輸入：總人數 N、間隔 M
• 過程：從 1 開始報數，報到 M 者離開，剩餘者繼續報數
• 輸出：最後倖存者編號

一、陣列實作：最原始但效率低

void JosephusArray(int N, int M) {
    std::vector a(N);
    for (int i = 0; i < N; ++i) a[i] = i + 1; // 編號 1..N

    int pos = -1, eliminated = 0;
    while (eliminated < N - 1) {
        for (int step = 0; step < M; ) {
            pos = (pos + 1) % N;           // 環狀索引
            if (a[pos] != 0) ++step;       // 跳過已淘汰 (0 標記)
        }
        std::cout << a[pos] << " eliminated\n";
        a[pos] = 0;                        // 標記淘汰
        ++eliminated;
    }
    // 找倖存者
    for (int v : a) if (v != 0) { std::cout << "Survivor: " << v; break; }
}

缺點分析

• 邏輯與資料糅合：淘汰標記 (0) 混入資料域，語意不清
• O(N×M) 時間：每步需掃描跳過 0，大 N/M 時極慢
• 難以擴充：加入性別、姓名、淘汰順序記錄等需大改結構
• 無封裝：全域函數操作裸露資料

二、結構體實作：資料聚合但無行為

struct Person {
    int id;
    bool alive;
};

void JosephusStruct(int N, int M) {
    std::vector circle(N);
    for (int i = 0; i < N; ++i) circle[i] = {i+1, true};

    int pos = -1, aliveCount = N;
    while (aliveCount > 1) {
        for (int step = 0; step < M; ) {
            pos = (pos + 1) % N;
            if (circle[pos].alive) ++step;
        }
        circle[pos].alive = false;
        std::cout << circle[pos].id << " eliminated\n";
        --aliveCount;
    }
    for (auto& p : circle) if (p.alive) std::cout << "Survivor: " << p.id;
}

改進與殘留問題

• ✅ 資料語意清晰 (alive 替代魔術數 0)
• ✅ 易擴充欄位 (姓名、屬性)
• ❌ 邏輯仍為程序式函數操作被動資料
• ❌ 環狀遍歷邏輯重複 (可抽象為迭代器)
• ❌ 無不變式保護 (外部可任意修改 alive)

三、類別實作：封裝、抽象與多型

核心抽象：循環鏈表節點

class JosephusNode {
    int id;
    JosephusNode* next;
    bool alive;
public:
    JosephusNode(int id_) : id(id_), next(nullptr), alive(true) {}

    int GetId() const { return id; }
    bool IsAlive() const { return alive; }
    void Eliminate() { alive = false; }

    JosephusNode* Next() const { return next; }
    void LinkNext(JosephusNode* n) { next = n; }

    // 找下一個存活節點 (封裝遍歷邏輯)
    JosephusNode* NextAlive() const {
        JosephusNode* cur = next;
        while (!cur->alive) cur = cur->next;
        return cur;
    }
};

遊戲控制類別

class JosephusGame {
    JosephusNode* head;
    int n, m;
public:
    JosephusGame(int N, int M) : n(N), m(M) {
        // 建立循環鏈表
        head = new JosephusNode(1);
        JosephusNode* prev = head;
        for (int i = 2; i <= N; ++i) {
            JosephusNode* cur = new JosephusNode(i);
            prev->LinkNext(cur);
            prev = cur;
        }
        prev->LinkNext(head); // 閉環
    }

    ~JosephusGame() {
        // 釋放鏈表記憶體
        JosephusNode* cur = head;
        do {
            JosephusNode* next = cur->Next();
            delete cur;
            cur = next;
        } while (cur != head);
    }

    int Play() {
        JosephusNode* cur = head;
        int aliveCount = n;
        while (aliveCount > 1) {
            // 移動 m-1 步 (當前算 1)
            for (int i = 1; i < m; ++i)
                cur = cur->NextAlive();

            JosephusNode* victim = cur->NextAlive();
            std::cout << "Eliminated: " << victim->GetId() << "\n";
            victim->Eliminate();
            --aliveCount;
            cur = victim->NextAlive(); // 下一輪從下一位開始
        }
        return cur->GetId();
    }
};

使用範例

int main() {
    JosephusGame game(41, 3); // 經典 41 人、間隔 3
    int survivor = game.Play();
    std::cout << "Survivor: " << survivor << "\n"; // 輸出 31
    return 0;
}

四、三版本對比總結

五、進階優化：O(N) 數學解法

// 遞推公式：f(1) = 0; f(i) = (f(i-1) + M) % i
// 最後倖存者編號 = f(N) + 1 (0-based → 1-based)
int JosephusMath(int N, int M) {
    int result = 0;
    for (int i = 2; i <= N; ++i)
        result = (result + M) % i;
    return result + 1;
}

此為純演算法優化，不涉及資料結構抽象。實務中若需記錄淘汰順序、支援動態增減人員、視覺化動畫，類別版本優勢明顯。

結語

面向物件抽象不只是「加上 class 關鍵字」，而是識別領域概念、封裝不變式、定義清晰介面、分離關注點。約瑟夫斯問題展示：從陣列的索引運算，到結構體的欄位語意，再到類別的行為封裝與 RAII 管理，每一步都讓程式碼更接近問題領域，而非機器細節。這正是 OOP 的核心價值。