プロジェクト・オイラー

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索
Project Euler
Euler
URL projecteuler.net
営利性 非営利
タイプ 問題解決ウェブサイト
登録 無料
設立日 2001年10月5日
アレクサ
ランキング
positive decrease 42,010 (December 2013)[1]

プロジェクト・オイラー: Project Euler、名称はレオンハルト・オイラー由来)は、数学やプログラミングなどに興味を持つ大人や学生が主な利用者であり、プログラミング (コンピュータ)による一連の計算問題の解決を目的としたウェブサイトである。 400以上[2]の問題の他に毎週末毎に1問ずつ増えており、様々な難問が用意されているが、 一般的なスペックのパソコンで効率的なアルゴリズムを用いれば、いずれも1分未満で解ける。 正答回答者のみが各問題の掲示板を閲覧できる[3]。 2001年に創設されて以来世界的な知名度と人気を得ており、2013年10月の時点では世界中から34万人以上の利用者(最低1問以上の正答者)を有する[4]。 利用者は正答数に応じて最大16のレベルが振り分けられ、各々の進捗状況を確認できる。

サイト内の問題はAPLのプログラミングコンテストでの使用実績があり[5]オンライン整数列大辞典では68問を引用している[6]

問題解答例[編集]

最初の問題

10未満且つ、3または5の倍数は、3、5、6、9であり、左の総和は23である。

同様に、1000未満且つ、3または5の倍数の総和を求めよ。[注 1]

上記の例は典型的な問題よりもはるかに易しいが、ここでは効率的なアルゴリズムにより本質的な違いを例示する為に挙げる。 力まかせ探索アルゴリズムは、1000未満のすべての自然数を調べ、基準値の総和を算出する。 以下に、簡単な擬似コードを示す :

Set TOTAL to 0;
for every number NUM from 1 to 999 do
  if NUM mod 3 = 0 or if NUM mod 5 = 0 then
    add NUM to TOTAL;
output TOTAL

難問解答の際には、効率的なアルゴリズムがより重要になる。 上記の場合は、包除原理閉形式総和により、1000回のループ文処理を避ける。

\begin{align}
\mathrm{sum}_{\text {3 or 5}}(n) & = \mathrm{sum}_3(n) + \mathrm{sum}_5(n) - \mathrm{sum}_{15}(n) \\

\mathrm{sum}_k(n) & = \sum_{i=1}^{\left \lfloor \frac{n-1}{k} \right \rfloor} ki \\

\sum_{i=1}^n ki & = k\frac{(n)(n+1)}{2}
\end{align}

この場合、\mathrm{sum}_k(n)n未満のkの倍数の総和を示す。 ランダウの記号による記法では、前述の力まかせ探索アルゴリズムはO(n)、上記の効率的なアルゴリズムはO(1)と示す。

脚注[編集]

注釈[編集]

  1. ^ 排他的論理和でなく論理和による

出典[編集]

  1. ^ Projecteuler.net Site Info”. Alexa Internet. 2013年12月1日閲覧。
  2. ^ Project Euler (list of problems)”. 2012年11月6日閲覧。
  3. ^ Project Euler - About”. 2008年4月4日閲覧。
  4. ^ Project Euler (Statistics) - not accessible for anonymous users”. 2012年11月16日閲覧。
  5. ^ APL programming contest”. 2010年11月2日閲覧。
  6. ^ OEIS sequences referencing Project Euler problems”. 2011年4月15日閲覧。

外部リンク[編集]