学步园

描述: 有N个人坐在一圈做游戏，给他们编号为1到N，现从1号人开始传递一份烤肉，传递M次停下，将拿着烤肉的人从圈中退出，圈缩小，将烤肉给退出的人后面的人，然后开始继续传递M次停下，又将拿着烤肉的人从圈中退出，圈缩小，依次类推，直到剩下一个人，那个人就可以品尝烤肉了，作程序，看看最后的获胜者是谁？。

分析:设有N个人，烤肉传递M次时，第M+1个人退出，从1号开始传递烤肉。

本文采用STL解法程序如下：

// Josephus问题（约瑟夫环问题）<br /> #include <iostream><br /> #include <list></p> <p>using namespace std;</p> <p>int main()<br /> {<br /> cout << "请输入人数N: ";<br /> int n;<br /> cin>>n;<br /> list<int> lst;<br /> for(int i = 1; i <= n; ++i )<br /> lst.push_back(i);<br /> cout << "请输入每次退人时需要的传递次数M: ";<br /> int m;<br /> cin>>m;</p> <p> list<int>::iterator it = lst.begin();<br /> //int k;</p> <p> while( lst.size() != 1 )<br /> {<br /> for( int i=0; i<m; ++i)<br /> {<br /> if( it != lst.end() )<br /> ++it;<br /> else<br /> it = lst.begin();<br /> }<br /> if( it == lst.end() )<br /> it = lst.begin();<br /> cout << *it << " ";<br /> it=lst.erase(it);<br /> if( lst.size() == 1 )<br /> {<br /> cout<<endl;<br /> cout<<"获胜者为: ";<br /> cout<<lst.front();<br /> cout<<"号"<<endl;<br /> }<br /> }<br /> cout<<endl;<br /> return 0;<br /> }

程序运行情况如下：

请输入人数N:  5

请输入每次退人时需要的传递次数M: 1

     2   4   1   5

获胜者为:   3号