algorithm - 汉诺塔封闭式解决方案

Question

所以我正在尝试为汉诺塔问题找到封闭形式的解决方案。我知道递归关系是 T(n) = 2T(n-1) + 1，因为它需要 T(n-1) 来回移动塔顶，这就是为什么有两个，而“+ 1"是移动基地。但是，我无法理解为什么封闭解是 2^n - 1。

当我尝试求解答案并使用反向替换时，我得到的结果是:T(n) = 8T(n-3) + 4 + 2 + 1，即 T(n) = 2 ^k (T(n - k)) + 2^k-1 + 2^k-2 + 2^k-3 其中 k 是步骤？我知道最后一部分也是几何级数，这意味着它是 2^(n + 1) - 1/(2-1)。但我就是不明白答案从何而来。

编辑:是不是因为几何级数部分不是2^k + 2^k-1 + ... + 2^k-k？这意味着几何级数不是 2^n + 1 - 1，而是 2^n - 1。我们使用 H(0) 作为基本情况 --> 所以 H(n - k)，使用 k = n ？

Answer 1

你可以很容易地用归纳法证明它。我们假设 T(n) = 2^n - 1 对于给定的 n 为真。然后:

T(n+1) = 2*T(n) + 1
       = 2*(2^n-1) + 1
       = 2^(n+1) - 2 + 1
       = 2^(n+1) - 1

我们知道 T(0) = 0 = 2^0 - 1 它证明了对于任何 n 等式 T(n) = 2 ^n - 1 为真。