2

我正在阅读Robert Sedgewick 的算法

以下是第 213 页的摘录，涉及数字二进制表示中尾随零的数量。

对于 Hanoi 塔问题，与 n 位数对应的含义是该任务的简单算法。我们可以通过以下两个步骤将桩向右移动一个钉子，直到完成：

  1. 如果 n 为奇数，则将小圆盘向右移动（如果 n 为偶数，则向左）
  2. 进行不涉及小磁盘的唯一合法移动。

也就是说，在我们移动小 dsik 之后，另外两个 peg 包含两个磁盘，一个比另一个小。唯一不涉及小磁盘的合法移动是将较小的磁盘移动到较大的磁盘上。其他所有移动都涉及较小的磁盘，原因与其他所有数字都是奇数并且规则上的所有其他标记都是最短的相同。

上面的文字并没有进入我的脑海，即使在阅读了来自谷歌信息的各种参考资料之后。

请帮我举一个简单的例子，例如磁盘 N = 3。Disk3 最大，Disk1 最小，它们需要从 PegA 移动到 PegB。

Disk1
Disk2
Disk3
-------       ------------         ------------
Peg A            Peg B                 Peg C
4

3 回答 3

4

这里首先要注意的是，在这个算法中，第一个 peg 被认为在最后一个 peg 的右边，最后一个 peg 被认为在第一个 peg 的左边。

重复应用列出的两个步骤将导致n磁盘塔被一个钉子向右移动。

在这种情况下n = 3,n是奇数，所以这两个动作是：

  1. 向右移动Disk1一个钉子。
  2. 做出唯一不涉及的合法举动Disk1。

通过重复这些动作给出以下解决方案：

  1. Disk1: PegA -> PegB（向右移动Disk1一个钉子）
  2. Disk2: PegA -> PegC（仅合法举动不涉及Disk1）
  3. Disk1: PegB -> PegC（向右移动Disk1一个钉子）
  4. Disk3: PegA -> PegB（仅合法举动不涉及Disk1）
  5. Disk1: PegC -> PegA（向右移动Disk1一个钉子）
  6. Disk2: PegC -> PegB（仅合法举动不涉及Disk1）
  7. Disk1: PegA -> PegB（向右移动Disk1一个钉子）

当他写“与 n 位数字的对应关系”时，Sedgewick 指的是这样一个事实，即您在k解决方案的步骤中移动的磁盘是对应1于二进制表示中的最低有效位的磁盘k。即n = 3：

step | bits | disk
------------------
  1  |  001 |  1
  2  |  010 |  2
  3  |  011 |  1
  4  |  100 |  3
  5  |  101 |  1
  6  |  110 |  2
  7  |  111 |  1
于 2012-09-10T09:29:38.273 回答
0

那么这个特定问题的解决方案是：移动Disk1到Peg B，移动Disk2到Peg C，移动Disk1到Peg C，移动Disk3到Peg B，移动Disk1到Peg A，移动Disk2到Peg B，移动Disk1到Peg B。完毕。

于 2012-09-10T08:59:18.827 回答
0

如果这对任何人都有帮助，我在这里用 python 编写了一个完整的解决方案：https ://github.com/goblinhack/towers-of-hanoi

#!/usr/bin/env python
#
# The way to solve this is quite simple but does differ slightly for N = odd or even numbers of rings.
# 
# At each move you do either a) or b):
# 
# a) move the "1" value to the peg to the right, wrapping around to the first peg if needed
# 
# b) make the only other legal move
# 
# And then repeat either a) or b) for (2 ^ numrings) - 1.
# 
# So for N=3, you would do the above steps 7 times.
# 
# The catch that I alluded to earlier is that for N == odd (3,5,...), you will need to repeat this
# entire algorithm one more time as the above will only move the rings one peg to the right. 
#
import sys

#
# Print the tower so we can check our progress
#
def print_tower(pegs, nrings):
    npegs = len(pegs)
    for y in range(0, nrings):
        h = nrings - y
        for x in range(0, npegs):
            if len(pegs[x]) >= h:
                sys.stdout.write(str(pegs[x][len(pegs[x]) - h]) + " ")
            else:
                sys.stdout.write("| ")
        print("")
    print("-----")

def solve_tower(nrings, npegs):
    pegs = []
    for peg in range(0, npegs):
        pegs.append([])

    #
    # push the nrings on
    #
    for i in range(0, nrings):
        pegs[0].append(i + 1)

    #
    # For N == odd numbers we will need to repeat this twice
    #
    for tries in range(0, 1 + nrings % 2):
        print_tower(pegs, nrings)
        move_peg_one_right = True

        #
        # Repeat the steps a) or b) for 2^N-1 times
        #
        for moves in range(0, (1 << nrings) - 1):
            #
            # step a)
            #
            if move_peg_one_right:
                for peg in range(0, npegs):
                    if len(pegs[peg]):
                        if pegs[peg][0] == 1:
                            next_peg = (peg + 1) % npegs
                            pegs[next_peg].insert(0, pegs[peg].pop(0))
                            print("Moving value 1 from peg {} to peg {}\n".format(peg + 1, next_peg + 1))
                            break
            else:
                #
                # step b)
                #
                moved_a_ring = False
                for peg in range(0, npegs):
                    #
                    # Look for a ring on a peg to move
                    #
                    if len(pegs[peg]):
                        value = pegs[peg][0]
                        #
                        # Don't move the ring value "1" as we move that in a)
                        #
                        if value != 1:
                            for next_peg in range(0, npegs):
                                #
                                # The next peg is the one to the right of this peg. If we reach the last peg then we
                                # need to move to the first peg.
                                #
                                next_peg = (peg + next_peg) % npegs

                                #
                                # Don't move to the same peg; that would be silly
                                #
                                if next_peg == peg:
                                    continue

                                #
                                # If the destination peg is empty, move there
                                #
                                if not len(pegs[next_peg]):
                                    pegs[peg].pop(0)
                                    pegs[next_peg].insert(0, value)
                                    moved_a_ring = True
                                    print("Moving value {} from peg {} to empty peg {}\n".format(value, peg + 1, next_peg + 1))
                                    break
                                elif value < pegs[next_peg][0]:
                                    #
                                    # Else if the destination peg has a lower value, move there
                                    #
                                    pegs[peg].pop(0)
                                    pegs[next_peg].insert(0, value)
                                    moved_a_ring = True
                                    print("Moving < value {} from peg {} to peg {} dest {}\n".format(value, peg + 1, next_peg + 1, pegs[next_peg][0]))
                                    break
                    if moved_a_ring:
                        break

                if not moved_a_ring:
                    print("Error, failed to move")
                    sys.exit(1)

            print_tower(pegs, nrings)

            #
            # Alternate between a) and b)
            #
            move_peg_one_right = not move_peg_one_right

        print("Finished pass\n")

nrings = 3
npegs = 3
solve_tower(nrings, npegs)
于 2021-03-13T11:22:35.317 回答