id:practicalschemeさんの珠玉のエントリ、なんでも継続は以下のような一説から始まります。 プログラミングの世界の概念には、禅の公案のようなものがある。 それを説明する文章はほんの一文なのに、最初に目にする時、 その文は全く意味をなさない、暗号の…
テキストデータを加工するとき、sedは欠くことの出来ないツールです。しかし、sedが改行を読み込まないことはあまり知られていません。例えば、入力に含まれる改行を全て削除するために以下のようなスクリプトを記述したとしましょう。 $ sed -n -e 's/\n//g…
数値計算のプログラムを行うとき、端数処理に関して繰り返し調べていることに気が付きました。負の数の扱いや絶対値を伴った計算は意外に複雑で、気が付くとWikipediaのRoundingやFloor and ceiling functionsを何度も訪れていたり...そこで備忘録として、切…
前回のエントリでは、3003 -- Spiderman’s workoutの解法としてメモ化再帰を解説しました。今回のエントリではこれを元に、動的計画法を解説します。 まず、前回のエントリにて実装したsearch関数を見てみましょう。 #define INT_INF 999999 int memo[40+1][…
昨年のSIGGRAPH参加後、9月ほどからでしょうか。アルゴリズムに関する知識と実装する力を基礎から鍛え直す衝動にかられ、北京大学のJudge Online(以下POJ)に参加するようになりました。現在のAC数は123問とまだ少ないですが、一つ一つの問題を解くごとに発見…
TrueだったらFalseで、FalseだったらTrueにしたい。なんかそんなことそこかしこで必要で、その為の便利なものがあるのかなぁと思ったんだけど無いぽい。 0と1を次々返す方法 - When it’s ready. Yieldpython実装は自然だが、next()がわずらわしい。 404 Blog…
数値計算の実装を行っていると、ある特定の数値を除外した数列を生成したくなることがあります。行列の特定の行や列を除いた要素を処理する際、例えば枢軸演算を行う場合がこれにあたります。Pythonで簡単に実装すると以下となります。 for i in range(N): i…
PostScriptにはSymbolというフォントが用意されています。ギリシャ文字を用いるにはこのフォントを使用します。例えば、πを出力するには以下のようにします。 /Symbol findfont 10 scalefont setfont 0 0 moveto (p) show文字は8進数数値としても与えられる…
多忙だったこともあり、久しぶりのエントリとなってしまいました。さて、Gmailのメッセージ検索にはダッシュ(-)、OR演算子および括弧が用意されています。これらの演算子は大変便利で、強い依存性があるように思います。それぞれの演算子の用法は大変簡潔で…
まとまった時間があったので、共分散行列(Covariance Matrix)を用いた主成分分析(Principal Component Analysis)にて生成した有向バウンディングボックスのデモをGoogle Gadgetsを用いて書いてみました(有向バウンディングボックスについては、過去のエント…
先日のエントリにてMac OS X 10.6に数式処理システムのMaximaをインストールする方法を記載しました。今回のエントリでは、Cocoa EmacsとteTeXにて構築している環境にimaximaをインストールする方法を記載します。 imaximaは本田康晃さんががメンテナンスさ…
Mac OS X 10.6にMaximaをインストールしました。Maximaは数式処理システムです。数値計算ではなく、数式のまま計算を行なう非常に強力なシステムです。例えば、2数の和の3乗を考えてみましょう。以下の等式の右辺は左辺の括弧を展開したものであり、また左辺…
先日のエントリにて、幅優先探索を用いたダイクストラのアルゴリズムを考察しました。今回は、幅優先探索が如何にキューを用いるかをまとめてみました。名著アルゴリズムCでは、幅優先探索はレベル順(level-order)の走査として、第1巻第4章、木の章にてごく…
先日話題になっていた最短経路探索問題を考察するにあたり、探索回数を如何に減らすかを主眼において考えてみました。それに伴い、いくつかの可視を行いました。 ダイクストラのアルゴリズムを伴った幅優先探索において、すでに訪れた節点を再度訪れる場合と…
面白い問題があったので解いてみました。問題の詳細は、出題者さんのエントリでご確認ください。 さて試験問題です。内容は、壁とスペースで構成された迷路が与えられたとき、スタート地点からゴール地点に至る最短経路を求めよ、というものです。 人生を書…
算術式を記述するにはいくつかの方法があります。算数、数学に使われる中値記法はその一つです。中値記法は、英語ではInfix Notationと表記されます。計算機で使用される言語では、数学のように大括弧(bracket)、中括弧(brace)、括弧(parenthesis)を使い分け…
先日のエントリにて、一貫した二分検索木の可視を行うアルゴリズムについて記載しました。また、木構造、特に二分木や二分検索木と親和性が高い、通りがけ順について説明しました。以下は、通りがけ順にてkd木を走査する様子を可視したものです。さて、木の…
名著アルゴリズム Cの特筆すべき点の一つとして、可視の美しさが挙げられます。特に二分木の可視は美しく、計算されつくされた様にいつも唸らされます。以下は、アルゴリズム C 第2巻の14章、初等的な検索法の章に掲載されている二分木の可視です。この木は9…
