アルゴリズムの実装力を養成するため、Perlで書いてみましたの続編です。
こちらの本の第8章から
図解入門よくわかるアルゴリズムの基本と仕組み (How‐nual Visual Guide Book)
- 作者: 杉浦賢
- 出版社/メーカー: 秀和システム
- 発売日: 2002/02/26
- メディア: 単行本
- 購入: 1人 クリック: 36回
- この商品を含むブログ (6件) を見る
再帰(第8章)
再帰アルゴリズムとは、その関数が目的を達成するまで、自分自身を何度も呼び出す構造となっている面白い構造です。
自分自身を深く深く掘り下げて、到達点に達した途端にすべてが解決するという、ピタゴラスイッチ的な面白い仕組みでとても好きなアルゴリズムです。
が、この「どう自分自身を掘り下げる（関数を呼び出す）か」「解決の到達点は何なのか」の勘所がなかなか難しいアルゴリズムでもあります。
最大公約数を求めるコード
2つの数の最大公約数を求める方法にユークリッドの互除法という方法があるそうです。2つの数を互いに割り算していくと答えが出る方法です。
その方法の理解はまだ出来ていませんが、とりあえずその仕組みを再帰で実装してみました。
「何度も割り算をしていく」が自分自身を掘り下げる関数に、「余りが0になった時」が解決の到達点っぽいですね。
階乗を求める
1からある数まで、1ずつ増やした数を掛け算した答えをだす（1 * 2 * 3 * ... * n）問題です。
掛けていく数を１ずつ増やすより、逆にnから1ずつ減らしていって最後に1になった時を解決の到達点と考えるのがポイントです。
クイックソート
クイックソートは並べ替えのアルゴリズムの1つです。並べ替える元データから任意の1つの値を取り出し、その値より大きいグループと小さいグループの2つのグループに分け、出来たグループでまた同じ動作をしていきます。各グループの要素数はだんだん少なくなっていき、グループ分けが出来なくなるまで少なくなればそこが到達点
と考えます。
まずは自分なりに考えてたコードです。問題点は、グループ分けした要素（配列）を量産しているので、実行時のメモリを沢山使っているところです。
クイックソートその2
本の実装例では、その1の問題点を見事に解決（新しい配列を量産するのではなく、元の配列内の数値をうまいこと入れ替えることで実装）していたので、その考え方で実装してみました。
配列の値をコピーするのではなく、元の配列の値の場所を入れ替える・・・そう、リファレンスの出番ですね。
ニュートン法
微分を使って平方根の値（近似値）を求める方法です。
ニュートン法自体の理解は数学的素養が必要なので、最近通っている高校数学勉強会での知識で、なんとなく分かった様な気がしている状態ですが、理屈の実装自体は難しくありません。
台形法
ある関数（数学の）で書かれたグラフの面積を、定積分を使って求める方法です。
ニュートン法と同様、数学的素養が必要ですが、理屈の実装自体は難しくありません。
ダイクストラ法
経路探索のアルゴリズム、駅すぱあとみたいなやつですね。
自力ではさっぱり分からなかったので解説を読んで実装しました。すべての点の最短経路を求めるていき、その点がゴールなら解決するというアルゴリズムです。
色々な基本アルゴリズムを実装してみましたが、このあたり全てがヒントなしでスラスラ書けるようになれたらなぁと思います。
まだ難しいアルゴリズムはすぐに忘れてしまいそうになるので、精進あるのみです。