C++によるハノイの塔の解法

C++によるハノイの塔の解法についての話です。
きっかけは、別問題（8王妃問題とか）だったのだけれど、パズルつながりで「ハノイの塔」を見かけたから、とりあえずC++で実装してみました。

まずは「ハノイの塔」について、Wikipediaによれば...
>ハノイの塔（ハノイのとう、Tower of Hanoi）は、パズルの一種。
>バラモンの塔または ルーカスタワー(Lucas' Tower)とも呼ばれる。
>ハノイの塔は、フランスの数学者エドゥアール・リュカが1883年に発売したゲーム『ハノイの塔』がルーツである。
>日本では1907年（明治40年）に書かれた書物『世界遊戯法大全』で紹介されている。
ja.wikipedia.org
「懐かしいわー」って、小さかった頃に遊んだ記憶があります。
まぁ、今も10歳だから、大きくはないのかもしれないけれど、子供だった時の話です。
いや、今も子供かっ！

次に、パズルのルールについて...
>以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
・3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
・最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
・円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。
数学的に言えば、「n枚の円盤すべてを移動させるには、最低 2 ^ n − 1 回の手数がかかる」ことになります。
>棒が4本以上の場合の最小手数は三角数を用いて計算できることが知られている。

>解は、次のように再帰的に考えることができる。
>塔を「一番下にある円盤」と「残りの円盤群」というように分けてみる。
>そして、まず「残りの円盤群」を移動させ、次に「一番下にある円盤」を移動し、その上にまた「残りの円盤群」を動かせばよい。
ってことで、実装！

このプログラムは、3本の軸の「ハノイの塔」の解法を示します。
円盤の枚数を入力することで、クリアするための手順が出力されます。

だから、コードとして書けば、こんな感じになります。

・C++によるハノイの塔の解法

/*
Tower of Hanoi Program in C++
C++によるハノイの塔の解法
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
void f(int n,int x,int y){
    if(n>1){
        f(n-1,x,6-x-y);
    }
    cout<<n<<"番を、"<<x<<"軸から"<<y<<"軸へ移動する。"<<endl;
    if(n>1){
        f(n-1,6-x-y,y);
    }
}
int main(void){
    int n;
    cin>>n;
    if(1<n && n<=11){
        cout<<"ハノイの塔(軸は3本)"<<endl;
        cout<<"----------------------------"<<endl;
        cout<<"円盤が"<<n<<"枚のとき"<<endl;
        cout<<"円盤の番号を小さい方から順に";
        for(int i=1;i<=n;i++){
            cout<<i<<"番"<<((i==n) ? "とし、\n" : ",");
        }
        cout<<"軸を左から1軸,2軸,3軸とします。"<<endl;
        cout<<"このとき、ハノイの塔をクリアするには、";
        cout<<"以下の手順を実行してください。"<<endl;
        f(n,1,3);
        return 0;
    }else{
        cout<<"2以上11以下の整数を入力値として、";
        cout<<"再度実行してください。"<<endl;
        return 0;
    }
}

ただし支配数がメルセンヌ数なので、nが大きくなると結果も膨大となるから、あらかじめ2以上11以下の整数を入力値とします。

動作の確認については、とりあえずオンライン実行環境のpaiza.IOに通してみてから...

Macのターミナルでも実行しておきました。

はい、大丈夫みたいです。

あと、GitHubにもアップロードしておきました。
github.com

全然関係ないけれど、ふと手を見たら、マメができてました。
たぶん学校で使ってる絵の具のパレットをガシガシ洗ったせいだと思います、ちゃんとキレイになったけれど。