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

The Tower of Hanoi【ハノイの塔】の任務は、棒Ｘに刺さっているｎ枚の円盤を、棒Ｙも使って、すべて棒Ｚに移動することです。 この任務は、３つの小任務に分けられます。 ①、棒Ｘに刺さっているｎ-１枚の円盤を、棒Ｚも使って、すべて棒Ｙに移動する。②、棒Ｘに残っている一番大きい円盤を棒Ｚ移動する。 ③、棒Ｙに刺さっているｎ-１枚の円盤を、棒Ｘも使って、すべて棒Ｚに移動する。

source for youtube demo

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

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

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