【题目描述】

有n个人依次围成一圈，从第1个人开始报数，数到第m个人出列，然后从出列的下一个人开始报数，数到第m个热呢又出列，... ,如此反复到所有的人全部出列为止。设n个人的编号分别为1，2

，... , n，打印出列的顺序。

【输入描述】

一行，n和m。

【输出描述】

输出列的顺序

【样例输入】

4 17

【样例输出】

1 3 4 2

【题目分析与思路1】—数组

1.  题目来源于“约瑟夫问题”。把所有人都放到数组中

2. 每个人的状态有两个，出列或者不出列，可以用true和false表示

3. 每个人一开始都在队列中，可以都用false表示

4. 然后模拟出队列的过程，直到所有人都出队列

5. 问题难点在于每个人出队后，队列就变了（长度变了），

6. 在外部写个循环保证还有人在队伍里就继续

7. 在上一个条件下，遍历数组，给选定的人进行标记，同时进行累加判断，找到第m个人。
   
   

【参考代码1】

#include <iostream>  #include <iomanip>  #include <cmath>  using namespace std;  int a[100]; //学生数组   int n,m; // n个人，第m个人出列   int main()  {      int people,position;  //用people表示还在队列中的人，position表示每轮的计数情况，每次从0开始       cin>>n>>m;       for(int i=1;i<=n;i++)          a[i]=1;  //先把所有的人都标记为1         	people=n; //把所有人赋值给people       position=0;        while(people>0) // 只要还有人在队列中就继续       {          for(int i=1;i<=n;i++)  //遍历n个人           {              if(a[i]==1) //如果当前这个人是1，表示在队列中，就从中找第m个               {                  position++;  //位置加1                   if(position==m) //如果是第m个位置                   {                      position=0;  // 把位置重置为0                       a[i]=0; //把当前这个人提出队列，下次就不再遍历他了                       cout<<i<<" "; //当前人编号输出                       people--;  //队列减去一个1                       if(people==0) //如果没人了，就退出                       {                          break;                      }                  }              }          }      }      return 0;  }

【题目分析与思路2】—队列

#include<iostream>  #include<queue>  using namespace std;  int main()  {      int n,m;      cin>>n>>m;  //读入n和m             queue<int> q;      for(int i=1;i<=n;i++)          q.push(i);                 int cnt=0;      while(!q.empty()){ //只要队列不为空           cnt++;  // 计数加1           int temp=q.front();  //把当前队首元素拿出           if(cnt==m){  //判断是不是到了m               cnt=0;  //把计算器变为0               cout<<temp<<" ";  // 输出这个人的编号           }          else{              q.push(temp); //表示还没到m           }          q.pop(); //遇到第m个，就删除队首。没有遇到第m个，就把队首删除（队首已经重新入队变成队尾了）       }      cout<<endl;      return 0;  }

(adsbygoogle = window.adsbygoogle || []).push({});