Project Eulerで用いた数学知識 - Scala日記
オイラーにちなんだ数学的なプログラミングの問題が出題されるサイト、Project Euler。 大体の問題は、greedy にやっても解けるんですが、適切な数学的知識を用いると時間計算量のオーダーが劇的に変わってきます。 そこで、１００問目まではラップトップで１秒以内（もちろん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 の問題に関してさえも）
Project Euler: Problem 23 - むしゃくしゃしてやった，今は反省している日記
問題はこちら。毎回、答え合わせに使っているProject Euler: Python solutionsよりも高速にできた。 方針としては 28123以下の過剰数のリスト abd を求める。 1.で作ったリスト abd を使い、1から28123までの全ての数について2つの過剰数の和で書けるか調べる。 2つの過剰数で書けない数の和を求める。 まずは、真の約数のリストを返すdivisorsを定義。（本当は真の約数の和を返せば十分だけど、後々使えそうなので） def divisors(n): divs = [1] for i in xrange(2, int(math.sqrt(n)) + 1): if n % i == 0: divs.append(i) if n/i not in divs: divs.append(n/i) divs.sort() return divs はじめ、メインの処
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
