约瑟夫环
# 共m个人(编号0~m-1) 第k个报数离开
上一轮 n+1 个人
该轮(n人)编号为0的在上一轮编号为 (k)%(n+1) (数到0~k-1，下一个就是k)
即：编号为f(n)的在上一轮编号f(n+1) 为 (f(n)+k)%(n+1)
求f(1)=0 时 其f(m)的值
f[1]=0;
for(int i=2;i<=m;i++){
f[i]=(f[i-1]+k)%i;
}
1
2
3
4
5
6
2
3
4
5
6
# 变种1：编号1~m
f[1]=1;
for(int i=2;i<=m;i++){
f[i]=(f[i-1]+k)%i;
if(f[i]===0)f[i]=i;
}
result=f(m)
1
2
3
4
5
6
7
2
3
4
5
6
7
# 变种2：编号1~m,从第j个开始报数
还是和变种1一样，先算出正常报数时的最后一个人的原始编号，result=(f(m)+j-1)%m
f[1]=1;
for(int i=2;i<=m;i++){
f[i]=(f[i-1]+k)%i;
if(f[i]===0)f[i]=i;
}
result=(f(m)+j-1)%m
if(result===0)result=m
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 变种3：编号为1~m,已知留到最后的原始编号为t,求从第j个开始报数可实现
先算出从1开始报数时最后一个人的原始编号f(m)，
res=(t-(f(m)-1))%m res==0?m:res
f[1]=1;
for(int i=2;i<=m;i++){
f[i]=(f[i-1]+k)%i;
if(f[i]===0)f[i]=i;
}
res=(t-(f(m)-1))%m
res==0?m:res
1
2
3
4
5
6
7
8
2
3
4
5
6
7
8
# 变种4：编号为0~m-1,留到最后三个人的原始编号
f(1) = 0
f(2) = k%2
g(2) = (f(2)+1)%2
f(3) = (f(2)+k%3
g(3) = (g(2)+k)%3
h(3) = {0,1,2}-{f(3),g(3)}
for(int i = 4;i<=m;i++){
}
最后算出f(m),g(m),h(m)
1
2
3
4
5
6
7
8
9
10
11
2
3
4
5
6
7
8
9
10
11
编辑 (opens new window)
上次更新: 2024/09/01, 23:56:56