読者です 読者をやめる 読者になる 読者になる

親子丼の備忘録(改)

親子丼の日常を綴った何か。専門的なことも書くかも?

ハノイの塔、ですけど。

おやこどぅぉーーん。
どうも、親子丼です。

2016/1/7 (Thu.)

昨日は、本当に適当な文章ですみませんm( )m
本当に眠かったんです、許してください、何でもしますから!
(↑今何でもt)

では、今日の話。
今日は、本当に1,2時間目の数学以外は時間が勝手に流れて行きました。
数学は、集中して聞いているのですが、その後文系教科が続いて眠気MAXでしたw
でも、タリーズコーヒーの力で乗り越え、部活をしてきました。
今日の部活では、昨日の創造工学でやった「ハノイの塔」という有名な問題を
授業では人間がコンピュータに倣ってアルゴリズムにしたがって解きましたが、
僕はその後、プログラムに解かせてみました。

インドのガンジス河の畔のヴァラナシ(ベナレス)に、世界の中心を表すという
巨大な寺院がある。そこには青銅の板の上に、長さ1キュビット、太さが蜂の体ほどの3本の
ダイヤモンドの針が立てられている。そのうちの1本には、天地創造のときに神が64枚の純金の
円盤を大きい円盤から順に重ねて置いた。これが「ブラフマーの塔」である。
司祭たちはそこで、昼夜を通して円盤を別の柱に移し替えている。
そして、全ての円盤の移し替えが終わったときに、世界は崩壊し終焉を迎える。 (ハノイの塔 - Wikipedia)

ハノイの塔とは、フランスの数学者リュカが作った問題で、↑の伝説があるとされています。
円盤の動かし方にはルールがあり、
1. 3本の杭と大きさの異なる複数の穴の空いた円盤から構成されている。
2. 最初は全ての円盤が左の杭に小さいものが上になるように順に重ねられている。
3. 円盤を一回一枚ずつどれかの杭に移動させられるが、小さな円盤の上に大きな円盤を
 のせることはできない。

これを最短で解くには、再帰の考え方を使うと簡単です。
N枚の円盤を右の杭に移動させたいなら、まず、左の杭から真ん中の杭に
N-1枚の円盤を移動させ、一番下の円盤を右の杭に移動させて、真ん中の円盤から
N-1枚の円盤を左に移動させる、という手順でこれを解くことができます。
この時、
N-1枚を移動させる→一枚移動→N-1枚移動させる
(N-1)-1枚移動させる→一枚移動→(N-1)-1枚移動させる


と、何回も入れ子のようにしていくと、最後は1枚移動させるところまで行きます。
1枚の円盤を移動させるのは、単純明快です。
なので、このように再帰的にやっていけば、最短で正確に解くことができますね。
(まあ、なんか説得力にかけるので詳細は↑のWikipediaを見てください。)

で、肝心のソースコードですが、GitHubに上げました。

ハノイの塔を解きます。 / C#

[追記]ちょっとだけ(移動回数カウントの部分)修正しました。

まあ、安定のC#コンソールアプリです。
円盤の枚数を入力すると、どのように円盤を移動させたのか、と移動回数が表示されます。
あとちなみに移動回数は計算で求められて、2n-1(nは円盤の枚数)で求められます。
なので最後にその値を確認用に入れています。

さて、まあ再帰ってとっても簡単にかけるけど、理論は複雑なのね、ってことが、
わかりました。
階乗も再帰で求められるので、今度打ってみたいと思います。
では、今日は「ハノイの塔」のお話でした、今日はこの辺で。
それでは、また。
親子丼でした。

※今日の一言「なんか今までの俺の記事読んでも得られるのは、俺のどうでも良い日常
だけだなって思って、なんかちょっと役に立つようなことを書いてみました。」

広告を非表示にする