주간 도전 172

Challenge , My solutions

작업 1: 프라임 파티션

일

두 개의 양의 정수 $m 및 $n 가 주어집니다.

주어진 번호의 Prime Partition을 찾는 스크립트를 작성하세요. 중복은 허용되지 않습니다.

내 솔루션

이것은 여러 가지 방법으로 해결할 수 있는 흥미로운 작업 중 하나입니다. 그리고 방법은 실제로 m 및 (더 중요한 것은) n 의 값에 따라 달라집니다.

제공된 예제의 값이 작은 경우 빠르고 쉬운 옵션을 선택했습니다. 이 방법에서는 모든 소수<=m의 목록을 수집하고 primes라는 목록(Perl의 배열)에 저장합니다. 그런 다음 itertool의 combinations 방법을 사용하여 n 크기의 모든 조합을 해결합니다. 합계가 m 값인 조합을 찾으면 결과를 인쇄하고 종료합니다. 찾지 못한 경우 적절한 메시지도 인쇄합니다.

Perl 버전의 경우 Algorithm::Combinatorics 모듈을 사용하여 Python의 itertools가 제공하는 것과 동일한 기능을 수행합니다. 이것은 Fedora(내 서버가 사용하는 OS)에서 RPM 패키지로 사용할 수 있으므로 좋은 선택인 것 같습니다.

이제 m 및 n가 더 큰 경우에 대한 논의입니다. 위 방법의 문제점은 n가 클 때 조합의 수가 기하급수적으로 증가한다는 것입니다. 이로 인해 합계가 너무 높거나 너무 낮아지는 많은 계산이 발생합니다.

예를 들어 7920의 소수 10개를 찾으려고 합니다. 1000번째 소수는 7919입니다. 목록을 높은 순위에서 낮은 순위로 정렬했기 때문에 첫 번째 gazillion을 의미합니다(정확하지는 않지만 26자리 숫자인 999 × 998 × ... × 991) 조합은 항상 너무 큰 숫자가 됩니다. 모든 조합을 통해 작업하는 대신 명확하게 유효하지 않은 조합을 제거할 수 있습니다. 예를 들어 첫 번째 숫자를 7829(990번째 소수)로 취하면 나머지 숫자의 합이 91보다 클 수 없다는 것을 알고 있습니다.

그러나 이 예는 m와 n가 (상대적으로 말해서) 더 작은 쪽에 있다는 기대를 명확하게 설정하므로 무차별 대입 방법이 충분합니다.

예시

$ ./ch-1.py 18 2
(13, 5)

$ ./ch-1.py 19 3
(11, 5, 3)

작업 2: 5자리 요약

일

정수 배열이 제공됩니다.

주어진 정수 세트의 five-number summary을 계산하는 스크립트를 작성하십시오.

내 솔루션

쉬운 해결책은 즉시 이를 지원하는 사용numpy일 것입니다. 하지만 그 재미는 어디에 있습니까? 이것이 직장에서 사용해야 하는 코드라면 실제로 import numpy가 스크립트의 맨 위에 있을 것입니다.

이 작업은 매우 간단하므로 실질적인 설명이 필요하지 않습니다. 정수를 가져와 가장 낮은 것부터 높은 것까지 정렬하고 각 사분위수에서 위치를 찾습니다. 해당 위치가 단일 값이 아닌 경우 두 값을 반으로 가져옵니다.

예시

$ ./ch-2.py 0 0 1 2 63 61 27 13
0, 0.5, 7.5, 44, 63