0 
def hanoi_move ( start , via , target ,n ,k ):
    """ finds the k-th move in an Hanoi Towers instance
    with n discs """
    if n <=0:
        return "zero or fewer disks"
    elif k <=0 or k >=2** n or type(k )!= int :
        return "number of moves is illegal"
    elif k ==2**( n -1):
        return str . format ("disk {} from {} to {}",n , start , target )
    elif k <2**( n -1):
         return hanoi_move ( start , target , via ,n -1 , k)
    else:
        return hanoi_move ( via , start , target ,n -1 ,k -2**( n -1))

为什么要看 2^(n-1) 移动？你能解释一下代码吗？

4

1 回答 1

3

TL;DR 版本 - 将一堆 n-1 个磁盘从一个位置移动到另一个位置需要 2^(n-1)-1 次移动，因此此代码正在查看您是否正在移动第 n 个磁盘，或者将 n-1 个磁盘堆栈移入或移出第 n 个磁盘。

完整答案：

理解为什么此代码查看第 (n-1) 步以确定第 k 步是什么，需要了解移动整个河内塔背后的基本思想。

让我们看一个例子。我们有点 A、B 和 C，以及从位置 A 开始的 10 个磁盘塔，我们要移动到位置 C。我们会说磁盘 9 是最大的，其次是 8，等等。开始，它看起来像这样：

A 9876543210
B
C

那么我们如何将所有内容移到 C 中呢？好吧，我们需要将基础磁盘 (9) 移至 C，因此我们首先将其他所有内容移出它，如下所示：

A 9
B 876543210
C

然后我们可以移动磁盘 9

A
B 876543210
C 9

然后将九个磁盘的堆栈移回磁盘 9，最终结果如下：

A
B
C 9876543210

当然，我跳过了如何移动九个磁盘堆栈的整个部分，但这为您提供了基本概念 - 移动堆栈需要将除底部磁盘之外的所有磁盘移开，然后移动底部磁盘，然后将其余磁盘移回其顶部。

所以这段代码在问“我们在这个过程中的什么位置？” 如果k等于 2^(n-1)，那么我们当前正在移动我们当前尝试移动的堆栈的底部磁盘。如果k小于那个值，我们仍在将磁盘堆栈从底部磁盘移走的过程中。如果k大于，我们正试图将磁盘堆栈移回底部磁盘。使用我上面的简单示例，如果k= 2^(10-1) = 2 ^ 9 = 512，那么我们正在将磁盘 9 从 A 移动到 C。如果k小于 512，那么我们仍在移动磁盘 0通过 8 离开磁盘 9 并进入点 B。如果k大于 512，那么我们在k-512 移动到将磁盘 0 到 8 从点 B 移回点 C 中的磁盘 9。

我们怎么知道 2^(n-1) 是正确使用的值？使用数学归纳法，我们可以证明最多需要 (2^n)-1 次移动来移动一堆 n 个磁盘。这是一个快速的证明：

归纳的基础：要移动一堆 n=1 磁盘，需要 (2^n)-1=(2^1)-1=1 移动 - 移动唯一的磁盘。归纳步骤：假设它适用于 n 个磁盘（即移动堆栈的最有效方式需要 (2^n)-1 次移动）。然后，要移动一堆 n+1 个磁盘，我们首先使用最有效的方法将顶部的 n 个磁盘从底部的磁盘上移开（采取 (2^n)-1 次移动），移动底部的磁盘（1 次移动） ，然后将其他 n 个磁盘移回底部磁盘的顶部（(2^n)-1 再次移动）。所以我们总共走的步数是 (2^n)-1+1+(2^n)-1=2*(2^n)-1=(2^(n+1))-1 步.

如果您之前没有见过归纳法，这可能看起来很复杂，但基本思想是这样的——因为我们知道它适用于一个磁盘，我们知道它适用于两个磁盘。由于我们现在知道它适用于两个磁盘，因此它适用于三个磁盘。因为我们现在知道它适用于三个磁盘......等等。归纳步骤适用于任意 n，因此我们可以根据需要多次应用它。所以对于任何有限的 n，我们知道移动 n 个磁盘的最快方法需要 (2^n)-1 次移动。

所以现在的问题是，第 n 个磁盘移动到哪一步了？在第 (2^(n-1))-1 次移动中，我们可以完成将 n-1 个磁盘堆栈移动到底部磁盘顶部。然后，在第 (2^(n-1))-1+1=2^(n-1) 次移动中，我们能够移动底部磁盘。

于 2014-02-13T19:31:00.390 回答