算法_00003_约瑟夫环

1 总结

有 n 个打算杀身成仁的犹太人(将军为约瑟夫)商量后决定分别从黑箱子里抽签(编号是连续的分别为 1,2,3…n, 在数组中下标即为 0,1,2…n-1), 然后按编号顺序围成一个圈, 随机取一个数 m , 不断的依次杀死报数为 m (即下标为m-1)的人, 求最后一个报数为 m 的人编号(自己有预谋的拿到这个编号,就可以活下来)

1. 第一个杀死的人为第一个抽签为 m (下标为m-1) 的人
2. 最后一个人在该轮的下标肯定为 0

• 上一轮的结果f(n-1) + 报数的值 m 取模 这一轮的总数 n
• f(n) 即有 n 个人从 下标为m-1依次报数, 将报数为m的人杀掉, 求最后一个报数为m(最后一个可以活着)的人的下标
  • 注意报的数是从 1 开始到 m, 所以报数为m的人的下标为 m-1, 毕竟数组的下标从0开始

    即 n 个人里面从 下标为(m-1)的人从1开始依次报数(1,2...m) 最后一个报数为m的人即为活着的人的 下标
    f(n) = (f(n-1) + m) % n

https://leetcode-cn.com/playground/93L4SBcb

2

大致过程如图下：

那么我们知道是这么得到的新的队列，那么也很容易知道怎么反推了：
反观如上的变化情况，都是减去一个q，所以：
变回去的公式如下：old = (new + q) % n
这里的old和new指的是下标，n指的是总共有多少人

知道了怎么推出之前的下标，那么也就可以一步步递推回去得到开始的队列或者从小推到大得到最后剩余的结果。
最后再做一道实际点的例子，求J2(4):

J2(1) = 0
J2(2) = (J2(1) + 2) % 2 = 0
J2(3) = (J2(2) + 2) % 3 = 2
J2(4) = (J2(3) + 2) % 4 = 0

参考

https://blog.csdn.net/tingyun_say/article/details/52343897

https://www.zhihu.com/question/23331384