フィボナッチ数列とtrace
天下一プログラマーコンテスト2012決勝のA問題ぶんたんは解き方が全く分かりませんでしたが、解答を見てみるとどうも貪欲に大きいフィボナッチ数を引いていけば良いみたいです。
なんで？と思っていたら証明している方がいました。なるほどなあ。
理屈さえ分かれば解き方自体はそんなに難しくなさそうです。
しかし、Haskellでフィボナッチ数列をどう書けばいいのか？
有名でスタイリッシュなコードはこう書くようです。
fib = 1 : 1 : zipWith (+) fib (tail fib)
zipWith A B C はB, CのリストをAを適用して新しいリストを作る関数で、
tail A はAの2番目以降のリストを作る関数です。
フィボナッチ数列の特徴を活かした簡潔な関数です。
ただ、個人的にはこちらで紹介されていた以下のコードが分かりやすくて好みです。
fib a b = a : fib b (a+b)
fib 0 1 = [0, (fib 1 1)] = [0, 1, (fib 1 2)] = [0, 1, 1, (fib 2 3)] = [0, 1, 1, 2, (fib 3 5)],...
となってフィボナッチ数列が形成されます。直観的に分かりやすい。
早速ぶんたんを解くコードを書きますが、なぜか上手く動かず。
printでデバッグしたいなーと思うも上手く動きません。
Haskellは型の制限がかなり厳しいので、プログラム内に気軽にprintを埋め込むとコンパイルが通らなくなります。
そこで、Debug.Traceモジュールのtrave関数を使います。
trace A Bで、Aの文字列を出力し、trace関数の評価した値をBにすることができます。
例えば、
sq n = n * n
の引数nの値が知りたいとします。
sq n = do print n n * n
とすると、コンパイルが通らなくなります。
traceを使うと、
sq n = trace ("n = " ++ show n) (n * n)
と書けます。
sq 21を呼ぶと、「n = 21」と出力されます。便利。
