T_NAKAの阿房ブログ

アクセスカウンタ

zoom RSS Python のおさらい(18)再帰的プログラムの例

<<   作成日時 : 2015/10/16 00:01   >>

ブログ気持玉 0 / トラックバック 0 / コメント 0

slide07 という資料は、再帰的プログラムの活かし方を説明ような気がします。

まず、べき乗を求める簡単な関数を三つ並べてみました。
exp1(3,4)、exp2(3,4)、exp3(3,4) は全て、34 = 81 を吐き出します。

画像

exp1 (a,b) は、べき乗を求める素直な論理ですね。a を b 回掛けています。
exp2 (a,b) は、再帰的プログラムになっています。b = 1 の場合は再帰を停止する必要があるので、これを if 文を使って検出しています。
exp3 (a,b) も、再帰的プログラムですが、(b%2)*2==b で b が偶数か?奇数か?をチェックしています。奇数の場合は exp2 (a,b) と同様の再帰ループになるのですが、偶数なら、2乗して、なおかつ b を半分にして再帰ループに渡します。こうすることによって、b を減らす速度を速めることが出来、ひいては計算を早く終わらせることが出来ると考えます。まあ、大きな数だと処理速度が増えてしまうので、こういう工夫は必要だと思います。

次の例がいわゆるハノイの塔というゲームを解く再帰的プログラムです。
こんな簡単な論理で解決出来てしまうのですね。
この実施例では、円盤3枚の簡単な場合を示しています。ネットで見つけた解の図を載せていますが、出力結果と比べて、全く一致していることが分かると思います。

画像


なおハノイの塔については、wikipediaここを参照して下さい。

今日はこの辺で。。

テーマ

関連テーマ 一覧


月別リンク

ブログ気持玉

クリックして気持ちを伝えよう!
ログインしてクリックすれば、自分のブログへのリンクが付きます。
→ログインへ

トラックバック(0件)

タイトル (本文) ブログ名/日時

トラックバック用URL help


自分のブログにトラックバック記事作成(会員用) help

タイトル
本 文

コメント(0件)

内 容 ニックネーム/日時

コメントする help

ニックネーム
本 文
Python のおさらい(18)再帰的プログラムの例 T_NAKAの阿房ブログ/BIGLOBEウェブリブログ
文字サイズ:       閉じる