C# 實作雙向循環鏈表解決約瑟夫斯問題 (Josephus Problem)

題目背景

經典約瑟夫斯問題：N 人圍成一圈，從第 1 人開始報數，報到 3 的人出列，剩餘繼續報數，求最後倖存者編號。本文使用泛型雙向循環鏈表實現，展示資料結構在演算法題中的應用。

節點類別：雙向鏈表節點

public class DoubleLinkNode
{
    public T Value { get; set; }
    public DoubleLinkNode Next { get; set; }
    public DoubleLinkNode Previous { get; set; }

    public DoubleLinkNode() { }
    public DoubleLinkNode(T value) => Value = value;

    public override string ToString() => Value?.ToString() ?? "null";
}

雙向循環鏈表類別

public class CircularDoublyLinkedList : IEnumerable
{
    public DoubleLinkNode First { get; private set; }
    public DoubleLinkNode Last { get; private set; }
    public int Count { get; private set; }

    private DoubleLinkNode _current;
    private int _currentIndex;

    // 索引器：雙向搜尋優化 (從較近的一端開始)
    public DoubleLinkNode this[int index]
    {
        get
        {
            if (index < 0 || index >= Count) throw new ArgumentOutOfRangeException();
            
            if (Count - index < index) // 從尾部反向較近
            {
                _current = Last;
                _currentIndex = Count - 1;
                while (_currentIndex > index)
                {
                    _current = _current.Previous;
                    _currentIndex--;
                }
            }
            else // 從頭部正向較近
            {
                _current = First;
                _currentIndex = 0;
                while (_currentIndex < index)
                {
                    _current = _current.Next;
                    _currentIndex++;
                }
            }
            return _current;
        }
    }

    // 在尾部新增節點 (維持循環)
    public void AddLast(DoubleLinkNode node)
    {
        if (First == null)
        {
            First = Last = node;
            node.Next = node.Previous = node; // 指向自己
        }
        else
        {
            node.Previous = Last;
            node.Next = First;
            Last.Next = node;
            First.Previous = node;
            Last = node;
        }
        Count++;
    }

    public void AddLast(T value) => AddLast(new DoubleLinkNode(value));

    // 移除節點 (自動修復鏈結)
    public void Remove(DoubleLinkNode node)
    {
        if (Count == 0) return;
        
        node.Previous.Next = node.Next;
        node.Next.Previous = node.Previous;

        if (node == First) First = node.Next;
        if (node == Last) Last = node.Previous;
        if (Count == 1) First = Last = null;

        Count--;
    }

    public void Remove(T value)
    {
        var node = Find(n => EqualityComparer.Default.Equals(n.Value, value));
        if (node != null) Remove(node);
    }

    // 尋找符合條件的第一個節點
    public DoubleLinkNode Find(Predicate> match)
    {
        if (First == null) return null;
        
        var current = First;
        for (int i = 0; i < Count; i++)
        {
            if (match(current)) return current;
            current = current.Next;
        }
        return null;
    }

    // IEnumerable 實作
    public IEnumerator GetEnumerator()
    {
        var current = First;
        for (int i = 0; i < Count; i++)
        {
            yield return current.Value;
            current = current.Next;
        }
    }

    System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator() 
        => GetEnumerator();

    public override string ToString()
    {
        var sb = new System.Text.StringBuilder();
        var current = First;
        for (int i = 0; i < Count; i++)
        {
            sb.AppendLine($"Node:{current.Value} Next:{current.Next.Value} Prev:{current.Previous.Value}");
            current = current.Next;
        }
        return sb.ToString();
    }
}

解決約瑟夫斯問題

public class Person
{
    public int Id { get; }
    public Person(int id) => Id = id;
    public override string ToString() => $"Person #{Id}";
}

class Program
{
    static void Main()
    {
        const int TOTAL_PEOPLE = 17;
        const int STEP = 3;

        var circle = new CircularDoublyLinkedList();
        for (int i = 1; i <= TOTAL_PEOPLE; i++)
            circle.AddLast(new Person(i));

        var current = circle.First;
        int count = 1;

        Console.WriteLine($"約瑟夫斯問題：{TOTAL_PEOPLE} 人，報數 {STEP} 出列");
        Console.WriteLine("----------------------------");

        while (circle.Count > 1)
        {
            Console.WriteLine($"{current.Value} 報數：{count}");
            
            if (count % STEP == 0)
            {
                var toRemove = current;
                current = current.Next; // 先移動到下一個，再移除當前
                circle.Remove(toRemove);
                Console.WriteLine($"  >>> {toRemove.Value} 出列！剩餘 {circle.Count} 人");
            }
            else
            {
                current = current.Next;
            }
            count++;
        }

        Console.WriteLine("----------------------------");
        Console.WriteLine($"最後倖存者：{circle.First.Value}");
        Console.ReadKey();
    }
}

執行結果範例

約瑟夫斯問題：17 人，報數 3 出列
----------------------------
Person #1 報數：1
Person #2 報數：2
Person #3 報數：3
  >>> Person #3 出列！剩餘 16 人
Person #4 報數：4
Person #5 報數：5
Person #6 報數：6
  >>> Person #6 出列！剩餘 15 人
...
最後倖存者：Person #10

資料結構選擇分析

優化方向

• 數學解法：f(n,k) = (f(n-1,k) + k) % n 遞推公式 O(N) 時間 O(1) 空間，無需資料結構。
• 陣列模擬：bool[] alive + 索引跳躍，空間 O(N) 但快取友善。
• 平衡樹 / 線段樹：支援動態增刪與第 K 個查詢，O(log N)。