常用演算法：C# 約瑟夫環問題實作

問題描述

n 人圍成一圈，從第 start 人開始報數，數到 m 的人出列，下一人繼續從 1 開始報數，循環至所有人出列。依出列順序輸出序號。

演算法實作

/// 

/// 約瑟夫環計算
/// 
/// 總人數
/// 起始位置（1-based）
/// 報數間隔
/// 出列順序陣列（索引 0 為第一個出列）
public int[] Josephus(int total, int start, int step) {
    int[] result = new int[total];
    int[] people = new int[total];
    for (int i = 0; i < total; i++) people[i] = i; // 0-based 編號

    int idx = (start - 1 + step - 1) % total; // 第一個出列索引
    for (int i = total, k = 0; i > 0; i--, k++) {
        result[k] = people[idx];
        // 將陣列後段前移覆蓋被移除元素
        for (int j = idx + 1; j < i; j++) people[j - 1] = people[j];
        // 計算下一個出列索引
        if (i > 1) idx = (idx + step - 1) % i;
    }
    return result;
}

程式碼解析

• people 陣列模擬圓圈，動態縮減。
• idx 為當前出列位置，每輪以 (idx + step - 1) % 剩餘人數 計算下一位置。
• 移除元素後，後續元素前移填補空缺，維持陣列緊湊。
• 回傳陣列依序為出列順序（0-based 編號），若需 1-based 輸出請自行 +1。

測試範例

int[] order = Josephus(7, 1, 3); // 7人，從1開始，每3個出列
Console.WriteLine(string.Join(", ", order));
// 輸出: 2, 5, 1, 6, 4, 0, 3 (0-based)

複雜度分析

• 時間複雜度：O(n²) —— 每次移除需移動陣列元素。
• 空間複雜度：O(n) —— 儲存人員陣列與結果陣列。
• 若 n 極大，可改用鏈表或數學遞推公式優化至 O(n) 或 O(k log n)。