2

周囲の長さが p の整数直角三角形には多数の解 (a、b、c) があり、これらすべての解に対して a+b+c == p であり、ピタゴラスの定理も適用されます。周囲長が 1000 以下の三角形の解の最大数を計算する Python スクリプトを作成しています。

私のスクリプトは正しいですが、実行に時間がかかります。i7 プロセッサでも 30 分以上かかると思いますので、最適化する必要があります。誰かが私を助けることができますか？(これは Project Euler の問題です。疑問に思っている人がいる場合に備えて)

def solutions(p):
    result = []

    for a in range(1, p + 1):
        for b in range(1, p - a + 1):
            for c in range(1, p - a - b + 1):
                if a + b + c == p and a < b and b < c:
                    d = a ** 2
                    e = b ** 2
                    f = c ** 2

                    if (d + e == f) or (e + f == d) or (f + d == e):
                        result.append((a, b, c))
    return len(result)


max_p = 0
max_solutions = 0

for p in range(3, 1001):
    print("Processing %d" % p)
    s = solutions(p)

    if s > max_solutions:
        max_solutions = s
        max_p = p

print("%d has %d solutions" % (max_p, max_solutions))
4

4 に答える 4

1

これがあなたのプログラムの私の書き直しです。

まず、すべての2乗値を事前に計算します。これは乗算を回避するだけでなく、Pythonがすべての平方値のオブジェクトを絶えず作成してガベージコレクションするわけではないことを意味します。

次に、三角形の3番目の辺のループを取り除きました。aの値を選択しb、基準に一致する可能性のある値が1つしかない場合は、その値をa + b + c == 1000テストするだけです。これにより、問題が約O（n ^ 3）から約O（n ^ 2）に変わり、大幅に改善されます。

それから私はそれを実行してみました。私の4歳のコンピューターでは、約46秒で終了したので、そこで停止しました。

私はグーグル検索をして、この問題の議論を見つけました。私が見た議論が正しければ、このプログラムは正解を出力します。

upper_bound = 1000

sqr = [i**2 for i in range(upper_bound+1)]

def solutions(p):
    result = []

    for a in range(1, p - 1):
        for b in range(1, p - a):
            c = p - (a + b)
            if a < b < c:
                d = sqr[a]
                e = sqr[b]
                f = sqr[c]

                if (d + e == f) or (e + f == d) or (f + d == e):
                    result.append((a, b, c))
    return len(result)


max_p = 0
max_solutions = 0

for p in range(3, upper_bound+1):
    print("Processing %d" % p)
    s = solutions(p)

    if s > max_solutions:
        max_solutions = s
        max_p = p

print("%d has %d solutions" % (max_p, max_solutions))

編集：これは私が遊んでいたやや速いバージョンです。コメントに@gnibblerからの提案が組み込まれています。

upper_bound = 1000

sqr = [i**2 for i in range(upper_bound+1)]

def solution(p):
    count = 0
    for a in range(1, p - 1):
        for b in range(a, p - a):
            c = p - (a + b)
            d = sqr[a]
            e = sqr[b]
            f = sqr[c]

            if (d + e == f):
                count += 1
    return count

c, p = max((solution(p), p) for p in range(3, upper_bound+1))
print("%d has %d solutions" % (p, c))

私のコンピューターでは、このバージョンは46秒ではなく31秒かかります。

使用するというトリッキーなビジネスでmax()は、実際にはそれほど速くはなりません。正方形を事前に計算せずに試してみましたが、非常に遅いので、正確な時間を待ちたくありませんでした。

于 2013-02-07T05:24:07.467 に答える
1

より良いもの：

def solution(n):
    count = 0
    for c in range(n // 3 + 1, n // 2):
        for a in range(1, n // 3):
            b = n - a - c
            if b <= 0:
                continue
            if a >= b:
                continue
            if a * a + b * b != c * c:
                continue
            count += 1
    return count
于 2013-02-07T05:22:20.597 に答える
0

とった。a^2+b^2=c^2 の設定に依存してから、 p - a - b = c を代入するだけです

 1 from math import pow
  2 
  3 def see_if_right_triangle(p):
        solutions = 0
  4     # Accepts the perimeter as input
  5     for a in range(1, p): 
  6         for b in range(1, p):
  7             if 2*p*b + 2*p*a - pow(p, 2) == 2*a*b:
  8                solutions += 1
        print "The perimeter {p} has {sol} number of solutions".format(p=p, sol=solutions)
 10                        
 11 
 12 for p in range(3, 1001):
 13     see_if_right_triangle(p)

これはもっと最適化できると思います...特に、 a と b に受け入れる範囲を絞り込むための数学を理解する場合

于 2013-02-07T05:29:30.687 に答える
0

これは最適化されたコードではなく、私自身のコード (この問題に使用したもの) です。プログラムを非常に簡単にし、時間1000^3を反復する必要がないようにするために、いくつかの代数を実行することから始めました(abacb

# Project Euler 9
'''
Algebra behind Final Method:
a + b + c = 1000 | a^2 + b^2 = c^2
c = 1000 - (a + b) # Solving for C
a^2 + b^2 = (1000 - (a + b))^2 # Substituting value for C
a^2 + b^2 = 1000000 - 2000a - 2000b + (a + b)^2 # simplifying
a^2 + b^2 = 1000000 - 2000a - 2000b + a^2 + b^2 + 2ab # simplifying again
0 = 1000000 - 2000a - 2000b + 2ab # new formula
2000a - 2ab = 1000000 - 2000b # isolating A
1000a - ab = 500000 - 1000b # divide by 2 to simplify
a(1000 - b) = 500000 - 1000b # factor out A
a = (500000 - 1000b) / (1000 - b) # solve for A
'''
def pE9():
   from math import sqrt
   a, b, c = 1, 1, 1
   while True:
      b += 1
      a = (500000 - 1000 * b) / (1000 - b)
      c = sqrt(a**2 + b**2)
      if a + b + c == 1000 and a**2 + b**2 == c**2:
         break
   print int(a * b * c)

from timeit import timeit
print timeit(pE9, number = 1)

number = 11回の実行でテストするだけです。

出力：

>>> 
# Answer hidden
0.0142664994414
于 2013-02-07T18:49:48.307 に答える