はじめに シリーズ一覧 初回の記事 この記事のmemoizeを使用します。 2-3 動的計画法 純粋関数型言語としては、扱いにくいところですね。 探索のメモ化と動的計画法 01 ナップサック問題 愚直 どうせ遅いので、リストの添え字アクセスもそのままにしています…

はじめに シリーズ一覧 初回の記事 前回の記事 2-2 貪欲法 硬貨の問題 硬貨の問題 貪欲は畳み込み、という感じがする。 solve cs a = snd $ foldl f (a, 0) cs' where f (r, a) (n, v) = (r - v*q, a + q) where q = min n $ div r v cs' = reverse $ zip cs…

はじめに 前回の続き。 2-1 階乗 こう書くと勝手に多倍長整数を扱っていると推論されるので、10000の階乗ぐらいなら一瞬で吐き出してくれます。 fact 0 = 1 fact n = n * fact (n-1) フィボナッチ数 単純な再帰。 fib n | n <= 1 = n | otherwise = fib (n-1…

はじめに プログラミングコンテストチャレンジブック（通称「蟻本」）を買ったので、Haskellのコードに落とすチャレンジをしようと思います。解説は基本的にしないつもりです。 目標とする計算量が達成できたらOKということにします。バージョンはGHC8.8.3で…