【C#】ハノイの塔をC#で書いた

C#

 

 

最近学んだハノイの塔のアルゴリズムをC#で書いたので紹介。

 

ハノイの塔

 

ハノイの塔は3つの棒と大きさの違う円盤を使った有名ななぞかけです。簡単に言うと、3つの棒と3つの円盤があるとすると、今1つの棒に円盤がピラミッド状に刺さっているとして、それをまとめて別の棒に移動させるにはどう移動させればいいか。

 

このハノイの塔にはルールがあります。

  • 棒は3つ
  • 最初は3つの棒のうちの1つの棒にすべての円盤がピラミッド状に刺さっている
  • 一度に移動できる円盤は1つだけ(まとめて移動はできない)
  • ある円盤の上に、その円盤よりも大きい円盤は乗せることは出来ない

これを満たしながら解かなければいけません。

試しに円盤が3つのときを解いてみると、7回ぐらいで3つの円盤を移動させることが出来ます。

 

下は実際のプラグラムで、「A、B、Cの3つの棒があるとして任意の数の円盤をAからBに移動させるる」処理し、その過程で一番小さい円盤を1段目、一番大きいの円盤をn段目として、どの円盤をどの棒に移動させるかの表示を行います。

 

 

このプログラムの肝は、「n段のピラミッドを別の塔に移動させる」ことを抽象的にとらえてそれをメソッドとして表すことです。

 

今回でいえば、A棒にいるn段分の円盤ピラミッドをB棒に移動させるには、n段目の円盤の上にあるn-1段分の円盤ピラミッドをC棒に移動させて、その後にn段目の円盤をB棒に移動、最後にn-1段分の円盤ピラミッドをC棒からB棒へ移動させる。

 

これがメソッドとして表すことができれば、後は再帰処理を行うことによって順次求めてくれます。

 

一見、一度に動かせる円盤の数は1つまでというハノイの塔のルールを無視しているので違和感があるかもしれません。しかし、n-1段分の円盤ピラミッドを1つの円盤とみなすことで、実質的に2段の円盤ピラミッドを見ているのと同じになり、問題をより抽象的に見ることが出来ます。

 

今回は上の通り、n段のハノイの塔を棒AからBへ移動させるメソッドを作り、それをn-1、n-2と2段のハノイの塔を解くにたどり着くまで再帰します。

 

再帰処理は、こういう問題の抽象的な表現を順次再帰させることで実際に解決まで持っていけるので便利ですね。(低速でバグの原因になるのであまりよく思われないみたいですが)

 

 

コメント