扩展河内塔

Question

问题定义
我正在尝试编写一个 C++ 程序来解决 Extended Hanoi Tower 问题。
扩展的河内塔类似于标准的河内问题。不同之处在于，奇数环在 A (1, 3, 5, ...) 中，偶数环在 B (2, 4、6、...）。问题是，我们如何以递归的方式将所有环转移到C？

我已经写下了我到目前为止所做的。任何帮助我实施我的方法或实施该计划的任何想法都将不胜感激！谢谢！

规则
1.一次只能移动一个磁盘
2. 没有磁盘可以放在较小的磁盘之上。
3.输出应该包含必要的动作，而不是最小必要的动作
4.磁盘总数可能是偶数或奇数.
5. 实现应该是递归的。

方法一
我们假设当前在 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

Answer 1

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

我们可以通过标准河内将 B 的 1,2 放在 A 的 3 上。其他盘都比较大，可以忽略。

我们可以通过标准河内将 A 中的 1、2、3 放在 B 上的 4 上。所有其他磁盘都较大，可以忽略。 .........

当我们将所有圆盘排列在一根柱子上时，它们要么在 A（如果圆盘总数为奇数），要么在 B（偶数）。

通过 Standard Hanoi 将它们全部移动到 C。

不过，这可能被认为是一种迭代方法，而您要求的是递归方法。

因此，递归：假设总共有 n 个磁盘。通过递归应用将 n-1 个磁盘移动到 C。 Standard Hanoi 将 n-1 个圆盘从 C 移动到 A（n 为奇数）或 B（n 为偶数）。通过 Standard Hanoi 将生成的 n 磁盘移动到 C。

这与您提出的非常相似，只是 n 代表磁盘（环）总数。它也不是纯粹的递归。

Answer 2

非常感谢@Will-Ness！！
这是可能的解决方案之一。
希望这可以帮助！ :)

#include <iostream>
using namespace std;

// function declarations
void customHanoi(long int, char = 'A', char = 'B', char = 'C');
void standardHanoi(long int, char = 'A', char = 'B', char = 'C');

int main()
{
    // initialize the variable
    long int n;
    // getting the number of rings
    cin >> n;
    // move odd & even rings to the first shaft, recursively
    // after that move all rings from first shaft to the destination shaft
    customHanoi(n);
    // our program finished successfully
    return 0;
}

// A: the shaft that holds odd rings
// B: the shaft that holds even rigns
// C: the final destination shaft
void customHanoi(long int n, char A, char B, char C)
{
    // initialize the variable
    static long int level = 1;

    // we can't handle zero/negative disk
    if (n < 1)
        return;

    // the base condition of recursion
    if (level == n)
    {
        // now, we moved all rings to the first shaft
        // so, we have to move them to the destination shaft
        standardHanoi(n);
        // finish the execution of recursion
        return;
    }

    // reordering the disks
    // based on even or odd number of disks & current level
    if (n % 2 == 1)
    {
        if (level % 2 == 1)
            standardHanoi(level, A, C, B);
        else
            standardHanoi(level, B, C, A);
    }
    else
    {
        if (level % 2 == 1)
            standardHanoi(level, B, C, A);
        else
            standardHanoi(level, A, C, B);
    }

    // go to the next level, it helps us control the flow
    level++;
    // the recursive calls
    customHanoi(n);
}

// a recursive function to find the solution for standard hanoi
void standardHanoi(long 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);
}

扩展河内塔

Extended Hanoi Tower

c++

recursion

towers-of-hanoi