河內塔的遞歸解決方案

Question

我正在閱讀RobetSedwick在C++中的算法。這裏的作者正在使用分而治之的設計和復發來解釋河內的塔樓。

後續代碼是對問題的遞歸解決方案。它指定哪一個磁盤應該在每一步移動，以及在哪個方向上移動（+表示將一個釘移動到右側，在最右側釘上時移動到最左側的釘;並且 - 表示將一個釘移動到左側，循環到當最左邊的釘子時最右手）。

Disk3   
Disk2 
Disk1 

Peg1  Peg2 Peg3 

我的問題是什麼意思筆者上面的「自行車最左邊掛」時，盤上留下PEG（即，PEG 1）我們如何循環到最左邊的掛？

作者還提到，遞歸基於以下想法：要將N個磁盤向右移動一個釘，我們首先將頂部N-1個磁盤移動到左側，然後將磁盤N移到右側，然後將N個磁盤移到右側將N-1個磁盤再向左移一個釘（在磁盤N上）。

我對上面的左右術語感到困惑。任何人都可以解釋。

void hanoi(int N, int d) 
    { 
    if (N == 0) return; 
    hanoi(N-1, -d); 
    shift(N, d);  
    hanoi(N-1, -d); 
    } 

Answer 1

這只是意味着：

自行車向右：

peg1 -> peg2 
peg2 -> peg3 
peg3 -> peg1 

自行車向左

peg1 -> peg3 
peg2 -> peg1 
peg3 -> peg2