0

私は現在、peulerの質問に取り組んでいます。例で提供されているコードでテストしたので、正しいコードを持っていると思います。ただし、500 を超える因数を持つ最初の三角数を見つけるために実行しようとすると、15 分以上実行されたままになります。しかし、因数が 100 を超える最初の三角数を見つけようとすると、1 分もかからずに見つかります。

下記を参照してください：

私の質問は、これをより速く計算するにはどうすればよいですか? くっつきそうだから？

#Project 12 #http://projecteuler.net/problem=12

def triangle(x) #finds the (x)st triangular number
    x=(1..x)
    return x.inject(:+)
end

def factors(x) #calculates how many factors (x) has
    factors =[]
    range=(1..x)
    range.each {|num|
    if x%num==0 
        factors << num
    end
    }
    return factors.length
    end 

def project12(x) #finds the first triangular number that has over (x) factors
i=1
    until factors(triangle(i)) > x
        i += 1
    end
return triangle(i)
end

print project12(500)
4

1 に答える 1

5

したがって、triangle(x) ではx-1足し算を行います。コード内でこれをiから まで実行すると、 が得られます。次に、要因によって、コードは基本的に時間通りに実行されます。これを ごとに行うので、 が得られます。i(i-1) + (1 + 2 + 3 + 4 + 5 + 6 + ... + i - 1) which approximates to i^2/2xtriangle(i)1*triangle(1) + 2*triangle(2) + 3*triangle(3) + 4*triangle(4) + ... + i*triangle(i) = 1*0 + 2*1 + 3*2 + 4*3 + ... + i*(i-1), which is approximately i^3/3 - i/3

これは何を意味するのでしょうか？これは、私のスケッチに基づいて、プログラムがほぼi^3/3 - i/3 + (i-1)反復で実行されることを意味します。これは立方時間であり、間違いなくスケーリングしません。

たとえば、これを まで実行する必要がある場合i = 50、これは 41699 回実行されます。ここで、もう一度だけ実行することを想像してみましょう: 44255 回 if i = 51. それは間違いなくスケールするつもりはありません。

于 2013-10-24T05:45:47.417 に答える