algorithm - 解决复发复发

Question

好的，我正在努力学习高德纳 (Knuth) 的具体数学，并且有一些我还不理解的示例。

J(n) = 2*J(n/2) - 1

这是第一章。特别是它为那些可能熟悉具体数学的人解决了约瑟夫斯问题。给出了解决方案，但绝对没有解释。 我试图用迭代方法解决它。这是我到目前为止的想法

J(n) = (2^k)*J(n/(2^k)) - (2^k - 1)

我被困在这里了。任何帮助或提示将不胜感激。

Answer 1

我会先记忆一下约瑟夫斯问题。

我们有 n 人围成一圈。刽子手将以下列方式处理圆圈:

1. 刽子手从位置i=1的人开始
2. 在位置i时，他饶了i但杀了i的跟随者
3. 他这样做直到只有一个人活着

通过快速查看此过程，我们可以看到在第一轮中每个处于偶数位置的人都会被杀死。当所有的“偶”都死了，剩下的人是谁？好吧，这取决于 n 的奇偶性。

如果 n 是偶数(比如 n = 2i)，那么剩下的人就是 1,3,5,...,2i-1。剩下的问题是 i 人而不是 n 的圈子。我们引入一个映射map_even在"new"圈子中的位置和n人圈子中的初始位置。

map_even(x) = 2.x - 1

这意味着新圈子中位置 x 的人在初始圈子中的位置为 2.x - 1。如果幸存者在新圈子中的位置为J(i)，则某人在n=2.i人的圈子中必须占据的位置为

map_even(J(i)) = 2.J(i) - 1

我们有第一个递归规则:

For any integer n :
J(2.n) = 2.J(n) - 1

但是如果 n 是奇数 (n = 2.j + 1)，那么第一次运行结束时会杀死所有“偶数”并且刽子手位于位置 n。 n 个追随者是 1 ... 因此，下一个被杀死的是 1。幸存者是 3,5,..,2j+1，刽子手继续前进，就好像我们有一圈 j 人。映射与偶数情况有点不同:

map_odd(x) = 2.x + 1

3 是新的 1，5 是新的 2，依此类推......

如果幸存者在j人的圈子中的位置是J(j)，那么n=2j+1的圈子里想活下来的人必须占据J(2j+1)的位置:

J(2j+1) = map_odd(J(j)) = 2.J(j) + 1

第二个递归关系得出:

For any integer n, we have :
J(2.n + 1) = 2.J(n) + 1

从现在开始，我们可以使用 2 个递归关系为 任何 整数 n 计算 J(n)。但如果我们看得更远一点，我们可以让它变得更好......

因此，对于每个 n = 2^k，我们有 J(n) = 1。好的，但是对于其他数字呢？如果您写下第一个结果(比如最多 n = 20)，您会发现该序列似乎是伪周期性的:
1 2 3 4 5 6 7 8 9 10 11
1 1 3 1 3 5 7 1 3 5 7

从 2 的幂开始，似乎位置在每一步增加 2，直到下一个 2 的幂，我们再次从 1 开始......因为，给定一个整数 n 有一个唯一的整数 m( n) 这样

2^m(n) ≤ n < 2^m(n)+1

令 s(n) 为满足 n = 2^m(n) + s(n) 的整数(我将其称为“s”，表示“shift”)。 我们观察的数学翻译是 J(n) = 1 + 2.s(n)

让我们用强归纳法来证明它。
对于 n = 1，我们有 J(1) = 1 = 1 + 2.0 = 1 + 2.s(1)
对于 n = 2，我们有 J(2) = 1 = 1 + 2.0 = 1 + 2.s(2)

假设 J(k) = 1 + 2.s(k) 对于任何 k 使得 k ∈ [1,n]，让我们证明 J(n+1) = 1 + 2.s(n+1) .

我们有 n = 2^m(n+1) + s(n+1)。显然，2^m(n) 是偶数(除了 n = 1 的平凡情况)，因此 n 的奇偶校验由 s(n) 携带。

如果 s(n+1) 是偶数，则我们表示 s(n+1) = 2j。我们有

J(n+1) = 2.J((n+1)/2) - 1 = 2.J(2^m(n+1)-1 + j) - 1

由于该陈述对任何 k ∈ [1,n] 都成立，因此对 1 ≤ k = (n+1)/2 < n 也成立，因此:

J(n+1) = 2.(2j + 1) - 1 = 2.s(n+1) + 1

我们可以类似地解决奇怪的情况。 该公式对任意整数 n 成立:

J(n) = 2.s(n) + 1, with m(n), s(n) ∈ ℕ the unique integers such that
2^m(n) ≤ n < 2^m(n)+1 and s(n) = n - 2^m(n)
In other terms : m(n) = ⌊ln₂(n)⌋ and s(n) = n - 2^{⌊ln₂(n)⌋}