约瑟夫环问题：

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

这里给出以下几种解法，

1.用队列模拟

每次将前m-1个元素出队，出队元素放入队列的末尾，再循环即可，这种方法时间复杂度为O(mn)(每找出一个数字需要m步运算，要找出n人数字)，空间复杂度为O(n),用于存放队列，运行结果如下。

2.环形链表模

时间复杂度为O(mn)，空间复杂度为O(n)

代码如下（vs2015调试正常）：

1 //Josephuse环问题 2 #include 
     
       3 #include 
      
        4 #include 
       
         5 #include 
        
          6 #include 
         
           7  8  9 using namespace std;10 11 //用队列模拟12 void Q_Joes(int n, int m)13 {14     queue
          
            Q;15 vector
           
             result;16 for (int i = 0; i < n; i++) {17 Q.push(i);18 }19 int count = m;20 while (!Q.empty()) {21 while (--count) {22 Q.push(Q.front());23 Q.pop();24 }25 result.push_back(Q.front());26 Q.pop();27 count = m;28 }29 for (auto i : result)30 cout << i << " ";31 cout << endl;32 cout << result[result.size() - 1];33 cout << endl;34 }35 36 //用循环链表来模拟，当单链表迭代器到末尾时，将其移到链表的开头，以此来模拟一个环形链表37 void List_Joes(int n, int m)38 {39 if (n < 1 || m < 1)40 return;41 list
            
              L;42 vector
             
               result;43 int i;44 for (i = 0; i < n; ++i)45 L.push_back(i);46 list
              
               ::iterator curNode = L.begin();47 while (L.size() > 0) {48 //找到第m个数字49 for (int i = 1; i < m; ++i) {50 curNode++;51 if (curNode == L.end())52 curNode = L.begin();53 }54 55 auto next = ++curNode;56 if (next == L.end())57 next = L.begin();58 --curNode;59 result.push_back(*curNode);60 L.erase(curNode);61 curNode = next;62 63 }64 for (auto i : result)65 cout << i << " ";66 cout << endl;67 cout << result[result.size() - 1];68 cout << endl;69 }70 71 int main()72 {73 int n, m;74 cin >> n >> m;75 Q_Joes(n, m);76 List_Joes(n, m);77 system("pause");78 return 0;79 }
              
             
            
           
          
         
        
       
      
     

 

3.数学解法

当n为1时，最后剩下的数字为0

当n大于1时，f(n,m) = f'(n -1,m) = (f(n -1,m) + m) %n

 

1 #include 
     
       2 #include 
      
        3  4 int main() 5 { 6     int n, m,i,last; 7     scanf("%d%d", &n, &m); 8     last = 0; 9     for (i = 2; i <= n; i++)10         last = (last + m) % i;11     printf("%d\n", last);12     system("pause");13     return 0;14 }