前回思いついたことを、少し掘り下げて考えてみました。

 

1.参照したプログラムは何をしているのか?(その黙示の前提は?)

もっと簡略化した日本語C#版のプログラムを載せます。

//////////////////////////////////////////////////////////////////
// TowerOfHanoi01.cs
// Tower of Hanoi, a mathimatic game
// https://www.programmingalgorithms.com/algorithm/tower-of-hanoi/
//////////////////////////////////////////////////////////////////

using System;

class TowerOfHanoi
{
    public static void Main()
    {
        int num = 0;    //塔の盤の段数
        Console.Write("円盤の枚数(整数)を入力してください:");
        while(!int.TryParse(Console.ReadLine(), out num) || num <= 0)
        {
            Console.Write("\n円盤の枚数(整数)を入力してください:");
        }
        TowerofHanoi(num, 1, 2, 3);    //「ハノイの塔」関数(num段の柱を1→2へ移動)
        Console.ReadKey();    //コンソールを閉じさせない為
    }

    //「ハノイの塔」関数(num段の柱を1→2へ移動)
    public static void TowerofHanoi(int diskCount, int fromPole, int toPole, int viaPole) 
    {
        if(diskCount > 0)    //num段を1まで減らしてゆく
        {

           //「ハノイの塔」関数(num - 1段の柱を1→2へ移動)
            TowerofHanoi(diskCount - 1, fromPole, viaPole, toPole);
            //最下段の盤を1→2へ移動

            Console.WriteLine(diskCount + "番目の盤を" + fromPole + "番の柱から" + toPole + "番の柱へ移動します。");
            //「ハノイの塔」関数(num - 1段の柱を3→2へ移動)

            TowerofHanoi(diskCount - 1, viaPole, toPole, fromPole)   //num-  1段の「ハノイの塔」関数、柱は3→2へ移動
        }
    }
}

 

いかがでしょう?コメントを総合すると、

「ハノイの塔」関数(num, 1→2) = 「ハノイの塔」関数(num - 1, 1→3へ移動)+ 「ハノイの塔」関数(最下段1段, 1→2へ移動)+「ハノイの塔」関数(num - 1, 3→2)

即ち「ハノイの塔を1→2へ移動させることは、まず最下段を除く塔をいったん退避させ、最下段を目的の柱に移し、更に塔を退避先から目的の柱(toPole)へ移動させる」ことに等しい、ということが分かります。また退避は1(fromPole)と3(viaPole)を交互に使い、往復させながら、最下段の盤を目的の柱へ積み上げてゆく」という動作を行っていることが分かります。

プログラムのポイントはこの「」動作に再帰を使っていることです。

因みに盤と動きの数を調べてみると、

盤数  動き  差分

1    1    1

2    3    2

3    7    4

4    15    8

となり、2の盤数の階乗の和(Σ 2^k(n, k = 0))になっていることが分かります。

 

2.必要なオブジェクト

(1)表示母体(コンソールを含む描画背景)

動作を視覚表現するための描画背景が必要であり、ウィンドウとピクチャーボックスを使うことになりそうです。ウィンドウの大きさから塔の高さ(=盤数)には自ずと制限が出てきます。まぁ、16段ぐらいにしておきましょうか?

 

(2)盤と盤数の取り扱い

盤はビットマップで表現することになりそうですね。幅64 x 高さ16のビットマップで左右1ドット(計2ドット)ずつ減らしてゆくと32 x 16が一番上の盤(他は余白)になりますが、もっと差を設けたいですね。幅を増やすべきでしょう。これら16個のビットマップはImageListで管理することが簡単そうです。また、このビットマップは座標のある「盤クラス」のオブジェクトで描画することになるでしょう。

 

(3)柱とスタック

「ハノイの塔」を見て最初に感じるのは、この盤を嵌めたり、抜いたりする動作が「先入れ後出し(First In Last Out-FILO)」というスタックになっていることです。(盤を嵌める→PUSH、盤を抜く→POP)「塔クラス」のオブジェクトを3つ作り、塔にどの盤オブジェクトが入っているのかわかるようにして描画するとよいかもしれません。

 

(4)メソッドとしての「盤遷移」、「盤移動」、「盤表示」(初期状態と初期化)

後は「ハノイの塔」オブジェクトの描画ですが、盤(ビットマップ)、背景(含む柱)に「塔クラス」オブジェクト→「盤クラス」オブジェクトで座標を伝え、描画してゆくことになります。移動する盤を描画したいなら、PUSH、POPを上下動のメソッド、左右移動のメソッドでまとめておくと「盤クラス」オブジェクトと柱を指定するだけでスルスルと動くような気がします。

 

(5)盤の移動手順

これは↑に書いている「ハノイの塔」関数の「最下段の盤を1→2へ移動」の所がPOP→PUSHになります。

 

まぁ、このように抽象的にプログラムの全体概要を煮詰めてゆくことがまず必要なあぷろろーちになるでしょうか?

 

ps. どうでもよいことですが、昨年見ていた「エルピス」の最後に流れる"Mirage"に結構はまり、今も聞きながら書いています。(昔から気に入ったら飽きるまで繰り返して聴く性格なんです...)いろいろなバージョンがあり、一通り聞いたのですが、長澤まさみさんが参加するバージョン(↑のリンク張ってるTVドラマの最後の奴)が一番好きかな?