在河内塔问题是递归的一个经典问题。给您3个钉，其中一个上有磁盘，并且必须按照给定的规则将所有磁盘从一个钉移动到另一个钉。您还必须以最少的移动次数执行此操作。

这是解决问题的递归算法：

void Hanoi3(int nDisks, char source, char intermed, char dest)
{
    if( nDisks > 0 )
    {
        Hanoi3(nDisks - 1, source, dest, intermed);
        cout << source << " --> " << dest << endl;
        Hanoi3(nDisks - 1, intermed, source, dest);
    }
}


int main()
{
    Hanoi3(3, 'A', 'B', 'C');

    return 0;
}

现在，想象同样的问题，只有4个钉子，所以我们添加了另一个中间钉子。当面对必须在任一点上选择哪个中间钉的问题时，我们将选择最左边的一个，以防多于一个空闲钉。

对于此问题，我具有以下递归算法：

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest)
{
    if ( nDisks == 1 )
        cout << source << " --> " << dest << endl;
    else if ( nDisks == 2 )
    {
        cout << source << " --> " << intermed1 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed1 << " --> " << dest << endl;
    }
    else
    {
        Hanoi4(nDisks - 2, source, intermed2, dest, intermed1);
        cout << source << " --> " << intermed2 << endl;
        cout << source << " --> " << dest << endl;
        cout << intermed2 << " --> " << dest << endl;
        Hanoi4(nDisks - 2, intermed1, source, intermed2, dest);
    }
}

int main()
{
    Hanoi4(3, 'A', 'B', 'C', 'D');

    return 0;
}

现在，我的问题是如何将这种递归方法推广到K钉子上？递归函数将收到一个char[]包含每个堆栈的标签的，因此该函数将如下所示：

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

我知道帧斯图尔特算法，这是最有可能的优化，但没有得到证实，和它给你的 号码
的移动。但是，我对严格的递归解决方案感兴趣，该解决方案遵循3钉和4钉的递归解决方案的模式，这意味着它可以打印实际的移动。

至少对我来说，Wikipedia上提出的Frame-
Stewart算法的伪代码是相当抽象的，而且我还没有成功地将其翻译成可打印动作的代码。我会接受该参考实现（对于random k），或更详细的伪代码。

我试图提出一种可以相应地对标签数组进行排列的算法，但是我没有运气让它起作用。任何建议表示赞赏。

更新：

用功能语言解决起来似乎容易得多。这是一个基于LarsH的Haskell解决方案的F＃实现：

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest when rest.IsEmpty        
            ->  HanoiK (n-1) (p1::p3::p2::rest)
                printfn "%A --> %A" p1 p2
                HanoiK (n-1) (p3::p2::p1::rest)    
        | p1::p2::p3::rest when not rest.IsEmpty    
            ->  let k = int(n / 2)
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

let _ =
    HanoiK 6 [1; 2; 3; 4; 5; 6]

并且不将3钉作为边缘包：

let rec HanoiK n pegs = 
    if n > 0 then 
        match pegs with
        | p1::p2::rest when rest.IsEmpty            
            ->  printfn "%A --> %A" p1 p2
        | p1::p2::p3::rest     
            ->  let k = if rest.IsEmpty then n - 1 else int(n / 2) 
                HanoiK k (p1::p3::p2::rest)
                HanoiK (n-k) (p1::p2::rest)
                HanoiK k (p3::p2::p1::rest)

请注意，这无法处理没有解决方案的退化案例，例如 HanoiK 2 [1; 2]