约瑟夫环问题又称丢手绢问题
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.


每一个平凡的日常都是连续的奇迹