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 人的圈子。_让我们在“新”圈子中的位置和n人圈子中的初始位置之间引入一个映射图。

映射_偶数(x) = 2.x - 1

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

映射_偶数(J(i)) = 2.J(i) - 1

我们有第一个递归规则：

对于任何整数 n ：
J(2.n) = 2.J(n) - 1

但是如果 n 是奇数（n = 2.j + 1），那么第一次运行最终会杀死所有“偶数”，并且刽子手在位置 n。n 追随者是 1 ... 因此下一个要被杀死的人是 1。幸存者是 3,5,..,2j+1，刽子手继续前进，就好像我们有一个由 j 人组成的圈子一样。映射与偶数情况有点不同：

地图_奇数(x) = 2.x + 1

3 是新的 1，5 是新的 2，以此类推……

如果幸存者在 j 人的圈子中的位置是 J(j)，那么想要在 n = 2j+1 的圈子中生存的人必须占据位置 J(2j+1) ：

J(2j+1) = 地图_奇数(J(j)) = 2.J(j) + 1

绘制第二个递归关系：

对于任何整数 n，我们有：
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”表示“移位”）。我们观察的数学翻译是 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)

假设对于任意 k 满足 k ∈ [1,n]，J(k) = 1 + 2.s(k)，让我们证明 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，其中 m(n), s(n) ∈ ℕ 唯一整数，使得
2 ^m(n) ≤ n < 2 ^m(n)+1和 s(n ) = n - 2 ^m(n)
换而言之：m(n) = ⌊ln ₂ (n)⌋ 和 s(n) = n - 2 ^{⌊ln ₂ (n)⌋}</sup>

Answer 2

从几个简单的例子开始，做出猜测，然后使用归纳法来（反）证明你的猜测。

考虑 n = 2 的某个幂。

J(2^0) = 1（给定）

J(2^1) = 2J(2^0) - 1 = 1

J(2^2) = 2J(2^1) - 1 = 1

好的，让我们猜测所有 n >= 1 的 J(n) = 1。

基本情况：J(1) = 1，根据定义这是正确的。

归纳步骤：假设某个任意 k 的 J(k) = 1。那么 J(2k) = 2J(k) - 1 = 1。

因此，通过归纳，所有 n 的 J(n) = 1（假设除法向下舍入为整数）。

Answer 3

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

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

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

T(n)=2*T(n/2)， 在哪里T(n)=J(n)-1

T(n)=2^log2(n)*T(1)

J(n)=2^log2(n)*(J(1)-1)+1