파이썬으로 수학문제 풀기- 프로젝트 오일러(project euler, 22번부터)

프로젝트 오일러 39번 - 직각 삼각형의 갯수

둘레 120으로 만들수 있는 길이가 정수인 직각 삼각형은 ( 20, 48, 52 ), ( 24, 45, 51 ), ( 30, 40, 50 )  이렇게 3개가 있습니다. 1000이하의 둘레의 길이중에서 직각 삼각형을 가장 많이 만들수 있는 둘레의 길이를 찾는것이 문제입니다.

 

1. 일단 피타고라스 정리를 알아야 겠죠? 

2. 그런다음에 두변을 loop 문으로 변화를 주면서 나머지 한변을 피타고라스 정리로 구했을때, 정수로 떨어지는가를 확인하면 간단합니다.

3. 그리고 그 조건을 만족할때 결과값을 1000 개짜리 list 에 저장하되, list의 index가 자동으로 그 삼각형의 둘레값이 되도록 index를 a+b+c 로 주면, 마지막에 최대값을 쉽게 구할수 있습니다.

 

루프 & 피타고라스 삼각형
for c in range(1,100):
    for a in range(1,c):
        b=(c**2-a**2)**0.5 # 피타고라스 정리
        if b == int(b):
            print(c,a,b,a+b+c)
5 3 4.0 12.0
5 4 3.0 12.0
10 6 8.0 24.0
10 8 6.0 24.0
13 5 12.0 30.0
13 12 5.0 30.0
15 9 12.0 36.0
15 12 9.0 36.0
...

위의 결과는 똑같은 삼각형이 두번씩 출력되고 있습니다. 그 이유는 a, b 값이 서로 값만 바뀌면서 중복 생성되고 있기때문입니다.  그래서 a의 루프값이 b 값보다 크지 않도록( 또는 그 반대로 ) 루프를 수정해줘야 합니다.

a값이 b보다 작기 위해서는, 빗변 c 와 밑변 a 사이의 각이 45도를 넘으면 안되고, 그말은 a의 최대값은 c의 코사인 45도인 (2분의 루트 2 ;;; 수식이,,,) c/2**0.5 가 되고, 정수여야 하기 때문에 int() 함수를 취해주면 range(1,int(c/2**0.5)) 가 됩니다. 그리고 range()의 종료값은 포함이 안되기 때문에, 다시 1을 더 더해줘야 합니다. (1을 빼먹으면,, 그 유명한,, 3,4,5 삼각형이 안나옵니다,, 물론 결과에는 지장이 없습니다,, 최대값이 나오는 구간이 아니라서,,)

for c in range(1,100):
    for a in range(1,int(c/2**0.5)+1):
        b=(c**2-a**2)**0.5
        if b == int(b):
            print(c,a,b,a+b+c)
5 3 4.0 12.0
10 6 8.0 24.0
13 5 12.0 30.0
15 9 12.0 36.0
17 8 15.0 40.0
20 12 16.0 48.0
25 7 24.0 56.0
...

 

결과값 저장

조건을 만족할때마다 카운트를 해 준 다음엔, 둘레 a+b+c 가 1000보다 작거나 같으면, 결과 list 에다 저장을 시킵니다. index값을 a+b+c로 주고, 해당 index에 카운트를 하나씩 올려주면, 자동으로 최대값이 합산이 되고, 마지막에 최대값을 뽑아내면 됩니다.

result=[0]*300
for c in range(1,100):
    for a in range(1,int(c/2**0.5)):
        b=(c**2-a**2)**0.5
        if b == int(b) and a+b+c <= 1000:
            result[int(a+b+c)] += 1
print(result)

 

최대값은

print(max(result))
print(result.count(8))
print(result.index(8))

이런식으로 뽑아낼수 있고,

아니면 한번에 아래처럼 쓸수도 있습니다.

print(max(result), result.index(max(result)))

 

댓글

댓글 본문
작성자
비밀번호
버전 관리
nomadlife
현재 버전
선택 버전
graphittie 자세히 보기