Uva10774 - Repeated Josephus

題目大意

有 n 個人，每個人被編號成 1 ~ n 號，我們每 2 個人就殺一個人
ex. 從 1 開始 2 殺掉 3 保留 4 殺掉…
然後將最後生存下來的編號，作為新的 n ，直到舊的 n == 最後生存下來的編號為止，並輸出跑過的回數與此編號。

重點觀念

• Joseph Ring
  • 參考資料
  • 數學: f[1] = 0, f[i] = (f[i-1]+k)%i (k 是 每幾個人殺掉, 求到 f[n] 再加一即是答案)

分析

• 因為只需要最後一個人的號碼，可以直接以數學求解

程式題目碼

#include <iostream>

using namespace std;

int josephus(int n, int k) {
    int f = 0;
    for (int i = 2; i <= n; i++) {
        f = (f + k) % i;
    }

    return f + 1;
}

int main() {
    int t;
    cin >> t;

    for (int i = 1; i <= t; i++) {
        int n;
        cin >> n;

        int round = 0;

        while (++round) {
            int survivor = josephus(n, 2);
            if (survivor == n) {
                break;
            }
            n = survivor;
        }

        cout << "Case " << i << ": " << round - 1 << " " << n << endl;
    }

    return 0;
}