我今天要讲的问题是约瑟夫环问题。
本蒟蒻第一篇学术文章,多多支持,写的不好请见谅。
这题是一道好题目,我这里推荐两种解法
1.直接模拟
我用了一个数组来模拟,在圈内为无穷大,不在圈内则为0。
模拟时要注意以下几点:
-
如果当前已经出了圈,那么这个位置不算一人。
-
记得将数组的值变为0.
-
当计数器超过n时,需要重置为1。
于是我就写出来代码:
#include<bits/stdc++.h>
using namespace std;
int a[101];
int main(){
int n,m,cnt=0,cnt2=1;
cin>>n>>m;
memset(a,0x3f,sizeof a);
while(n){
while(cnt2<=m){
cnt++;
cnt2++;
if(cnt>n)cnt%=n;
if(a[cnt]==0)cnt2--;
}
a[cnt]=0;
cnt2=1;
cout<<cnt<<' ';
n--;
}
return 0;
}
结果发现不仅样例错了而且死循环。检查后发现是这个问题
判断计数器是否大于n时,因为n在减少,所以其实并未大于n就重置了。
改正后是这样的:
AC CODE
#include<bits/stdc++.h>
using namespace std;
int a[101];
int main(){
int n,m,cnt=0,cnt2=1,nn;
cin>>n>>m;
nn=n;//备份n
memset(a,0x3f,sizeof a);//将所有人标记为在圈内
while(nn){
while(cnt2<=m){//逐一计数
cnt++;
cnt2++;
if(cnt>n)cnt%=n;//判断是否大于n
if(a[cnt]==0)cnt2--;//判断此人在不在圈内
}
a[cnt]=0;
cnt2=1;
cout<<cnt<<' ';
nn--;
}
return 0;
}
别急着走,接下来还有第二种方法:
2.巧用数据结构
在淘汰这种题目中,用数组并不是一个明智的选择,在标记是否在圈内时较为麻烦,而队列刚好解决了这个问题。
思路:
枚举m个人,前m-1个人先从队列另一头加入,再弹出,将第m个弹出队列,不需要考虑大于n和是否在圈内的情况。
AC CODE
#include <bits/stdc++.h>
using namespace std;
queue<int> q;
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
q.push(i);//预处理,将人放入队列
}
while(q.size()){
for(int i=1;i<=m-1;i++){
q.push(q.front());
q.pop();
}
cout<<q.front()<<' ';
q.pop();
}
return 0;
}
这是我的评测记录
(上面是模拟,下面是队列)
都看完了点个赞再走吧。
标签:cnt,int,约瑟夫,问题,队列,while,cnt2,圈内 From: https://www.cnblogs.com/xdh2012/p/17767271.html