约瑟夫环问题的几种解法

int mind01()
{
  vector<int> vec;
  int n, m;
  scanf("%d%d",&n,&m);
  //初始化
  for (int i=1;i<=n;i++)
  {
    vec.push_back(i);
  }
  //开始游戏
  int vz = 0;
  while (vec.size() > 1)    //留下最后一个人
  {
    //约瑟夫环经典公式-->循环队列
    vz = (vz + m - 1) % vec.size(); //因为下表从0开始的，所以减一
    //淘汰的那个人
    cout << vec[vz] << endl;
    vec.erase(vec.begin()+vz);
  }
  //淘汰掉最后一个人
  cout << vec[0] << endl;
  return 0;
}

int mind02()
{
  queue<int> que;
  int n, m;
  int count_num = 1;    //计数
  scanf("%d%d",&n,&m);
  //初始化
  for (int i=1;i<=n;i++)
  {
    que.push(i);
  }
  //开始游戏-->循环队列
  while (!que.empty())   //当队列不为空
  {
    if (count_num == m)   //有人要被淘汰掉了
    {
      cout << que.front() <<" ";
      que.pop();        //把被淘汰的人从队列中剔除出去
      count_num = 1;      //下一个人要重新从1开始
    }
    else //这个人不会被淘汰掉
    {
      count_num++;
      que.push(que.front());    //把队头的人当到队尾
      que.pop();
    }
  }
  return 0;
}

struct node
{
  int date;
  node *next;
}*head , *tail;     //循环链表的头尾结点
void initList(int len)
{
  //辅助指针
  node* s;
  //建立头节点
  head = new node;
  tail = head;
  head->next = NULL;
  //初始化-->尾插法
  for (int i=1;i<=len;i++)
  {
    s = new node;
    s->date = i;
    tail->next = s;
    tail = s;
  }
  tail->next = head->next;    //循环链表
}
void del_node(node * &cur,node * &pro)
{
  node *s = cur;
  pro->next = cur->next;
  cur = cur->next;
  delete s;
  s = NULL;
}
int mind03()
{
  int n, m;
  int count_num = 1;    //计数
  node *cur = NULL;
  node *pro = NULL;
  scanf("%d%d",&n,&m);
  initList(n);
  cur = head->next;
  cur = head->next;
  pro = head;
  这里我们不妨先把头节点删掉
  while (pro->next != pro)      //只剩下最后一个人了
  {
    //cout << "aaaa" << endl;
    if (count_num == m)     //踢人咯
    {
      count_num = 1;
      cout << cur->date << " ";
      del_node(cur,pro);
    }
    else
    {
      count_num++;
      cur = cur->next;
      pro = pro->next;
    }
  }
  //
  if (pro != NULL)
  {
    //cout << "aaaa" << endl;
    cout << pro->date << endl;
    delete pro;
    pro = NULL;
    cur = NULL;
  }
  if (head != NULL)
    delete head;
  return 0;
}

//线段树-->可以直接百度查找模板直接使用即可 O(lbn)
/*
线段树是一种二叉搜索树，与区间树相似，
它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶子节点[a,b]，它的左儿子表示的区间为[a,(a+b)/2]，
右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树，最后的子节点数目为N，即整个线段区间的长度。
使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)。
而未优化的空间复杂度为2N，因此有时需要离散化让空间压缩。
线段树至少支持下列操作:
Insert(t,x):将包含在区间 int 的元素 x 插入到树t中;
Delete(t,x):从线段树 t 中删除元素 x;
Search(t,x):返回一个指向树 t 中元素 x 的指针。
*/