MonBloG

私が働いている職場には、「ハノイの塔（円盤の枚数は5枚）」という展示があります。

円盤を動かして遊んでいる姿は何度も見ていましたが、「プログラムでどう実装するんだろう？」と考えたことはありませんでした。

コンピュータサイエンスを学び始めてから、ハノイの塔は再帰の代表例としてよく登場します。
そこで今回は、実際の展示を思い浮かべながら、ハノイの塔をプログラムで実装しつつ、自分なりに理解を整理してみました。

実際に展示を自分で動かしながら考えてみると、

「一番大きい円盤を移動させるにはどうすればいいんだろう？」
「最後に元の形へ戻すにはどういう順番になるんだろう？」

ということばかり考えていました。

最初は5枚のまま挑戦してみましたが、途中で頭の中が完全にこんがらがってしまいました（笑）。そこで、「まずは一番簡単な状態から考えてみよう」と思い、円盤の枚数を減らして考えることにしました。

STEP1：まずは1枚で考える

1枚だけなら、考えることはありません。
AからCへそのまま移動させれば終わりです。

ここで気付いたのは、「1枚なら誰でもできる」ということでした。プログラムでも、実はこの状態が一番重要です。

再帰では、この「これ以上分けられない状態」が処理の終了条件になります。

STEP2：2枚で考える

次に2枚で考えてみました。

ここで初めて、「大きい円盤はすぐには動かせない」ということに気付きます。

まずは小さい円盤を別の棒へ移動します。
そのあとで大きい円盤を目的の場所へ移動し、最後に小さい円盤を上へ戻します。

文章にすると当たり前のようですが、この手順を実際に展示でやってみると、とても分かりやすかったです。

STEP3：3枚で考える

ここでようやく、「なるほど！」と思えました。
3枚の場合も、結局やっていることは同じです。

一番大きい円盤を動かしたい。でも、その上には2枚あります。
つまり、先ほど考えた「2枚を移動する方法」をそのまま使えばいいだけでした。

「3枚だから新しい解き方を考える」のではなく、「2枚の解き方を利用する」。さらに2枚を動かすには、1枚の解き方を利用する。
この考え方が、再帰そのものなんだと理解できました。

最初はコードを読んでも全然イメージできませんでしたが、実際に展示を動かしてからコードを見ると、「あ、この処理は円盤をどかしているだけなんだ」と自然に理解できるようになりました。

次は、この考え方をそのままTypeScriptで実装していきます。

/*
ハノイの塔の条件
・1枚の場合
・2枚以上の場合
・小さい円盤の上には、大きい円盤は置けない
*/
// step1: 関数を作る
/*
@param 円盤n
@param 出発地
@param 目的地
@param 経由地
*/
function hanoi(
    n:number,
    from:string,
    to:string,
    via:string
):void{}

/*
ハノイの塔の条件
・1枚の場合
・2枚以上の場合
・小さい円盤の上には、大きい円盤は置けない
*/
// step1: 関数を作る
/*
@param 円盤n
@param 出発地
@param 目的地
@param 経由地
*/
function hanoi(
    n:number,
    from:string,
    to:string,
    via:string
):void{
    // step2: 1枚の条件を作る
    if(n === 1){
      console.log(`${from}->${to}`);
      return;
    }
}

/*
ハノイの塔の条件
・1枚の場合
・2枚以上の場合
・小さい円盤の上には、大きい円盤は置けない
*/
// step1: 関数を作る
/*
@param 円盤n
@param 出発地
@param 目的地
@param 経由地
*/
function hanoi(
    n:number,
    from:string,
    to:string,
    via:string
):void{
    // step2: 1枚の条件を作る
    if(n === 1){
      console.log(`${from}->${to}`);
      return;
    }
    // step3: 2枚以上の条件を考える
    // 2枚以上の場合は、上に乗ってる奴は？->中継地点へ！
    hanoi(n-1,from,via,to);
    // 1番大きいのはどこへ動かす？->最終目的地！！
    console.log(`${from}->${to}`);
    
    // 最後、中継地点にいた奴は？->最終目的地へ！！！
    hanoi(n-1,via,to,from);
}

最後に

今回、ハノイの塔を実装してみて感じたのは、「コードから理解しようとすると難しいものでも、実際の動きを理解してからコードを見ると意外とシンプルに見える」ということでした。

普段、職場にある展示ですが、自分がプログラムとして考えてみると、また違った面白さがありました。

今回の経験を通して、アルゴリズムはコードを覚えるものではなく、「なぜその手順になるのか」を考えることが大切なんだと改めて感じました。

これからも展示をきっかけに、コンピュータサイエンスの視点で考えたり、実際にプログラムを書いてみたりしながら、自分なりの学びをMonBloGに残していきたいと思います。

ちなみに、動画の解説も作ってみたので、見たい方はこちらへ！！

ハノイの塔を、エンジニア目線で理解してみた

STEP1：まずは1枚で考える

STEP2：2枚で考える

STEP3：3枚で考える

最後に