用具体数学解决约瑟夫环问题
约瑟夫环
有 n 个人围成一个圈,每 q 个人踢掉一个人,问最后留下来的人是几号?
使用链表暴力求解时间复杂度是 O(qn),递归的话是 O(n) ,使用这个方法可以加速到 O(logn).
解法思路:
假设初始编号为 1,2,3 ... n ,现在考虑一种新的编号方式.
第一个人不会被踢掉,那么他的编号从 n 开始往后加 1 ,变成 n+1 ,然后第二个人编号变为 n+2 ,直到第 q 个人,他被踢掉了.
然后第 q+1 个人编号继续加 1 ,变成了 n+q ,依次下去.
考虑当前踢到的人编号为 kq,那么此时已经踢掉了 k 个人,所以接下去的人新的编号为 n+k(q-1)+1....
所以编号