nigoblogスマートフォン用の表示で見るnigoblog技術系会社のCEOブログ~私的編~この広告は、90日以上更新していないブログに表示しています。rubyアルゴリズム第二弾ということで今回はハノイの塔を再帰アルゴリズムで解く説明をしていきます。結果という流れで説明します。ハノイの塔とは?次の図のようなものがあったとします。簡単に説明すると3つの棒があって、円盤が上から小さい順に重ねられている。これを次の条件のもと別の棒に全て移動させることができれば終了。一回の移動に一枚しか移動できない。小さい円盤の上に大きい円盤をのせてはいけない。これだけ!このルールで上記の図を次のようにすると終了。ここで3枚円盤が合った場合、何回で移動できるかを少し考えてみて下さい。四枚のときは15回となります。いうわけで何やら数列っぽくなっているのがわかります。回の時も考えてみます。回の時の回数を出すための式は上記の式で表すことができます。これって本当にそうなのかという感じもなくはないですよね。帰納法かなんかで証明するのもかったるいですし...ここで少し考えなおしてもっと簡単に移動回数を出す方法を考えてみましょう。再帰アルゴリズムでハノイの塔を解く一度整理するために、移動方法をもう一度考えてみましょう。移動する円盤は上から順に1,2,3,4,...,nという添字をつけます。ここであることに気がつくはずです。最初に動かした二枚分を目的のところに移動。move(1)として、move(n)はn枚の円盤を移動コストとします。先ほどのn乗を使うものよりもはるかに簡単です。このようにある関数Aの値を出すためにその関数Aを使うようなアルゴリズムを再帰アルゴリズムといいます。move(5)結果はこんな感じ1371531解説は短いので不要ですね。move(n-1)を返しています。いうわけで再帰アルゴリズムを使うといとも簡単に実装が出来るというものでした。ハノイの塔は例外ですが、大抵の場合繰り返しを使ったほうがマシンに負荷をかけないケースが多いようです。フィボナッチや階乗なんかがその例。ハノイの塔の一般項にべき乗というマシンに負荷がかかる演算が入っているから再帰を用いてなるべく加算だけで行った方がよいということです。同じようになるべく掛け算の回数を減らして計算量を小さくするアルゴリズムに高速フーリエ変換などがあります。これはいつか紹介したいですね。23:46プログラマーは今こそアルゴリズムを書くべき!!2~再帰アルゴリズムでハノイの塔を解く~Tweet広告を非表示にする関連記事2013-03-14モンティ・ホール問題のシミュレーションをしてみるモンティ・ホール問題という有名な確率の問題があります。山南敬介にみる”組織力”について~歴史から学ぶシリーズ~2017年は「WEBブランディング広告」元年になる。plusGoogleはてなブログをはじめよう!nigohirokiさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。