最近Project Eulerに登録して,ちょこちょこ解いています.何番煎じか分かりませんが,復習のために自分の解答をあげていこうと思います.目指せ,Eulerian !!

Problem 39 「整数直角三角形」

[問題文]
If p is the perimeter of a right angle triangle with integral length sides, {a,b,c}, there are exactly three solutions for p = 120.
{20,48,52}, {24,45,51}, {30,40,50}
For which value of p ≤ 1000, is the number of solutions maximised?

[和訳]
各辺の長さが整数$(a,b,c)$であるような直角三角形の周囲長を$p$とすると,$p=120$に対する解はちょうど3組存在する.
$$(20,48,52),(24,45,51),(30,40,50)$$ $p\leq 1000$を満たす$p$のうち,このような解の数が最大となるものはどれか?

方針

各$p$に対してループを回し,総当りで$(a,b,c)$を試し,$a^2 + b^2 = c^2$となるものを探していきます.
いくつかの不等式や代数拘束からループの数や繰り返し回数を減らしていきます.
(以下,$a\leq b\leq c$とします.)

繰り返し回数減らす

大雑把に考えましたが次のような性質を使いました.

pの範囲

最小の整数直角三角形は$(3,4,5)$のものです.このため,
$$12 \leq p \leq 1000$$
とすればOKです.

cの範囲

三角不等式$$c\leq a+b$$に$$a+b=p-c$$を代入して$$c\leq\frac{p}{2}$$

bの範囲

再び三角不等式$$c\leq a+b$$から$$c\leq a+b \leq 2b$$です.すなわち,$$\frac{c}{2}\leq b\leq c$$

aについて

$a$は範囲というより,拘束条件から$$a=p-b-c$$と定まりますね.

解答

というわけで,解答です.python3で書きました.

problem_39.py
#! -*- coding:utf-8 -*-
def finder():
    max,maxp = 0,0
    for p in range(12,1001):
        count = 0
        for c in range(1,(p+1)//2):
            for b in range(c//2,c):
                a = p - c - b
                if a**2 + b**2 == c**2:
                    count += 1
        if (count >= max):
            max = count
            maxp = p
    return maxp

def main():
    answer = finder()
    print(answer)

if __name__ == '__main__':
    main()
実行結果
$ python3 problem_39.py
840

難しくはありませんでしたが,一発で正解すると気持ちが良いです.


p.s. 先日Qiitaで「ネストが深くなる場合、ジェネレータ関数やジェネレータ内包表記にすると良い」という知見を得たので,上記のコードも内包表記ですっきり書きたかったのですが,イマイチ良いやり方が分かりませんでした:(
まだまだ修行が足りません!

Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account log in.