주어진 배열에 대한 GCD 쌍 찾기

Java Q&A: 주어진 배열의 GCD 쌍을 찾는 것은 배열에 있는 숫자의 최대 공약수(GCD)를 계산해야 하는 일반적인 질문입니다. Java에서는 유클리드 알고리즘을 사용하여 이 문제를 해결할 수 있습니다. 이 기사에서 PHP 편집자 Xigua는 Java를 사용하여 주어진 배열의 GCD 쌍을 찾는 방법을 작성하는 방법을 소개하여 독자가 이 알고리즘을 더 잘 이해하고 적용할 수 있도록 돕습니다.

질문 내용

n 크기의 정수 배열이 주어졌습니다. 여기서 n은 짝수입니다. 배열에서 2개의 숫자를 선택하고 gcd를 찾으세요. 마찬가지로 배열의 나머지 항목 중 2개 항목을 선택하고 gcd를 찾습니다. gcd 쌍을 찾으려면 위 단계를 반복하세요. gcd 값을 합산하여 가장 높은 합계를 얻습니다.

제약조건:

으아악

예 1:

으아악

답변:

으아악

지침:

으아악

예 2:

으아악

답변:

으아악

지침:

으아악

내 코드는 다음과 같습니다.

으아악

내 코드는 첫 번째 예에서는 작동하지만 두 번째 예에서는 잘못된 출력을 제공합니다. 디버깅을 해보니 제가 사용하고 있던 방법이 올바르지 않은 것으로 나타났습니다. 이 문제를 해결하는 올바른 방법은 무엇입니까?

Solution

총 gcd를 계산하는 가능한 모든 방법을 재귀적으로 검색할 수 있습니다. 무엇을 해야 할까요?

배열에 요소가 두 개만 포함된 경우 이 두 요소의 gcd만 반환할 수 있습니다.

더 많은 값이 포함되어 있으면 모든 값 쌍을 반복해 보겠습니다. 각 쌍에 대해 gcd를 계산하고 두 값이 모두 제거된 배열 복사본을 사용하여 함수를 재귀적으로 호출합니다. 두 계산의 결과를 더하면 현재 선택된 값 쌍에 대한 총 gcd를 얻습니다.

이제 우리는 지금까지 발견된 최고의 gcd를 추적하고 마지막에 반환합니다.

이것이 바로 그 일을 하는 코드입니다.

으아악

이 알고리즘은 꽤 느립니다. 작업 속도를 높여야 하는 경우 개선할 수 있는 영역이 최소한 두 가지 있습니다.

• gcd 계산은 비용이 많이 드는 작업입니다. 가능한 모든 고유 값 쌍의 gcd를 미리 계산하고 해시맵에 저장하면 이중 계산이 제거됩니다.
• 일부 가능한 순열을 여러 번 확인합니다. (예: 다음 재귀에서 첫 번째 쌍을 선택한 다음 두 번째 쌍을 선택하는 것은 두 번째 쌍을 선택한 다음 첫 번째 쌍을 선택하는 것과 같습니다.) 이 문제를 해결하는 방법에 대한 막연한 아이디어가 있지만 오늘 밤은 너무 늦었습니다. 죄송합니다. .

아마도 더 빠른 알고리즘이 있을 것입니다. 그건 단지 제 생각입니다.

Editor: 글쎄, 좀 자고 나니 문득 이해가 됐어요. 쌍을 생성할 때 외부 루프를 생략하면 쌍의 중복 정렬이 발생하지 않습니다. 기본적으로 다음과 같이 i를 모든 곳에서 0으로 바꾸십시오.

으아악

위 내용은 주어진 배열에 대한 GCD 쌍 찾기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!