プログラミングメモ →目次

ハノイの塔(アルゴリズム)

The Tower of Hanoi

【ハノイの塔】の任務は、棒Xに刺さっているn枚の円盤を、棒Yも使って、すべて棒Zに移動することです。

この任務は、3つの小任務に分けられます。①、棒Xに刺さっているn-1枚の円盤を、棒Zも使って、すべて棒Yに移動する。②、棒Xに残っている一番大きい円盤を棒Z移動する。③、棒Yに刺さっているn-1枚の円盤を、棒Xも使って、すべて棒Zに移動する。

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);                     //円盤が1枚しかない
}

ボタンで、【ハノイの塔】の動画を実現します。

ダイアログベースで、ボタンを5つ貼り付けます。必ず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);
}