具体数学-第8课（取整进阶一）

例题1

给出下列递归式：

现在不要求你求解，要你证明：

首先想到的就是数学归纳法，假设对于任意 ，都有 ，那么：

如果 ，那么

如果 ，那么 ，这时不成立。

所以数学归纳法无法证明，今后我们会用其他方法来证明这个式子。

约瑟夫环新解

还记得约瑟夫环问题吗？详见第一节课。

这里我们继续推广到一般情况，如果有 n 个人，每隔 q 个人踢掉一个人，最后剩下的是几号？

初始编号为 ，现在考虑一种新的编号方式。

第一个人不会被踢掉，编号加 1 ，变成 ，然后第二个人编号变为 n+2 ，直到第 q 个人，他被踢掉了。

然后第 个人编号继续加 1 ，变成了 ，依次下去。

考虑当前踢到的人编号为 ，那么此时已经踢掉了 k 个人，所以接下去的人新的编号为

所以编号为 的人编号变成了 ，其中 。

直到最后，可以发现活下来的人编号为 ，问题是怎么根据这个编号推出他原来的编号？

以 为例，下图就是每个人新的编号：

令

所以他上一次的编号是

因为

所以上一次编号可以写为

因此最后存活的人编号可以用如下的算法计算：

N = qn
while N > n:
    N = k + N - n
ans = N

其中

如果我们用 替代 N ，将会进一步简化算法：

算法伪代码如下：

D = 1
while D <= (q-1)n:
    D = k
ans = qn + 1 - D

其中