Challenge 089

작업 #1 › GCD 합계

일

양의 정수$N가 제공됩니다. 1과 $N 사이의 가능한 모든 고유 쌍의 GCD를 합산하는 스크립트를 작성하십시오.

내 솔루션

이것은 비교적 간단합니다. 가능한 모든 고유 쌍은 1에서 $N - 2 사이의 첫 번째 숫자로 계산할 수 있으며 두 번째 숫자는 첫 번째 숫자보다 하나 더 많은 $N 까지 계산할 수 있습니다.

그런 다음 이 조합에 대한 GCD를 계산하는 문제입니다. 이를 위해 나는 두 개의 숫자 중 최소값을 취하고 하나의 숫자로 거꾸로 작업하는 서브루틴_gcd을 가지고 있습니다. 나머지 없이 두 숫자로 나눌 수 있는 첫 번째 값을 반환합니다.

예

» ./ch-1.pl 3
3

» ./ch-1.pl 4
7

작업 #2 › 마법의 매트릭스

일

아래와 같이 1~9의 숫자로 행렬을 표시하는 스크립트를 작성하세요. 숫자는 한 번만 사용하는지 확인하세요.
[ a b c ]
[ d e f ]
[ g h i ]
따라서 다음을 만족합니다.
a + b + c = 15
d + e + f = 15
g + h + i = 15
a + d + g = 15
b + e + h = 15
c + f + i = 15
a + e + i = 15
c + e + g = 15

내 솔루션

내 첫 번째 생각은 이것을 무차별 대입하는 것이 었습니다. 가능한 순열은 9입니다! = 362880이고 반쯤 괜찮은 컴퓨터라도 이것을 꽤 빨리 알아낼 수 있습니다.

그러나 더 빠르게 만들기 위해 약간 다른 접근 방식을 취했습니다.

가능한 모든 순서가 있는 세 자리 숫자 조합을 계산하여 합이 15가 됩니다. 8개의 조합만 있는 것으로 나타났습니다. 1 5 9, 1 6 8, 2 4 9, 2 5 8, 2 6 7, 3 4 8, 3 5 7, 4 5 6

이 행을 사용하여 모든 숫자가 사용되도록 이 행의 모든 ​​조합을 계산하십시오. 12개의 행이 반환되었습니다.

이것은 이제 가능한 솔루션이 6³ × 12(2,592)임을 의미합니다. 우리는 이 모든 것이 필요하지 않다는 것을 알고 있습니다. 예를 들어, 1은 항상 왼쪽 상단, 중간 상단 또는 중앙 위치에서 찾을 수 있습니다(다른 모든 위치는 이 중 하나의 미러/플립이 될 것입니다).

이 시점에서 저는 해결책을 찾을 때까지 무차별 대입 방식을 사용합니다.

각 행은 6가지 방법(abc, acb, bac, bca, cab, cba) 중 하나로 주문할 수 있습니다.

12개의 솔루션 각각에 대해 각 행의 6개 숫자 조합을 순환할 수 있습니다.

요구 사항을 충족하는 솔루션이 발견되면 솔루션을 인쇄하고 종료합니다.

다른 Team PWC 멤버들이 이 작업을 어떻게 처리할지 기대됩니다.

예

» ./ch-2.pl 
[ 6 1 8 ]
[ 7 5 3 ]
[ 2 9 4 ]