C# 實現約瑟夫環問題：10 人報數 3 出列

問題描述

10 個學生圍成一圈，編號 1-10，從 1 開始報數，報到 3 的人出列，剩餘繼續報數，求最後剩下的編號。

模擬法 (隊列/列表)

using System;
using System.Collections.Generic;

class Josephus {
    static void Main() {
        int n = 10, k = 3;
        var people = new List();
        for (int i = 1; i <= n; i++) people.Add(i);

        int index = 0;
        while (people.Count > 1) {
            index = (index + k - 1) % people.Count;
            Console.WriteLine($"出列: {people[index]}");
            people.RemoveAt(index);
        }
        Console.WriteLine($"最後剩下: {people[0]}");
    }
}

數學遞推法 O(n) 時間 O(1) 空間

遞推公式：f(1) = 0; f(i) = (f(i-1) + k) % i (0-based 索引)

static int JosephusMath(int n, int k) {
    int result = 0; // f(1) = 0
    for (int i = 2; i <= n; i++) {
        result = (result + k) % i;
    }
    return result + 1; // 轉 1-based 編號
}

// 驗證
Console.WriteLine(JosephusMath(10, 3)); // 輸出 4

遞歸版本

static int JosephusRecursive(int n, int k) {
    if (n == 1) return 0;
    return (JosephusRecursive(n - 1, k) + k) % n;
}

通用擴展：任意起始位置、步長、輸出順序

public static class JosephusExtensions {
    public static IEnumerable EliminationOrder(this IEnumerable source, int step) {
        var list = new List(source);
        int idx = 0;
        while (list.Count > 0) {
            idx = (idx + step - 1) % list.Count;
            yield return list[idx];
            list.RemoveAt(idx);
        }
    }

    public static int LastRemaining(this IEnumerable source, int step) {
        int result = 0;
        int count = 0;
        foreach (var _ in source) {
            count++;
            result = (result + step) % count;
        }
        return result + 1; // 1-based
    }
}

// 使用
var order = Enumerable.Range(1, 10).EliminationOrder(3).ToList();
Console.WriteLine("出列順序: " + string.Join(", ", order));
Console.WriteLine("倖存者: " + Enumerable.Range(1, 10).LastRemaining(3));

驗證結果

n=10, k=3 → 出列順序: 3, 6, 9, 2, 7, 1, 8, 5, 10 → **倖存者: 4**

總結

模擬法直觀易懂，適合輸出過程；數學遞推法極致高效，適合大數據量 (如 n=10^7)。面試常考遞推公式推導與 0/1-based 索引轉換。