学步园

约瑟夫环问题。

其中的注释部分为暴力方法，这明显会tle。

so 参考：http://hi.baidu.com/autogerk/blog/item/3ec31065699e6df9f636546e.html

这篇也很有意思：http://www.9php.com/FAQ/cxsjl/c/2007/03/403506277877.html

#include<cstring><br /> #include<cstdio><br /> #include<iostream><br /> using namespace std;<br /> //bool vis[20];<br /> int arr[15];<br /> //bool solve(int n,int k)<br /> //{<br /> // memset(vis,true,sizeof(vis));<br /> // int cout=0;int i=0,j=0;<br /> // while(cout<n/2)<br /> // {<br /> // i=i%n;<br /> // if(vis[i])<br /> // {<br /> // j++;<br /> // if(i>=n/2&&j==k)<br /> // {<br /> // cout++;<br /> // if(cout==n/2 )return true;<br /> // j=0; vis[i]=false;<br /> // }<br /> // else if(j==k&&i<n/2) return false;<br /> //<br /> // } i++;<br /> // }<br /> // return false;<br /> //}<br /> //int f(int n)<br /> //{<br /> // int i;<br /> // for(i=2;;i++)<br /> // {<br /> // if(solve(n,i))<br /> // {<br /> // return i;<br /> // }<br /> // }<br /> //}<br /> void solve(int n)<br /> {<br /> int len=n*2;<br /> int s,m=n+1;<br /> while(1)<br /> {<br /> s=0;<br /> int cout=0;<br /> while(cout<n)<br /> {<br /> int k=(s+m-1)%len;<br /> if(k>=n)<br /> {<br /> cout++;<br /> if(cout==n)<br /> {<br /> arr[n]=m;<br /> printf("%d/n",m);<br /> return ;<br /> }<br /> s=k;<br /> len--;<br /> }<br /> else<br /> {<br /> m++;<br /> s=0;len=n*2;<br /> break;<br /> }<br /> }<br /> }<br /> }<br /> int main()<br /> {<br /> int n;<br /> memset(arr,0,sizeof(arr));<br /> while(1 )<br /> {<br /> cin>>n;<br /> if(n==0) break;<br /> if(arr[n])<br /> printf("%d/n",arr[n]);<br /> else solve(n);<br /> }<br /> return 0;<br /> }