约瑟夫环问题

0~n-1个数排成环，每次从中删除第m个数字后，问最后剩下的数字是多少

思路：使用链表模拟环状结构，到达尾部时使其重新指向头部

int Josephuse(int n ,int m)
{
  if(n<1 || m<1)return -1;
  list<int>numbers;
  for(int i = 0; i<n;i++)
    numbers.push_back(i);
  
  list<int>::iterator current = numbers.begin();
  while(numbers.size()>1)
   {
      for(int i = 0; i<m;i++)
        {
           current++;
           if(current == numbers.end())
            current = numbers.begin();
        }

    list<int>::iterator  next = current + 1;
    if(next == numbers.end())
      next = numbers.begin();  
    numbers.erase(current);
    current = next;
  }
  return *(next);
}

《剑指offer》创新解法

int last(int n, int m)
{
  if(n<1 || m<1)
    return 0;
  int last = 0;
  for(int i = 2; i<=n; i++)
    last = (last+m)%i;
  return last;
}