ハノイの塔をC言語で攻略する

はじめに

昨年の情報処理演習Ⅱの課題のグループワークのレポートでハノイの塔の解法を表示するアルゴリズムを作るものが出たのだが、ふと思い出したので、どんな感じで書いたかを思い出しながらメモしていこうと思う。今年も同じ課題が出る可能性があるので、出てて、なおかつこれを見ている数理の1年生はラッキーということで(先生に見つかると多分課題は変わる)。まあ、目的は再起呼び出しの備忘録って感じです。

ハノイの塔のルール

ハノイの塔のルールは、まず、3本の柱があり、そのうち1本にn段(n∈N、n>1)の塔があるという状況から始める。(このとき任意の2段の大きさを比較したときに下の段が上の段より大きくなるように塔を作る。)この状態から「下の段より上の段が小さい」という条件を満たし続けながら「任意の塔の一番上の段を動かす」という操作を繰り返してn段の塔を別の柱に動かしせば終了である。

解法

柱にA、B、Cと名前を付けるとA、B、Cはそれぞれ最初に塔がある、何もなし、最終的に塔を移動したい柱ということとする。また、移動できるのは一番上の段であるから、最終的には「どこの柱からどこの柱に移動する」ということのみが分かればよい。このとき、最終的には塔を違う柱に移動しなくてはいけないが、このとき最も移動しにくい段は一番下の段となる。ようするに、n段の塔をCに移動するためにn−1段の塔をBに移動しなくてはならない。
また、n−1段の塔をBに移動するためには、n−2段の塔をCに移動しなくてはならない…というようになり、交互に移動する柱が交代する。また、n−1段がBに移動し、n段目がCに移動したら、今度はAにn−2段移動してn−1段目をCに移動する…のような操作となる。以上より関数を再起呼び出しを利用してn枚の移動をする関数を実現することができる。

プログラム

上の説明をプログラムにするとこんな感じになる。

#include<stdio.h>
void Hanoi(int n,const char ∗from,const char ∗work,const char ∗dest);
void Hanoi(int n,const char ∗from,const char ∗work,const char ∗dest){
    if(n>=1){
        Hanoi(n−1,from,dest,work);
        printf("%d枚目を%sから%sへ移動\n",n,from,dest);
        Hanoi(n−1,work,from,dest);
    }
}
int main(){
    int k;
    printf("枚数を入力してください。");
    scanf("%d",&k);
    Hanoi(k,"A","B","C");
}

最小手数について

解法を見ればわかると思うが、 $a_n = a_{n-1} + 1 + a_{n-1} = 2a_{n-1} + 1$ が最小手数である。数学の美しい物語のサイトにも書いてあったはずなので、詳しくは説明するつもりはないが、

n-1段の塔を移動する
n段目を移動する
n-1段の塔をn段目を移動した柱に移動する

の動きを繰り返すので、このような数列で最小手数は表される。

おわりに

当時自分がやってた時にまともに大学の環境で、先生の求めるような形で動くようなプログラムを発見できず、再起で何をやっているのかもわからず苦労した記憶があるので、少しでも参考になる人がいれば幸いです。