圆圈中最后剩下的数字-白红宇

题目：0，1，...，n-1这n个数字排成一个圆圈，从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

这就是有名的约瑟夫（Josephuse）环问题。可以用环形链表模拟圆圈的经典解法。

分析：用模板库中的std::list来模拟一个环形链表。由于std::list本身不是一个环形结构，因此每当迭代器扫描到链表末尾的时候，要记得把迭代器移到链表的头部，这样就相当于按照顺序在一个圆圈里遍历了。

这种思路的代码如下：

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

本文转自夏雪冬日博客园博客，原文链接：http://www.cnblogs.com/heyonggang/p/3645558.html，如需转载请自行联系原作者