约瑟夫環問題：C++ 實現 10 人報數 3 出列求最後編號

問題描述

10 個小朋友圍圈報數，報到 3 的出列，循環至剩最後一人，求其原始編號。

數學建模

經典 Josephus 問題，遞推公式：f(1)=0; f(i)=(f(i-1)+k)%i，最終答案 +1（編號從 1 開始）。

C++ 代碼（模擬法 + 數學法）

#include <iostream>
#include <vector>
using namespace std;

// 模擬法
int josephus_sim(int n, int k) {
    vector a(n);
    iota(a.begin(), a.end(), 1);
    int idx = 0;
    while (a.size() > 1) {
        idx = (idx + k - 1) % a.size();
        a.erase(a.begin() + idx);
    }
    return a[0];
}

// 數學法 O(n)
int josephus_math(int n, int k) {
    int res = 0;
    for (int i = 2; i <= n; i++)
        res = (res + k) % i;
    return res + 1;
}

int main() {
    cout << "模擬法結果: " << josephus_sim(10, 3) << endl; // 4
    cout << "數學法結果: " << josephus_math(10, 3) << endl; // 4
    return 0;
}

參考資料

Josephus 問題詳細推導與多語言實現