可逆圧縮アルゴリズムのひとつであるランレングス圧縮を実装してみます。
ランレングス圧縮は連続するデータをその一つのデータとそのデータが連続している長さの組に変換します。
この圧縮は同じ値が連続するデータをく含んでいる場合には変換後のデータのサイズを小さくできますが、バラバラな値を多く含んでいる場合には逆に大きくなってしまいます。実際にこのアルゴリズムが使われる場合には、連続しないデータを含んでいてもそれほど圧縮率が下がらないような工夫がされます。 (さらに…)
2010年8月3日 | カテゴリー：アルゴリズム
ユークリッドの互助法という名前のアルゴリズムを紹介します。これは最大公約数を求めるアルゴリズムで、
ある整数x,yの最大公約数gcd(x,y)の解を求めるとして、yが0であればx、そうでなければgcd(y, x % y)が解となる。
という至って単純なアルゴリズムです。
以下のコードはこのアルゴリズムを再帰で実装したものです。ループで実装したコードはコメントアウトされています。(再帰のほうが断然エレガントである) (さらに…)
2010年7月20日 | カテゴリー：アルゴリズム
プログラマなら誰もが知っている再帰ですが、よくC言語のポインタと並んで初心者がよくつまづく概念としても有名(?）です。今回はこの再帰(特に末尾再帰について)と基本的な制御構造の一つであるループとの関係について考えてみます。
ループ構文というのは大抵の言語に存在する制御構造ですが、世の中にはループ構文が存在しない言語もたくさんあります(gotoでジャンプしてるわけではありませんよ)。このような言語ではループの代わりに再帰呼び出しを使います。 (さらに…)
2010年7月6日 | カテゴリー：アルゴリズム
