オイラーにちなんだ数学的なプログラミングの問題が出題されるサイト、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 の問題に関してさえも)まだ完全ではないんですが、暇を見つけて少しずつ更新していきます。

約数

  • 約数
  • 最大公約数
  • ユークリッド互除法
  • 約数の数
  • 高度合成数

素因数分解

  • 試し割り法
  • MPQS, Multiple Polynomial Quadratic Sieve

素数

  • 素数
  • 素数定理
  • エラトステネスの篩
  • ミラー-ラビン素数判定法
  • 擬似素数
  • 強い擬似素数

置換

  • 置換に関するトピックリスト

分割数

  • 分割数
  • 分割関数
  • オイラーのトーシェント関数

フィボナッチ数列

  • フィボナッチ数
  • フィボナッチ数の一般項

ピタゴラス数

  • ピタゴラス数
  • ピタゴラス数の生成法
  • 原始ピタゴラス数の木

平方数

  • 平方数
  • 四角錐数(平方数の和)

順序集合

数列

  • ファレイ数列

方程式

  • Pell方程式

分数

  • 加比の理
  • 連分数
  • 連分数に関する定理

少数

  • 循環小数

数値解析

  • ラグランジュ多項式
  • 連分数展開 (平方根の計算)

グラフ探索

  • クラスカル法
  • ダイクストラ法
  • ハンガリー法 (Kuhn–Munkres アルゴリズム)
  • 最大フロー問題
  • Push–relabel法

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

f:id:yuimat:20151202152117p:plain