约瑟夫环问题又称丢手绢问题
WIKI解释
下标 0 至 n-1 形成一个环
每次翻过m个数,删除后,从后面一个数继续开始翻过m个数删除,问最后剩下的数的下标
每一轮存在以下 ? 个操作步骤
- 找到 0 开始的第m%n(m可能大于n)个元素并删除
- 从 m%n 开始后一个元素作为第一个元素向前移动 m%n 个位置
- 幸存者的下标 x 会变成 x - m%n
- 以上 1 - 3 步骤重复执行一直到x的下标变为0
// 递归写法
if n == 1
x = 0
// 因为是循环数组,因此需要取余
f(n) = (f(n-1) + m)%n
// 迭代写法
int x = 0
for (int i = 1; i < n; i++) {
// 加回移动的m%n个位置 ,这里的n是下一次的元素总长度,因此要变为i+1
x = (x + m)%(i+1)
}
return x;
Q.E.D.