UVa11531 - Last Man Standing(數論 Math theorm、Josephus problem 約瑟夫問題)

題目大意

約瑟夫問題，給你 n,k，總共有 n 個人，數到第 k 個人，那人則必須離開。

試問，最後一個人會是離開的人是誰？

題目連結

重點觀念

• 約瑟夫問題

分析

只要你了解約瑟夫問題，這題基本上小學生都會寫。

實現約瑟夫問題的遞迴公式即可。

心得

我學約瑟夫問題學了 4hr，現在來一題簡單的，有點開心嗎(? XD。

題目程式碼

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

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

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> n >> k;
        int survivor = 0;  //約瑟夫問題 請直接點選 重點觀念-約瑟夫問題 來了解相關知識
        for(int i = 2; i <= n; i++) survivor = (survivor + k) % i;
        survivor++;
        cout << "Case " << ++kase << ": " << survivor << '\n'; //輸出答案
    }
    return 0;
}