Project Eulerで用いた数学知識
オイラーにちなんだ数学的なプログラミングの問題が出題されるサイト、Project Euler。 大体の問題は、greedy にやっても解けるんですが、適切な数学的知識を用いると時間計算量のオーダーが劇的に変わってきます。 そこで、100問目まではラップトップで1秒以内(もちろんScalaです)に解くという縛りを設けてやっていました。 (ただし、幾つかの問題ではこの縛りに違反したまま。 Problem 60: 9,472ms, Problem 78: 2,948ms, Problem 86: 2,125ms, Problem 93: 2,244ms, Problem 95: 3,854ms, Problem 96: 1,184ms)
その際に使った知識(Wikipediaへのリンク)をここにまとめていきます。 このリストは(これまでに解いた Project Euler の問題に関してさえも)まだ完全ではないんですが、暇を見つけて少しずつ更新していきます。
約数
素因数分解
素数
置換
分割数
フィボナッチ数列
ピタゴラス数
平方数
順序集合
数列
方程式
分数
少数
数値解析
グラフ探索
これまでに解いた問題は以下のとおり。