河内塔(算法)

The Tower of Hanoi

【河内塔】的任务是：把棒Ｘ上的ｎ枚圆盘，可以利用棒Ｙ，都搬到棒Ｚ上。

这个人物可以分成三个小任务。①、棒Ｘ上的ｎ-１枚圆盘，可以利用棒Ｚ，都搬到棒Ｙ上。②、棒Ｘ剩下的最大的一枚圆盘移到棒Ｚ上。③、棒Ｙ剩下的ｎ-１枚圆盘，可以利用棒Ｘ，都搬到棒Ｚ上。 void CHanoiDlg::Hanoi(int n, int x, int y, int z)   //【河内塔】的任务
{ 
    if (n > 1) 
    {
        Hanoi(n - 1, x, z, y);         // 小任务の①
        Move(x, z);                     // 小任务の②
        Hanoi(n - 1, y, x, z);         // 小任务の③ 
    }
    else 
        Move(x, z);                     //一枚圆盘
}

用按钮控件，实现【河内塔】游戏的動画。

创建一个对话框工程，贴五个按钮。必须做到这五个按钮的ID从IDC_BUTTON1到IDC_BUTTON5的资源值是连续的。按钮的位置和大小将在程序里处理，所以位置和大小将随便设一下即可。为了起动動画，再增加一个[Go]按钮。代码如下。

#define NN 100
char TowerArray[3][10];
#define TOWER_MAX 5

void CHanoiDlg::Move(int a1, int a2)
{
    char c1 = TowerArray[a1][strlen(TowerArray[a1])-1];
    TowerArray[a1][strlen(TowerArray[a1])-1] = '\0';    
    TowerArray[a2][strlen(TowerArray[a2])] = c1;    
    TowerArray[a2][strlen(TowerArray[a2])+1] = '\0';    
    
    UINT uiID = (c1 - '1') + IDC_BUTTON1;
    CRect r1;
    GetDlgItem(uiID)->GetWindowRect(&r1);
    ScreenToClient(&r1);
    int dx = (a2 - a1) * 150;
    int dy = -((int)strlen(TowerArray[a2]) - (int)strlen(TowerArray[a1]) - 1) * r1.Height();
    for (int i = 1; i <= NN; i ++)
    {
        CRect rr = r1;
        rr.OffsetRect(dx * i / NN, dy * i / NN);
        GetDlgItem(uiID)->MoveWindow(&rr);
        
        MSG msg;
        while(::PeekMessage(&msg, NULL, NULL, NULL, PM_NOREMOVE))
        {
            if (!AfxGetApp()->PumpMessage())
                break;
            Sleep(2);
        }
    }
}

void CHanoiDlg::Hanoi(int n, int x, int y, int z)           
{                                                       
    if(n == 1)   
        Move(x, z);           
    else
    {
        Hanoi(n - 1, x, z, y);   
        Move(x, z);   
        Hanoi(n - 1, y, x, z);   
    }   
}   

void CHanoiDlg::OnButtonGo() 
{
    memset(TowerArray, '\0', sizeof(TowerArray));
    strcpy(TowerArray[0], "12345");

    GetDlgItem(IDC_BUTTON5)->MoveWindow(50,10,60,29);
    GetDlgItem(IDC_BUTTON4)->MoveWindow(40,40,80,29);
    GetDlgItem(IDC_BUTTON3)->MoveWindow(30,70,100,29);
    GetDlgItem(IDC_BUTTON2)->MoveWindow(20,100,120,29);
    GetDlgItem(IDC_BUTTON1)->MoveWindow(10,130,140,29);

    Hanoi(TOWER_MAX, 0, 1, 2);
}