用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个参数。

干杯！