자바 두 개의 비 마이너스 정수 최대 공약수 알고리즘[순환 법 과 재 귀 법]

본 논문 의 사례 는 자바 가 두 개의 비 마이너스 정수 최대 공약수 알고리즘 을 설명 하 였 다.여러분 께 참고 하도록 공유 하 겠 습 니 다.구체 적 으로 는 다음 과 같 습 니 다.
코드 기능:
1.자바 구현(전체 소스 코드 테스트 사례 첨부);
2.두 개의 비 마이너스 정수 p,q(p>=q)의 최대 공약수 풀이;
3.순환 법 과 재 귀 법 두 가지 구 해 사고;
전체 원본:

/* GCD:Greateast Common Divisor */
public class GCD{
 public static void main(String args[]){
  /* Test Case */
  int p = 32;
  int q = 24;
  System.out.println("The greatest divisior of "+p+" and "+q+" is 
"+
   "[ gcd1 ] : "+gcd1(p,q)+"
"+"[ gcd2 ] : "+ gcd2(p,q));
 }
 // (q % gcd ==0 AND p% gcd ==0 [gcd from q to 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;
    break;
   }
  }
  return gcd;
 }
 // gcd(p,q)=gcd(q,p%q)[if 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+")");
  return gcd2(q,r);
 }
}

캡 처 실행:

코드 설명:
순환 법 gcd 1(p,q)
자연 언어 설명:순환 법 은 두 개의 비 마이너스 정수 p,q(p>=q)의 최대 공약수,즉 q 의 공약수 중 p 의 공약수 의 최대 치 를 구 해 한다.d(피제수)를 p 에서 부터 점차 줄 이기 시작 합 니 다(체감 step=1)d 는 항상'조건 을 만족 시 킬 최대 치'입 니 다.d 가 조건 을 만족 시 킬 때(p 에 의 해 정 제 될 수도 있 고 p 에 의 해 정 제 될 수도 있 을 때),d 는 p 와 q 의 공약수 이 고 d 는 p,q 의 최대 공약수 입 니 다.
귀속 법 gcd 2(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)의 최대 공약수 이 링 의 시작 이지 만 링 의 끝 조건 q 가 0 이라는 것 을 잘 이해 하지 못 하고 p 로 돌아 갑 니 다.
아주 간단 한 풀이 최대 공약수 알고리즘 이지 만 굳이 두 가지 사고방식 으로 써 야 한다.주로 내 가 잘 모 르 는 귀속 법 을 다시 느끼 기 위해 서 이다.예전 에 한 노 타 와 피 보 나치 수의 귀속 알고리즘 을 구 해 내 는 것 을 보 았 을 때 명백 한 공식 이 거기에 밝 아 졌 는데 감개 무량 하 다.이것 은 완전히 수학 이 야!오늘 배 운 것 이 그때 보다 더 충격 적 이어서 무슨 문제 가 기묘 하 게 해결 되 었 는 지 모르겠다.나 는 메모리 나 효율 같은 지 표를 별로 신경 쓰 지 않 았 다.다만 이 녀석 이 정말 똑똑 하 다 고 생각 했 을 뿐이다.그들 에 게 컴퓨터 도 좋 고 프로 그래 밍 언어 도 좋 으 며 문 제 를 해결 하 는 도구 일 뿐 이 라 고 생각 했다.재 귀 는 컴퓨터 로 계산 하 게 하 는 알고리즘 을 생각 하 게 하 는 것 이 라 고 하 는데 정말 적절 한 표현 인 것 같다.
참고 자료
투 령 프로 그래 밍 총서:알고리즘(제4 판)세 치 웨 이 크(Robert Sedgewick)(저자),웨 인(Kevin Wayne)(저자),셀 로 윈(번역자)
자바 알고리즘 과 관련 된 내용 에 관심 이 있 는 독자 들 은 본 사이트 의 주 제 를 볼 수 있 습 니 다.
본 고 에서 말 한 것 이 여러분 의 자바 프로 그래 밍 에 도움 이 되 기 를 바 랍 니 다.