Scala日記

Scalaの備忘録。ときどき研究の話。

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 の問題に関してさえも)まだ完全ではないんですが、暇を見つけて少しずつ更新していきます。

約数

素因数分解

素数

置換

分割数

フィボナッチ数列

ピタゴラス

平方数

順序集合

数列

方程式

分数

少数

数値解析

グラフ探索


これまでに解いた問題は以下のとおり。

f:id:yuimat:20151202152117p:plain