http://oj.acm.zstu.edu.cn/JudgeOnline/problem.php?id=4442

題解：經(jīng)典的約瑟夫環(huán)問題

詳細信息參考https://blog.csdn.net/tingyun_say/article/details/52343897

C++版本一

/* *@Author: STZG *@Language: C++ */ #include <bits/stdc++.h> #include<iostream> #include<algorithm> #include<cstdlib> #include<cstring> #include<cstdio> #include<string> #include<vector> #include<bitset> #include<queue> #include<deque> #include<stack> #include<cmath> #include<list> #include<map> #include<set> //#define DEBUGusing namespace std; typedef long long ll; const int N=10000; const double PI = acos(-1.0); const double EXP = 1E-8; const int INF = 0x3f3f3f3f; int t,n,m; int yuesefu(int n,int m){if(n == 1){return 0; //這里返回下標,從0開始，只有一個元素就是剩余的元素0}else{return (yuesefu(n-1,m) + m) % n; //我們傳入的n是總共多少個數(shù)} }int main() { #ifdef DEBUGfreopen("input.in", "r", stdin);//freopen("output.out", "w", stdout); #endifscanf("%d",&t);while(t--){scanf("%d%d",&n,&m);cout<<yuesefu(n,m)+1<<endl;}//cout << "Hello world!" << endl;return 0; }

C++版本二

題解：

用數(shù)組模擬當前還在圈內(nèi)的人的編號。
記錄下次要報1 的人在當前圈內(nèi)的下標x,(x+k-1)%n 就是下次要出圈的人的下標，然后把這個數(shù)從數(shù)組中刪除，最后剩下的人就是答案。

#include<bits/stdc++.h> using namespace std; const int N = 1005; int num[N]; int main(){ // freopen("data.in","r",stdin); // freopen("check1.out","w",stdout);int T;cin >>T;while(T--){int n,k;scanf("%d %d",&n,&k);for(int i = 0;i < n;i ++) num[i] = i;int now = 0;while(n>1){now += k-1;now %= n;for(int i = now;i < n-1;i ++){num[i] = num[i+1];}n--;}printf("%d\n",num[0]+1);}return 0; }

C++版本三

#include<bits/stdc++.h>using namespace std; typedef long long ll; const int N=1e5+5; const int MOD=1e9+7; vector<int> t; int main(void){ // freopen("data.in","r",stdin); // freopen("check1.out","w",stdout);int T;cin >> T;while(T--){int n,k;cin >> n >> k;t.clear();for(int i=1;i<=n;i++) t.push_back(i);int st=0;while((int)t.size()>1){int id=(st+k-1)%((int)t.size()); // cout <<st<<" "<<id<<endl;t.erase(t.begin()+id);st=id%((int)t.size()); // for(auto te : t ) cout <<te<<" "; // cout << endl;}cout << *t.begin() << endl;}return 0; }

C++版本四

#include<bits/stdc++.h> using namespace std; const int N = 1005; int num[N], r[N], l[N]; int main(){ // freopen("data.in","r",stdin); // freopen("check1.out","w",stdout);int T;scanf("%d", &T);while(T--){int n,k;scanf("%d%d",&n,&k);for(int i = 0;i < n;i ++) num[i] = i + 1, r[i] = i + 1, l[i] = i - 1;r[n - 1] = 0, l[0] = n - 1;int now = 0, up;while(n > 1){up = k % n;if(!up) up = n;n--;for(int i = 1; i < up; ++i) now = r[now];r[l[now]] = r[now];l[r[now]] = l[now];now = r[now];}printf("%d\n",num[now]);}return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的第k人的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。