私はソースコードをなるべく短くする、いわゆる「CodeGolf」は好きではありません。ソースコードを短縮することにこだわるあまり、可読性の低いコードになっているケースをたまに見かけるからです。しかし CodeGolf にも利点はあります。今まで同じアルゴリ…

えー、ある方からコメントをいただきましたので、ここで釈明(?)しておきます。まぁ、プログラミングをかじったことのある人ならだれでも知ってるアルゴリズムを例に、Haskell で書き下したらどうなるかざっとご紹介したわけですが、私は「これが効率のいいア…

fibs :: [Integer] fibs = 0 : 1 : [x + y | (x, y) <- zip fibs (tail fibs)] Fibonacci 数列は急速に値が大きくなるので Int より精度の高い Integer 型を使ってます。もうあまりの嬉しさに泣きたくなってきた。

qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x : xs) = qsort smaller ++ [x] ++ qsort larger where smaller = [a | a <- xs, a <= x] larger = [a | a <- xs, a > x] マジ Haskell 凄いんですけど。ちなみに qsort 関数の最初の宣言は順序クラスに…

primes :: [Int] primes = sieve [2..] sieve :: [Int] -> [Int] sieve (p : xs) = p : sieve [x | x <- xs, x `mod` p /= 0] 目から鱗でござった。

Twitter でとある方が「+ 演算子を使わずに a と b の和を求める方法を…」といったことをつぶやいていたので、ちょっと作ってみた。 #include <stdio.h> int add(int, int); int main() { printf("%d\n", add(2, 3)); printf("%d\n", add(2, - 3)); return 0; } int a</stdio.h>…

一通り道具は揃ったはずなので、とりあえずプログラムっぽく整えてみる。

k-CNF の充足可能な(つまり、全ての clause が真になるような真偽値の)割り当てを求める問題は k-SAT(Satisfiability Problem)と呼ばれる。同書にならって 3-SAT を考える。問題としては、これまた同書でユーリが「僕」に示した問題で行ってみよう。まず変数…

続き。同書では(変数)ないし¬(変数)を "literal"(リテラル) と呼び、literal のいくつかの論理和を "clause"(クローズ)と呼んでいる。clause のいくつかの論理積を CNF(Conjunctive Normal Form)と呼ぶ。全ての clause が k 個の literal からなるような CNF…

結城浩先生 (id:hyuki) の「数学ガール／乱択アルゴリズム」を読んでいて、これを実際にプログラミングするとしたらどうなるんだろうと考えてちょっとやってみることにした。まず、ランダムに真偽値を返す、次のようなメソッドを考えた。 static boolean ran…