c++ - 河内扩展塔

问题定义

我正在尝试编写一个C++程序来解决Extended Hanoi Tower问题。

河内扩展塔类似于标准河内问题。区别在于，奇数环在 A (1、3、5 ...)中，偶数环在 B (2、4、6 ...)中。这个问题问，如何将所有环以递归的方式转移到 C ？
我已经写了到目前为止的工作。
任何帮助我实现我的方法的帮助或实现该程序的任何想法，将不胜感激!
谢谢 !

规则

1.一次只能移动一个磁盘。
2.请勿在较小的磁盘上放置任何磁盘。
3.输出应包含必要的 Action ，而不是最小的必要 Action
4.磁盘总数可以是偶数或奇数。
5.实现应该是递归的。

方法1

我们假设已经解决了当前在A和B中的n-1个环的问题。这意味着它们都移到了C，并且C具有2n-2有序环。之后，我们必须处理A和B中剩余的环。这意味着我们必须取较小的环并将其放在较大的环上(从B到A)。之后，我们必须合并C(2n-2)中的环和A(2)中的环。最后，我们必须使用标准的Hanoi解决方案来实现我们的目标，并将所有环移动到C。

实现1

int main()
{
    long int n;
    cin >> n;
    // move odd & even rings to the first shaft, recursively
    customHanoi(n);
    // move all rings from first shaft to the destination shaft, recursively
    standardHanoi(n);
    return 0;
}

// the shaft holds the odd rings: A
// the shaft holds the even rings: B
// the final destination shaft: C
void customHanoi(int n, char A, char B, char C)
{
    if (n == 1)
        return;
    else if (n == 2)
    {
        cout << B << " " << A << endl;
        return;
    }
    else if (n == 3)
    {
        cout << A << " " << C << endl;
        cout << B << " " << A << endl;
        cout << C << " " << A << endl;
    }
    else
    {
        // here we have some missing code !
    }
}

// a recursive function to find the solution for standard hanoi
void standardHanoi(int n, char from, char helper, char to)
{
    // the base condition
    if (n == 1)
    {
        cout << from << " " << to << endl;
        return;
    }
    // the recursive calls
    standardHanoi(n - 1, from, to, helper);
    cout << from << " " << to << endl;
    standardHanoi(n - 1, helper, from, to);
}

相关资源

Link

最佳答案

我们可以将A中的1比2放到B上。

我们可以将B超过1,2的3放在标准河内的A上。所有其他磁盘都更大，可以忽略。

我们可以将标准河内的A，4上的1,2,3放到B上。所有其他磁盘都更大，可以忽略。 ........

当我们将所有磁盘排列在一个极点上时，它们要么位于A(如果磁盘总数为奇数)上，要么位于B(偶数)上。

将它们全部移到Standard Hanoi的C中。

虽然，这可能是一种迭代方法，但是您要求递归方法。

因此，递归:假设总共有n个磁盘。通过递归应用程序将n-1磁盘移动到C。将标准河内的n-1磁盘从C移到A(n为奇数)或B(n为偶数)。通过标准河内将生成的n磁盘移动到C。

这与您建议的内容非常相似，只是n代表磁盘总数(环)。它也不是纯粹的递归。

关于c++ - 河内扩展塔，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/47835192/