[B! アルゴリズム] yosukenのブックマーク

yosuken id:yosuken

アルゴリズムに関するyosukenのブックマーク (2)

竹内関数 - Wikipedia
再帰的に定義される、3個の引数 x, y, z をとる次のような関数である。特に変わる所は無いがLisp版[1]も参照のこと。定義からわかるように処理を次々にたらい回しにしていくことから、たらいまわし関数[2]、たらい関数 (Tarai function) とも呼ばれる（後述のマッカーシー版との混同を避けるためこの名で呼ばれることのほうが多いが、こちらの定義のほうがオリジナルである。マッカーシー版を特にTak関数として区別する場合もある）。電電公社研究員（当時）の竹内郁雄が、1974年の夏前の頃、後述するような特性のある関数をあれこれ考えていた、ある日の午前に思いついたものである[3]。竹内関数と命名したのは野崎昭弘である[4]。特性として、他のよくベンチマークに使われる関数と比較して、たとえばフィボナッチ数を何の工夫もなく計算するいわゆるダム（dumb）フィボナッチと比較して、計算量
yosuken 2009/11/09
プログラミング

アルゴリズム
リンク
404 Blog Not Found:アルゴリズム百選 - ハッシュを再発明する
2007年12月03日11:15 カテゴリアルゴリズム百選アルゴリズム百選 - ハッシュを再発明する (実はハッシュを使って)配列を再発明したところで、今度は配列を使ってハッシュを再発明してみます。現代におけるプログラミングでは、連想配列(associative array)というものを非常によく使います。通常の配列では、データを取り出すのに整数の番号を使いますが、連想配列ではその代わりに文字列を使います。これは非常に便利で、多くの言語ではオブジェクトの実装にこの連想配列を用いています。JavaScriptのオブジェクトも実は連想配列です。しかし、これを実装するには、少し工夫が必要です。単なる配列であれば、ただ等間隔に並べておけば、「何番目を出してくれ」で事足りますが、連想配列で「'dankogai'番目」といっても人間にもコンピューターにもなんのことかさっぱりわかりません。誰でも
yosuken 2009/10/02
プログラミング

アルゴリズム
リンク
1