FC2ブログ

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

アルゴリズム勉強記⑮~再帰編2 ハノイの塔編~

はい、再帰の第二回目です。

出ました。ハノイの塔。いい感じにトラウマです。
多分最初に挑んだのが1年前くらいで、散々考えた挙句イミフwwwで終わった記憶があります。

あれから1年、再び私の前に立ちはだかると言うのか! タワー・オブ・ハノイ!(スタンド名っぽいww)

ハノイの塔のルールはWikipediaに載ってます。有名なパズルらしいですが、私ははじめ知りませんでした。

ずばりハノイの塔の解法は、

3本の棒をそれぞれ始点、終点、作業用とする。
始点に存在する円盤のうち、一番下以外の円盤を△とする。
△を作業用へ移し、一番下の円盤を始点から終点へ移し、△を作業用から終点へ移す。


シンプルェ……
要するに、ある時点での円盤の移動を、△と一番下の円盤に分けるというのがミソです。
具体例として円盤が4枚のときを考えてみます。


棒a,b,cがあり、aにある4枚の円盤をbへ移動させます。
円盤は上から1,2,3,4とします。

(深さ0)
始点=a,終点=b,作業用=c
(1,2,3,4)を、4と(1,2,3)に分ける。
(1,2,3)を始点aから作業用cへ移動させるために、再帰呼び出し

(深さ1)
始点=a,終点=c,作業用=b
(1,2,3)を、3と(1,2)に分ける。
(1,2)を始点aから作業用bへ移動させるために、再帰呼び出し

(深さ2)
始点=a,終点=b,作業用=c
(1,2)を2と(1)に分ける。
(1)を始点aから作業用cに移動させるために、再帰呼び出し

(深さ3)
始点=a,終点=c,作業用=b
(1)はこれ以上分けられないので、(1)を始点aから終点cに移動させる。

(深さ2)
始点=a,終点=b,作業用=c
2を始点aから終点bへ移動させる。
1を作業用cから終点bへ移動させる。

(深さ1)
始点=a,終点=c,作業用=b
3を始点aから終点cへ移動させる。
(1,2)を作業用bから終点cへ移動させるために再帰呼び出し(省略)。

(深さ0)
始点=a,終点=b,作業用=c
4を始点aから終点cへ移動させる。
(1,2,3)を作業用cから終点bへ移動させるために再帰呼び出し(省略)。




これをプログラムに起こすと、

再帰関数hanoi
①円盤を分割し、△を始点から作業用へ移動(再帰呼び出し)
②残った一番下の円盤を始点から終点へ移動
③作業用の△を終点へ移動(再帰呼び出し)

hanoi自体が円盤を移動させる機能を持ち、移動させるために自身の機能を使う。
再帰ェ……こりゃややこしいわ。本にかじりつきながらなら理解できるけど、ゼロからこれを考えつくなんて多分一生ありえないと思います。

とにかく、これで積年の恨み(?)は果たした! ……はず。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメント

Secret

再帰関数なんてまともに経験してないからどこで使えるのかわかりませんw
理解していてよく使う技法は線形リストくらいです^^;
勉強しなおそうかな(汗
それともここで学べばいいんだ←

リンクありがとうございます~(^-^
先に言い出したのに貼るの遅れて申し訳ないです('';
プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。