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

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

Feb 22, 2024 pm 12:37 PM
최대공약수준비

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 중국어 웹사이트의 기타 관련 기사를 참조하세요!

성명
이 기사는 stackoverflow에서 복제됩니다. 침해가 있는 경우 admin@php.cn으로 문의하시기 바랍니다. 삭제

핫 AI 도구

Undresser.AI Undress

Undresser.AI Undress

사실적인 누드 사진을 만들기 위한 AI 기반 앱

AI Clothes Remover

AI Clothes Remover

사진에서 옷을 제거하는 온라인 AI 도구입니다.

Undress AI Tool

Undress AI Tool

무료로 이미지를 벗다

Clothoff.io

Clothoff.io

AI 옷 제거제

AI Hentai Generator

AI Hentai Generator

AI Hentai를 무료로 생성하십시오.

인기 기사

R.E.P.O. 에너지 결정과 그들이하는 일 (노란색 크리스탈)
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 최고의 그래픽 설정
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. 아무도들을 수없는 경우 오디오를 수정하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌
WWE 2K25 : Myrise에서 모든 것을 잠금 해제하는 방법
3 몇 주 전By尊渡假赌尊渡假赌尊渡假赌

뜨거운 도구

Atom Editor Mac 버전 다운로드

Atom Editor Mac 버전 다운로드

가장 인기 있는 오픈 소스 편집기

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse용 SAP NetWeaver 서버 어댑터

Eclipse를 SAP NetWeaver 애플리케이션 서버와 통합합니다.

스튜디오 13.0.1 보내기

스튜디오 13.0.1 보내기

강력한 PHP 통합 개발 환경

SecList

SecList

SecLists는 최고의 보안 테스터의 동반자입니다. 보안 평가 시 자주 사용되는 다양한 유형의 목록을 한 곳에 모아 놓은 것입니다. SecLists는 보안 테스터에게 필요할 수 있는 모든 목록을 편리하게 제공하여 보안 테스트를 더욱 효율적이고 생산적으로 만드는 데 도움이 됩니다. 목록 유형에는 사용자 이름, 비밀번호, URL, 퍼징 페이로드, 민감한 데이터 패턴, 웹 셸 등이 포함됩니다. 테스터는 이 저장소를 새로운 테스트 시스템으로 간단히 가져올 수 있으며 필요한 모든 유형의 목록에 액세스할 수 있습니다.

SublimeText3 중국어 버전

SublimeText3 중국어 버전

중국어 버전, 사용하기 매우 쉽습니다.