/* O(n)获取任意步骤的结果 每一轮报数,报到m的人就被杀掉 例如:n=5,s=1,m=3 第一轮:1 2 3 4 5,排除3,剩下1 2 4 5 第二轮:4 5 1 2,排除1,剩下4 5 2 第三轮:2 4 5,排除5,剩下2 4 第四轮:2 4,排除2,剩下4 最后剩下4 对于第二轮的4 5 1 2,修改编号为1 2 3 4,这样可以发现: 设修改编号之后的每个元素编号为x,每个x修改之前对应的元素编号为y, 则有y==(x+m)%(t) (注意边界)(t是未排除之前的元素个数) 而同时,可以发现:如果把每一步去掉的元素的编号x设为0,y符合上述表达式 所以可以使用递推式: 设f[i]为i个人玩最后的胜利者,定义f[0]=0,有下列表达式成立: f[1]=(f[0]+m)%1 f[2]=(f[1]+m)%2 f[3]=(f[2]+m)%3 以此类推。(不考虑边界) 那么f[n]就是最后的胜利者。 同时,如果设在被去掉的元素之后,剩余t个元素时,这个被去掉元素编号为g: 那么g可以写成一个递归/递推函数 当这个元素被去掉时,它的编号一定是0,此时f[0]=0,这里f是这个元素在前若干步中的编号 f[1]=(f[0]+m)%(t+1) f[2]=(f[1]+m)%(t+2) f[3]=(f[2]+m)%(t+3) 以此类推。(不考虑边界) 那么g=f[n-t] */ int Josephus2(int* f,int n,int s,int m,int t){//t为剩余人数 f[0]=0; for(int i=1;i<=n;i++){ f[i]=(f[i-1]+m)%(t+i); if(f[i]==0)f[i]=t+i; } int g=f[n-t]; return g+s-1<=n?g+s-1:g+s-1-n; }