5

私は Project Euler の問題のリストをゆっくりと調べていて、解決方法を知っている問題にたどり着きましたが、それはできないようです (私の解決策が書かれた方法を考えると)。

私はこれを行うために Common Lisp を使用しており、私のスクリプトは 24 時間以上実行されています (1 分間の目標をはるかに超えています)。

簡潔にするために、これが私の解決策です（ネタバレですが、非常に高速なプロセッサを持っている場合のみ）：

(defun square? (num)
  (if (integerp (sqrt num)) T))

(defun factors (num)
  (let ((l '()))
    (do ((current 1 (1+ current)))
        ((> current (/ num current)))
      (if (= 0 (mod num current))
          (if (= current (/ num current))
              (setf l (append l (list current)))
              (setf l (append l (list current (/ num current)))))))
    (sort l #'< )))

(defun o_2 (n)
  (reduce #'+ (mapcar (lambda (x) (* x x)) (factors n))))

(defun sum-divisor-squares (limit)
  (loop for i from 1 to limit when (square? (o_2 i)) summing i))

(defun euler-211 ()
 (sum-divisor-squares 64000000))

より小さく、より親しみやすいテスト引数を使用して問題を解決するのに必要な時間は、指数関数的よりも大きくなるようです...これは実際の問題です。

それは取った：

  • 100 を解くのに 0.007 秒
  • 1000 を解くのに 0.107 秒
  • 10000 を解くのに 2.020 秒
  • 100000 を解くのに 56.61 秒
  • 1000000 を解くのに 1835.385 秒
  • 64000000 の解決に 24 時間以上

スクリプトのどの部分が非常に時間がかかる原因になっているのかを突き止めようとしています。因子関数をメモ化することについていくつか考えましたが、実際にそれを実装する方法について途方に暮れています。

問題自体を調べたい人は、ここにあります。

このことをより速くする方法についてのアイデアは大歓迎です。

**スポイラーである場合は申し訳ありませんが、意図したものではありません....しかし、これを適切な時間で実行するための計算能力があれば、より多くのパワーが得られます.

4

7 に答える 7

14

[Project] Euler の精神を念頭に置いた解決策を次に示します。【注意：ネタバレ。答えの一部だけを読んで、必要に応じて自分で考えられるように、ヒントを遅くするように努めました。:)]

数字に関係する問題に直面したとき、1 つの良い戦略は (おそらく 210 のプロジェクト オイラーの問題を解決することで既に知っているように) 小さな例を見て、パターンを見つけ、それを証明することです。[最後の部分は、数学に対するあなたの態度に応じてオプションかもしれません;-)]

ただし、この問題では、n=1、2、3、4 などの小さな例を見ても、おそらく何のヒントも得られません。しかし、数論の問題を扱う場合には、もう 1 つの「小さな例」の意味があります。これはおそらくもうご存知でしょう。素数は自然数の構成要素であるため、素数から始めます。

素数 p の場合、その唯一の約数は 1 と p であるため、その約数の 2 乗の和は 1+p 2です。
素数 p kの場合、その唯一の約数は 1、p、p 2、… p kであるため、その約数の 2 乗の和は 1+p+p 2 +…+p k =(p k+1 - 1)/(p-1)。
これが最も単純なケースでした。素因数が 1 つだけのすべての数の問題を解決しました。

これまでのところ、特別なことは何もありません。ここで、 2 つの素因数を持つ数値 n があるとします(n=pq とします)。その場合、その因数は 1、p、q、および pq であるため、その除数の 2 乗和は 1+p 2 +q 2 +p 2 q 2 =(1+p 2 )(1+q 2 ) です。
n=p a q bはどうですか？その因数の二乗和はいくつですか?

[.....................................この行より下を読むのは危険です....... ....]

∑ 0≤c≤a, 0≤d≤b (p c q d ) 2 = ((p a+1 -1)/(p-1))((q b+1 -1)/(q -1))。

それは答えが何であるかとそれを証明する方法の両方についてのヒントを与えるはずです. do は 64000000 を因数分解し (これは頭の中で行うのは非常に簡単です :-))、その素数べき乗のそれぞれ (= 両方、素数は 2 と 5 しかないため) の答えを掛けます。

これにより、Project Euler の問題が解決されます。今、それから取り除く道徳。

ここでのより一般的な事実は、乗法関数に関するものです。つまり、gcd(m,n)=1 の場合は常に f(mn) = f(m)f(n) となるような自然数の関数です。つまり、m と n には素因数がありません。一般。そのような関数がある場合、特定の数での関数の値は、素数べき乗での値によって完全に決定されます (これを証明できますか?)

証明しようとすることができる少し難しい事実[それほど難しくない]は、次のとおりです。乗法関数f [ここでは、f(n)=n 2 ]があり、関数FをF(n) = ∑ d は n f(d) を割ります (問題がここで行ったように)、F(n) も乗法関数です。

[実際、非常に美しいものが真実ですが、まだそれを見ないでください。おそらくそれは必要ないでしょう。:-)]

于 2008-12-03T02:53:46.567 に答える
3

あなたのアルゴリズムは可能な限り最も効率的ではないと思います。ヒント: 間違った側から始めている可能性があります。

編集:上限として 64000000 を選択することは、投稿者がより良いものを考えるように伝える問題の方法である可能性が高いことを追加したいと思います。

編集:いくつかの効率のヒント:

  • それ以外の
(setf l (l (...) を追加))

あなたが使用することができます

(プッシュ (...) l)

これは、値をcar、前者lをcdrとして新しいセルをconsすることにより、リストを破壊的に変更lし、このセルを指します。これは、リストを 1 回ずつトラバースする必要がある追加よりもはるかに高速です。他の順序でリストが必要な場合は、完了後に nreverse できます (ただし、ここでは必要ありません)。

  • なぜソートするのlですか？

  • (> current (/ num current))代わりに num の平方根と比較することで、より効率的にすることができます(num ごとに 1 回だけ計算する必要があります)。

  • 数の因数をより効率的に見つけることはおそらく可能ですか?

そしてスタイルのヒント: のスコープをldo 宣言に入れることができます:

(する ((l ())
     (現在の 1 (+ 現在の 1)))
    ((> 現在 (/現在の数))
     l)
  ...)
于 2008-12-03T01:43:48.500 に答える
2

数値の素因数分解 (例: 300 = 2^2 * 3^1 * 5^2) を行うことでこれを攻撃します。これは、特にふるいによって生成する場合は比較的高速です。このことから、i=0..2 を繰り返して因数を生成するのは比較的簡単です。j=0..1; k=0..2 で、2^i * 3^j * 5^k を実行します。

5 3 2
-----
0 0 0 = 1
0 0 1 = 2
0 0 2 = 4
0 1 0 = 3
0 1 1 = 6
0 1 2 = 12
1 0 0 = 5
1 0 1 = 10
1 0 2 = 20
1 1 0 = 15
1 1 1 = 30
1 1 2 = 60
2 0 0 = 25
2 0 1 = 50
2 0 2 = 100
2 1 0 = 75
2 1 1 = 150
2 1 2 = 300

これは十分に速くないかもしれません

于 2008-12-03T02:52:59.843 に答える
2

あなたが見逃している巧妙なトリックは、数字を因数分解する必要がないことです.1..N から 1 の倍数はいくつありますか? N 1..N のうち、2 の倍数は何個? N/2

秘訣は、リスト内の各数値の因数を合計することです。1 の場合、リスト内のすべての数値に 1^2 を追加します。2 の場合は、1 つおきに 2^2 を足します。3 の場合、3 番目の数値ごとに 3^2 を追加します。

割り切れるかどうかはまったくチェックしません。最後に、合計が完全な平方かどうかを確認する必要があります。それだけです。C++ では、これは 58 秒で機能しました。

于 2009-03-11T01:48:32.697 に答える
1

申し訳ありませんが、あなたの回答を読むのに十分なほどLISPを理解していません。しかし、ブルート フォース ソリューションの時間コストは次のようになるはずだというのが私の第一印象です。

開き括弧

sqrt(k) を使用して k の約数を求め (試行分割により)、それぞれを 2 乗し (因子ごとの定数時間)、それらを合計します (因子ごとの定数時間)。これが σ 2 (k) で、これを x と呼びます。

プラス

良い整数平方根アルゴリズムの複雑さはわかりませんが、確かに sqrt(x) (愚かな試行乗算) より悪くはありません。x は k よりも大きいかもしれないので、ここで判断を留保しますが、k には最大で k 個の約数があり、それぞれが k より大きくないため、その平方が k より大きくないため、x は明らかに k^3 で制限されます。 ^2. 数学の学位を取得してから長い時間が経ち、ニュートン・ラフソンが収束する速さはわかりませんが、sqrt(x) よりも高速であると思われます。

閉じ括弧

n を掛けます (k の範囲は 1 .. n として)。

したがって、アルゴリズムが O(n * sqrt(n^3)) = O(n ^ (5/2)) より悪い場合、ダム平方の場合、または O(n * (sqrt(n) + log( n^3)) = O(n ^ 3/2) 巧妙な sqrt の場合、アルゴリズムで識別できるはずの何かが間違っていると思います.この時点で、LISP をデバッグできないため行き詰まっています.

ああ、算数は使用中の数値に対して一定時間であると想定しました。それは 6400 万という小さな数値に対応する必要があり、その 3 乗は 64 ビットの符号なし整数にかろうじて収まります。しかし、LISP の実装が算術演算を O(1) より悪化させているとしても、O(log n) より悪化してはならないので、複雑さにはあまり影響しません。確かに超多項式にはなりません。

ここに誰かがやって来て、私がどれほど間違っているかを教えてくれます。

おっと、私はちょうどあなたの実際のタイミング図を見ました。それらは指数関数より悪くはありません。最初と最後の値を無視して (短い時間は正確に測定できず、それぞれ終了していないため)、n に 10 を掛けても、時間は 30 倍以下になります。30 は約 10^1.5 であり、これは上記の総当たり攻撃にほぼ適しています。

于 2008-12-03T01:16:34.127 に答える
0

この問題は、プライムシーブのようなもので攻撃できると思います。それは私の最初の印象にすぎません。

于 2008-12-03T01:35:22.777 に答える
0

ここのコメントから取ったいくつかのメモを使用して、プログラムを作り直しました。「factors」関数はこれまでになくわずかに効率的になり、新しい出力を受け入れるように σ_(2)(n) 関数も変更する必要がありました。

「要因」は、次のような出力を持つことから始まりました:

$ (factors 10) => (1 2 5 10)

好きな人を持つこと

$ (factors 10) => ((2 5) (1 10))

修正された関数は次のようになります。

(defun o_2 (n)
"sum of squares of divisors"
  (reduce #'+ (mapcar (lambda (x) (* x x)) (reduce #'append (factors n)))))

適度に書き直した後、100,000 の計算で約 7 秒しか節約できませんでした。

お尻から降りて、より直接的なアプローチを書かなければならないようです。

于 2008-12-03T05:50:57.567 に答える