约瑟夫环问题

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后结果+1即为原问题的解。

假设有num个人，每隔k-1人（即第k个人）出列，求出最后出列的人编号

#include <iostream> #include<vector> #include<algorithm> using namespace std; int main() { int num;//共num人 int lastnum;//标记最后出列的人的编号 int countnum=1; int k;//每隔k-1个人（即第k人）出列 vector<int>v; vector<int>::iterator it; cin>>num; cin>>k; v.resize(num); for(int i = 0; i < num; i++) v[i] = i; for(it = v.begin(); !v.empty();) { if(countnum == k) { lastnum = *it; v.erase(it); countnum = 1; } else { it++; countnum++; } if(it == v.end()) { it = v.begin(); } } v.clear(); cout<<lastnum+1<<endl; return 0; }