3

私は、各三角形の数の要素の数を計算して、それらの最初の要素が X 数を超える要素を持っていることを確認するいくつかの小さなソフトウェアを持っています (はい、それはプロジェクタイラーの問題であり、番号 12ですが、私は知りませんでした)まだ解決していません)... X にランダムな値を作成して、コードが何をどのくらいの時間で実行するかを確認しようとしているときに、(少なくとも私にとっては) 奇妙なことに気付きました: X=47 になるまで、実行時間は明らかに通常の方法で増加します、しかし、X = 48の場合、通常よりも増加し、関数呼び出しはレートよりもはるかに大きくなります..なぜそうするのですか??

コード：

def fac(n):
    c=0
    for i in range (1,n+1):
        if n%i==0:
            c=c+1
    return c

n=1

while True:
    summ=0
    for i in range (1,n+1):
        summ=summ+i
    if fac(summ)>X:
        break
    n=n+1

print summ

プロファイリング時:

when X=45 :  314 function calls in 0.027 CPU seconds
when X=46 :  314 function calls in 0.026 CPU seconds
when X=47 :  314 function calls in 0.026 CPU seconds
when X=48 :  674 function calls in 0.233 CPU seconds
when X=49 :  674 function calls in 0.237 CPU seconds

続けていれば、システムコールが増えたり、時間が急激に増えたりする点は他にもあると思いますが、以前はそういう点がありましたが、時間が小さかったのであまり気にならなかった. 新しい値のために関数をもう一度呼び出すだけではないでしょうか??

PSはcProfileをプロファイラーとして使用しXています。ここのコードはデモ用です。値をコードに直接書き込みます...よろしくお願いします...

4

2 に答える 2

6

関連する実際の値を見ましたか?

因数が 47 を超える最初の三角数は T(104) = 5460 で、因数は 48 です。

しかし、因数が 48 を超える最初の三角数は T(224) = 25200 で、因数は 90 です。そのため、さらに多くの作業が必要になるのも不思議ではありません。

コードが T( n )まで実行される場合、 range2 n回とfac n回、合計 3 n回の関数呼び出しが行われます。したがって、T(104) の場合は 312 回の関数呼び出しが必要であり、T(224) の場合は 672 回の関数呼び出しが必要です。おそらく、表示されていないオーバーヘッドの関数呼び出しが 2 つあります。これにより、得られるプロファイリング結果が説明されます。

あなたの現在の戦略では、プロジェクト オイラーの問題の答えは得られません。しかし、私はいくつかのヒントを与えることができます。

  • summ=0三角数を計算するたびに最初からやり直す必要がありますか?
  • 除数の数を計算するために、 nまでのすべての数値をループする必要がありますか? より速い方法はありますか？(2 16 = 65536 にはいくつの約数がありますか? 1 から 65536 までのすべての数値をループする必要がありますか?)
  • 三角数の約数はいくつ？(答えを計算できるいくつかの小さな三角数を見てください。) もっと大きな三角数の答えを計算するのに役立つパターンを見つけられますか?
于 2011-08-06T23:44:25.187 に答える
3

出力を確認すると、実行時間にいくつかのスパイク (急激な増加) が見られます。

その理由は、必要なループの数が徐々に増加するのではなく、急激に増加するためです。nループした後に印刷するwhile Trueと、それが表示されます。

注: Euler は数学のサイトです。ブルート フォース アルゴリズムを記述しないでください ;)

于 2011-08-06T23:43:42.550 に答える