어떻게 최대 공약수 를 구 합 니까?

1913 단어 알고리즘
제목:       코드 를 써 서 두 수의 최대 공약수 를 구하 고 알고리즘 의 성능 을 최대한 최적화 해 야 한다.       1. 폭력 매 거       2. 전전 상 제법       두 개의 정수 a 와 b (a > b), 그들의 최대 공약 수 는 a 를 b 로 나 눈 나머지 c 와 d 사이 의 최대 공약 수 와 같다.       3. 더 상 감 손 술       두 개의 정수 a 와 b (a > b), 그들의 최대 공약 수 는 a - b 의 차이 c 와 비교적 작은 b 의 최대 공약 수 와 같다.       4. 2 와 3 을 결합       a 와 b 가 모두 짝수 일 때 gcd (a, b) = 2 * gcd (a / 2, b / 2) = 2 * gcd (a > > 1, b > > 1)       a 가 짝수 이 고 b 가 홀수 일 때 gcd (a, b) = gcd (a / 2, b) = gcd (a > > 1, b)       a 가 홀수 이 고 b 가 짝수 일 때 gcd (a, b) = gcd (a, b / 2) = gcd (a, b > > 1)       a 와 b 가 모두 홀수 일 때 먼저 더욱 상 감 손 법 으로 한 번 연산 한다. gcd (a, b) = gcd (b, a - b) 는 이때 a - b 는 반드시 짝수 이 고 그 다음 에 이 위 연산 을 계속 할 수 있다.
public class getGreatestCommon {

    //         ,      O(min(a,b))
    public static int getGreatestCommonDivisor(int a,int b){
        int big = a>b ? a:b;
        int small = a1;i--){
            if(small % i==0 && big%i==0){
                return i;
            }
        }
        return 1;
    }

    //        ， a%b      
    public static int getGreatestCommonDivisorV2(int a,int b){
        int big = a>b ? a:b;
        int small = ab ? a:b;
        int small = a>1,b>>1)<<1;
        }else if((a&1) == 0 &&(b&1)!=0){
            return gcd(a>>1,b);
        }else if((a&1) !=0 &&(b&1)==0){
            return gcd(a,b>>1);
        }else{
            int big = a>b ? a:b;
            int small = a
C 언어 BFS (5)TT 와 마법사 (swustoj 2464)
Yii 2 프레임 워 크 에 API 모듈 추가

좋은 웹페이지 즐겨찾기

개발자 우수 사이트 수집

개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
best100-homepage