이 기사에서는 두 개의 비 음성 정수의 가장 큰 공통 구분을 해결하기위한 Java의 알고리즘에 대해 설명합니다. 다음과 같이 참조에 대해 공유하십시오.
코드 기능 :
1. Java 구현 (테스트 케이스가있는 전체 소스 코드);
2. 두 개의 비 음성 정수 P 및 Q (P> = Q)의 가장 큰 일반적인 제수를 해결합니다.
3. 두 솔루션 : 루프 방법 및 재귀 방법;
완전한 출처 코드 :
/ * GCD : Greateast Common Divisor */public class gcd {public static void main (String Args []) {/ * 테스트 사례 */int p = 32; int q = 24; System.out.println ( ""+p+"및"+q+"의 가장 큰 직종은 /n"+"[gcd1] :"+gcd1 (p, q)+" /n"+"[gcd2] :"+gcd2 (p, q)); } // (q % gcd == 0 및 p % gcd == 0 [q에서 1]) public static int gcd1 (int p, int q) {int gcd = 1; int d = q; while (d> 0) {d-; if (q%d == 0 && p%d == 0) {gcd = d; 부서지다; }} return gcd; } // gcd (p, q) = gcd (q, p%q) [q = 0, gcd = p] public static int gcd2 (int p, int q) {if (q == 0) return p; int r = p%q; //system.out.println("("+q+","+r+ ")"; 반환 gcd2 (q, r); }}스크린 샷 실행 :
코드 설명 :
원형 방법 GCD1 (P, Q)
자연 언어 설명 : 루프 방법은 두 개의 비 음성 정수 P, Q (p> = q)의 가장 큰 공통 구분을 해결합니다. D (분할) P에서 D (분할) 감소를하자 (감소 단계 = 1) d는 항상 "만족할 조건의 최대 값"입니다. d가 조건을 충족 할 때 (p로 나눌 수 있고 p로 나눌 수있는 경우), d는 p 및 q의 공통 제수이고, d는 p 및 q의 가장 큰 일반적인 제수이며;
재귀 방법 GCD2 (P, Q)
자연 언어 설명 : 재귀 방법은 두 개의 비 음성 정수 P, Q (p> = q)의 가장 큰 공통 구분을 해결합니다. Q가 0과 같을 때 가장 큰 일반적인 제수는 p입니다. 그렇지 않으면, 나머지 p와 q를 가져 가서 r = p%q를 얻고, p 및 q의 가장 큰 공통 구분은 q와 r의 가장 큰 일반적인 제수입니다.
코드 경험 :
루프 방법과 관련하여, 처음에, 내가 생각한 것은 공통 디바이저를 해결하는 방법을 작성하고, 정수 배열을 사용하여 비 음성 정수의 모든 공통 구분기를 저장 한 다음, P 및 Q에서 공통 가장 큰 공통 분배기를 비교하고 찾아 보는 것이었다. 나중에, 나는 최대 값을 찾는 것이기 때문에 뒷면에서 앞쪽으로 직접 감소하는 것이 더 쉽지 않다고 생각 했습니까? 뒷면에서 앞쪽으로 줄이면이 숫자가 현재 최대 규모가 될 수 있습니다. 조건을 충족하지 않는 것보다 큰 사람들이 (P 및 Q로 나눌 수 있음) 제거되므로 초기에 최대 값을 찾는 데 어려움을 겪지 않기 때문입니다. 최대 값을 찾는 방법은 여러 가지가 있지만 증명하고 검색 할 필요가 없다면 하하, 왜 철학에 대해 조금 느끼나요?
재귀와 관련하여, 직관에 근거하여 내가 완전히 이해할 수있는 것은 P와 Q의 가장 큰 일반적인 제수가 Q와 R (r = P%Q)의 가장 큰 일반적인 제수라는 유일한 문장이며, 이는 고리의 시작 인 링의 시작 조건이 0이고 P;
가장 큰 일반적인 구분 알고리즘에 대한 매우 간단한 솔루션이지만, 나는 주로 내가 익숙하지 않은 재귀 방법을 느끼기 위해 두 가지 방법으로 작성해야합니다. 과거에는 Hannover Tower와 Fibonacci 번호를 해결하기위한 재귀 알고리즘의 명확한 공식을 보았습니다. 내가 오늘 배운 느낌은 그 당시보다 훨씬 더 충격적이었습니다. 나는 무슨 일이 일어 났는지 궁금해하고 이상하게 해결했다. 당시에는 기억, 효율성 및 기타 지표에 대해별로 신경 쓰지 않았습니다. 나는 이것을 생각할 수있는 사람들이 정말 똑똑하다고 생각했습니다. 그들에게는 컴퓨터이든 프로그래밍 언어이든 문제를 해결하는 도구 일뿐입니다. 어떤 사람들은 재귀는 뇌가 컴퓨터에 대해 계산할 수있는 알고리즘이라고 말하며, 실제로 적절하다고 느낍니다.
참조
튜링 프로그래밍 시리즈 : 알고리즘 (4 판) Robert Sedgewick (저자), Kevin Wayne (저자), Xie Luyun (Translator)
Java 알고리즘에 대한 자세한 내용은이 사이트에 관심이있는 독자들이 주제를 볼 수 있습니다. "Java 데이터 구조 및 알고리즘 자습서", "Java Operation Dom Node Tips 요약", "Java 파일 및 디렉토리 작동 팁 요약"및 "Java Cache Operation Tips의 요약"을 볼 수 있습니다.
이 기사가 모든 사람의 Java 프로그래밍에 도움이되기를 바랍니다.