用10塊板解決河內塔遞歸C++

Question

試圖解決河內的塔，我真的不明白爲什麼我的功能無法正常工作。我已經在這裏檢查了每個C++解決方案。

bool CPlayer::MoveTop(int n, int from, int to) 
{ 
    if (n == 0) 
    { 
     m_towers.MoveDisc(to, 1); 
     return true; 
    } 

    MoveTop(n -1 , from , 1); 

    m_towers.MoveDisc(1,from); 

    MoveTop(n - 1, 1, to); 

}// MoveTop 

其中1是中間掛鉤。而m_tower.MoveDisc（從，）將一張光盤從一個釘到另一個釘。

這是第一次調用MoveTop函數。

void CPlayer::OnRun() 
{ 
    bool ok = MoveTop(10,0,2); 

}// OnRun 

我也得到一個返回上稱爲PEG板數的高度的功能，但我真的不認爲我需要它。

增加了更多的問題形容 的移動的所有圖形中的窗口，在這裏，我可以看到的板如何從栓移動到栓的結果被示出。而現在，它不會簡單地做它應該做的。在運行代碼時，第一個平臺移動到樁1（中間的樁）並「上下跳動」。

這些都是可用的功能：

高度功能：

int CTowers::Height(int tower) 
{ 
    ASSERT(torn>=0 && torn<3); 

    return m_height[torn]; 
} 

具體的塔返回的高度。

int CTowers::TopSize(int tower) 
{ 

     int h = Height(tower); 
     if (h==0) 
      return 1000; 
     else return DiscSize(torn, h-1); 
} 

返回掛鉤上的大小。

int CTowers::DiscSize(int tower, int place) 
{ 
    ASSERT(place < Height(torn)); 

    return m_pinne[tower][place]; 
} 

返回指定的dicssize。

bool CTowers::MoveDisc(int to, int from) 
{ 
    if (m_abort) 
     return false; //  

    m_pView->DrawAnimation(from, to); 

    if (TopSize(from)>=TopSize(to)) 
     return false; 
    m_numMoves++; 
    int ds = Pop(from); 
    Push(to, ds); 
    m_pView->Invalidate(); 
    return true; 
} 

將光盤從一個掛鉤移動到另一個掛鉤。

Answer 1

這是一個老派:)分&征服問題。

試着看一下這個代碼：

void hanoi(int diskSize, int source, int dest, int spare) 
{ 
    //This is our standard termination case. We get to here when we are operating on the 
    //smallest possible disk. 
    if(diskSize == 0) 
    { 
     std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl; 
    } 
    else 
    { 
     //Move all disks smaller than this one over to the spare. 
     //So if diskSize is 5, we move 4 disks to the spare. This leaves us with 1 disk 
     //on the source peg. 
     //Note the placement of the params. 
     //We are now using the dest peg as the spare peg. This causes each recursion to ping-pong 
     //the spare and dest pegs. 
     hanoi(diskSize - 1, source, spare, dest); 

     //Move the remaining disk to the destination peg. 
     std::cout << "Move disk " << diskSize << " from peg " << source << " to peg " << dest << endl; 

     //Move the disks we just moved to the spare back over to the dest peg. 
     hanoi(diskSize - 1, spare, dest, source); 
    } 
} 

具有3個參數的想法（來源，DEST，備用）是能夠知道每個PEG是備用一個讓你可以使用時間它把磁盤放在上面。

正如評論中所述，備用和dest之間的遞歸ping-pongs。

您的代碼可以不尊重地方你不能把一個更大的磁盤上更小的磁盤頂部的規則（見here）。所以你需要一個變量來保持的目標掛鉤，而不是像你的代碼那樣總是1。

這就是爲什麼你需要3個參數。

乾杯！