约瑟夫问题总结

题解在代码里~

#include 
#include 
#include 
using namespace std;int main()
{int n, k, f[100];n = 12; cin>>k;//链表做法,复杂度O(n*k)list <int> L;for(int i = 1; i <= n; i++) f[i] = i, L.push_back(i);list<int>::iterator pos = L.begin();while(L.size() > 1){for(int i = 1; i < k; i++){++pos;if(pos == L.end()) pos = L.begin();}f[*pos] = 0; pos = L.erase(pos); if(pos == L.end()) pos = L.begin();for(int i = 1; i <= n; i++) cout<3)<endl;}//若只需求最后出列的人，则可以直接采用动态规划，复杂度O(n)/*dp[i]表示有i个人时(从0到i重新编号)，最后出列的人那么如果有i+1个人，我们只需要去掉第一个出列的人，即第k个人就可以转换成i个人的情况即dp[i+1] = (k + dp[i])%(i+1)*/int dp[100];dp[1] = 0;for(int i = 2; i <= n; i++) dp[i] = (dp[i-1] + k)%i;cout<3)<1<<endl;
}