問題解答例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/09/01 02:54 UTC 版)
「プロジェクト・オイラー」の記事における「問題解答例」の解説
最初の問題 10未満且つ、3または5の倍数は、3、5、6、9であり、左の総和は23である。 同様に、1000未満且つ、3または5の倍数の総和を求めよ。 上記の例は典型的な問題よりもはるかに易しいが、ここでは効率的なアルゴリズムにより本質的な違いを例示する為に挙げる。 力まかせ探索アルゴリズムは、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回のループ文処理を避ける。 s u m 3 or 5 ( n ) = s u m 3 ( n ) + s u m 5 ( n ) − s u m 15 ( n ) s u m k ( n ) = ∑ i = 1 ⌊ n − 1 k ⌋ k i ∑ i = 1 n k i = k ( n ) ( n + 1 ) 2 {\displaystyle {\begin{aligned}\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{aligned}}} この場合、 s u m k ( n ) {\displaystyle \mathrm {sum} _{k}(n)} は n {\displaystyle n} 未満の k {\displaystyle k} の倍数の総和を示す。 ランダウの記号による記法では、前述の力まかせ探索アルゴリズムはO(n)、上記の効率的なアルゴリズムはO(1)と示す。
※この「問題解答例」の解説は、「プロジェクト・オイラー」の解説の一部です。
「問題解答例」を含む「プロジェクト・オイラー」の記事については、「プロジェクト・オイラー」の概要を参照ください。
- 問題解答例のページへのリンク
