1.求解最后一個(gè)

N個(gè)人坐成一個(gè)圓環(huán)（編號(hào)為1 - N），從第1個(gè)人開(kāi)始報(bào)數(shù)，數(shù)到K的人出列，后面的人重新從1開(kāi)始報(bào)數(shù)。問(wèn)最后剩下的人的編號(hào)。
例如：N = 3，K = 2。2號(hào)先出列，然后是1號(hào)，最后剩下的是3號(hào)。
輸入
2個(gè)數(shù)N和K，表示N個(gè)人，數(shù)到K出列。(2 <= N, K <= 10^6)
輸出
最后剩下的人的編號(hào)
輸入樣例

3 2

輸出樣例

3 #include <bits/stdc++.h> using namespace std; //迭代寫法 int Joseph(int n,int m) {/* if(n <= 1 || m <= 1)return -1;*/int ans = 0;for(int i = 2; i <= n; i++){ans = (ans + m) % i;}return ans+1; } int main() {int n,m;cin>>n>>m;cout<<Joseph(n,m)<<endl;return 0; } #include <bits/stdc++.h> using namespace std; //遞歸寫法 int Joseph(int n,int m) {/*if(n <= 1 || m <= 1)return -1;*/if(n == 2){if(m&1)return 2;elsereturn 1;}elsereturn (Joseph(n-1,m)-1 + m) % n + 1; } int main() {int n,m;cin>>n>>m;cout<<Joseph(n,m);return 0; }

2.求解每一個(gè)

題目背景
約瑟夫是一個(gè)無(wú)聊的人！！！

題目描述
n個(gè)人(n<=100)圍成一圈,從第一個(gè)人開(kāi)始報(bào)數(shù),數(shù)到m的人出列,再由下一個(gè)人重新從1開(kāi)始報(bào)數(shù),數(shù)到m的人再出圈,……依次類推,直到所有的人都出圈,請(qǐng)輸出依次出圈人的編號(hào).

輸入格式
n m

輸出格式
出圈的編號(hào)

輸入輸出樣例
輸入 #1 復(fù)制

10 3

輸出 #1 復(fù)制

3 6 9 2 7 1 8 5 10 4

說(shuō)明/提示
m,n≤100

//way4：vector模擬 #include <bits/stdc++.h> using namespace std; vector<int>v; int main() {int n,m;cin>>n>>m;for(int i = 1; i <= n; i++)v.push_back(i);int x = 0;for(int i = 0; i < n; i++){x = (x + m - 1) % v.size();cout<<v[x]<<" ";v.erase(v.begin()+x);}return 0; } //way3：隊(duì)列模擬 #include <bits/stdc++.h> using namespace std; int main() {queue<int>q;int n,m;cin>>n>>m;if(!n||!m) return 0;for(int i = 1; i <= n; i++){q.push(i);}int cnt = 0;while(q.size()>1){int x = q.front();cnt++;q.pop();if(cnt % m == 0){cout<<x<<" ";continue;}q.push(x);}cout<<q.front()<<endl;q.pop();return 0; } //way2：環(huán)形鏈表模擬 #include <bits/stdc++.h> using namespace std; typedef struct Node {int num;struct Node *nxt; }node; node* createNode(int x) {node *p;p = new node;p->num = x;p->nxt = NULL;return p; } node* createJoseph(int n) {node *p,*head,*q;for(int i = 1; i <= n; i++){p = createNode(i);if(i == 1)head = p;elseq->nxt = p;q = p;}q->nxt = head;return head; } void runJoseph(int n,int m) {node *p = createJoseph(n);node *q = NULL;while(p->nxt != p){for(int i = 1; i < m-1; i++){p = p->nxt;}q = p->nxt;cout<<(q->num)<<" ";p->nxt = q->nxt;p = p->nxt;delete q;}cout<<(p->num)<<endl; } int main() {int n,m;cin>>n>>m;if(n&&m)runJoseph(n,m);return 0; } //way1：數(shù)組模擬 #include <iostream>using namespace std; bool vis[105]; int main() {int n,m;cin>>n>>m;int cnt = 0,num = 0;while(cnt<n){for(int i = 1; i <= n; i++){if(vis[i]) continue;num++;if(num % m == 0){vis[i] = true;if(cnt != n)cout<<i<<" ";else cout<<i<<endl;cnt++;if(cnt == n) break;}}}return 0; } //數(shù)組模擬鏈表 #include <bits/stdc++.h> using namespace std; int nxt[105]; int main() {int n,m;cin>>n>>m;for(int i = 1; i <= n; i++)nxt[i] = i+1;nxt[n] = 1;for(int i = n,j = 1; n;i = nxt[i],j++){if(j % m == 0){cout<<nxt[i]<<" ";nxt[i] = nxt[nxt[i]];n--;}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的简单约瑟夫环问题解法汇总（模拟/数论）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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