c++ - Tower of Hanoi - n peg 求解算法

Question

我正在实现汉诺塔问题以更多地了解递归。我能够使用 3 peg 的情况来实现它，但是，当我想使用更多的 peg(以产生更少的移动)时，我理解 Frame-Stewart 解决方案，我必须打破我拥有的磁盘数量并堆叠到 一个 Hook ，并且在我将磁盘从源 Hook 转移到带有所有中间 Hook 的目标 Hook 时，永远不要碰那个 Hook 。但是，我不明白如何将 move(disks, 1, i, {2...K}) 之类的东西写成一个函数。当我从一开始就不知道它们时，我怎么能在函数原型(prototype)中写下所有钉子的名称？我在下面给出了我为 3 磁盘解决方案所做的工作，但在更一般的情况下我需要帮助。

// private member function: primitive/basic move of the top disk
    // from the source peg to the destination peg -- and legality-check
    void move_top_disk(int source, int dest)
    {
        cout << "Move disk " << towers[source].front() << " from Peg ";
        cout << source+1 << " to Peg " << dest+1;
        towers[dest].push_front(towers[source].front());
        towers[source].pop_front();
        if (true == is_everything_legal())
            cout << " (Legal)" << endl;
        else 
            cout << " (Illegal)" << endl;
    }

    // private member function: recursive solution to the 3 Peg Tower of Hanoi
    void move(int number_of_disks, int source, int dest, int intermediate)
    {
        if (1 == number_of_disks)
        {
            moves++;
            move_top_disk (source, dest);
        }
        else 
        {
            moves++;
            move (number_of_disks-1, source, intermediate, dest);
            move_top_disk (source, dest);
            move (number_of_disks-1, intermediate, dest, source);
        }
    }

我不明白我需要对我的“移动”功能进行什么样的更改才能解决 6 个钉子的问题。谢谢

Answer 1

您将需要修改最后一个代码块，它移动的位置，move-top-disk，move。

这里是关于 N 钉的汉诺塔解决方案的文章:Towers of Hanoi with K pegs