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;
}
