UVa10774 - Repeated Josephus(數論 Math theorm、Josephus problem 約瑟夫問題)

題目大意：

我不想浪費你的時間在讀題目，這裡有 n 個人要約瑟夫問題，其中 k = 2，倖存者的位置為 x，如果 \(x != n\)，那我們將讓 \(n = x\)，n 等於 x，重新進行一次約瑟夫問題，而新的倖存者位置如果等於 n，那我們就輸出，這是第幾次執行約瑟夫問題(不包含第一次)，第 n 個人的位置是多少？

舉例：n = 5 時的約瑟夫問題為 3，\(5 != 3\)，將 \(n =3\) 執行約瑟夫問題，這次 \(n = 3, x = 3\)，重複執行了 1 次約瑟夫問題，最後一次的約瑟夫問題的 x 是 3。
因此輸出 “1 3”

題目連結

重點觀念

• 能了解此題題目，不誇張，我看了 30min
• 約瑟夫問題

分析

其實這題並沒有太大的難度，只要你了解約瑟夫問題。

之後就是判斷有沒有與 n 相同，沒有就重做，有就繼續做。

參考連結

Uva10774 - Repeated Josephus by txya900619

心得

謝謝力瑋的詳解QQQQ。
我寫這個寫得好痛苦。

我之前是有學過約瑟夫問題，但是年代久遠後似乎就忘記了，現在要重學一遍發現自己都忘得差不多，快跟一個初學者差不多了…。

我不想忘記我所學過的事物阿。

不過謝謝力瑋，我看他的程式碼才了解他的英文…。

題目程式碼

會在下面放一些簡單註解，供大家學習時參考。

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
using namespace std;
int t, repeat, kase;

int josephus(int n, int k){ //約瑟夫問題 請直接點選 重點觀念-約瑟夫問題 來了解相關知識
    int s = 0;
    for(int i = 2; i <= n; i++) s = (s+k) % i;
    return s+1;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        kase++;
        int n, survivor=-1;
        cin >> n;
        repeat = 0; //判斷總共做了幾次約瑟夫問題(不包含第一次)

        while(1){
            survivor = josephus(n,2); //表示這次的倖存者位置
            if(survivor == n) break; //如果倖存者位置與 n 相同就跳出
            n = survivor; //將 n 設定為倖存者位置
            repeat++; //約瑟夫問題將會重做一次
        }

        cout << "Case " << kase << ": " << repeat << " " << n << '\n'; //輸出答案
    }
    return 0;
}