约瑟夫环问题

来源：Bloomberg Onsite

原帖：http://blog.csdn.net/wuzhekai1985/article/details/6628491

题目：
最近看bloomberg的面经看到出现过几次约瑟夫环问题。这道题的模拟解法非常直观，更好的解法是观察索引的映射关系采用recursion来解。以前没有仔细思考过这个问题。博客链接给了很好的解释。

约瑟夫环问题的原来描述为，设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求n个人出圈的次序。  稍微简化一下。

问题描述：n个人（编号0~(n-1))，从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。求胜利者的编号。

代码：
1] Brute force solution

 int JosephusProblem(int n, int m) {   
   if (n < 1 || m < 1)   
     return -1;   
    
   list<int> listInt;   
   unsigned i;   
   //初始化链表   
   for (i = 0; i < n; i++)   
     listInt.push_back(i);    
   list<int>::iterator iterCurrent = listInt.begin();   
   while (listInt.size() > 1) {   
     //前进m - 1步   
     for(i = 0; i < m-1; i++) {   
       if(++iterCurrent == listInt.end())   
         iterCurrent = listInt.begin();   
     }   
     //临时保存删除的结点   
     list<int>::iterator iterDel = iterCurrent;   
     if(++iterCurrent == listInt.end())   
       iterCurrent = listInt.begin();   
     //删除结点   
     listInt.erase(iterDel);   
   }  
   return *iterCurrent;   
 }  

2] dp solution

 int JosephusProblem(int n, int m) {   
   if(n < 1 || m < 1)   
     return -1;   
   vector<int> f(n+1,0);   
   for(unsigned i = 2; i <= n; i++)   
     f[i] = (f[i-1] + m) % i;    
   return f[n];   
 }