간단한 모듈러스 연산

Question

그래서 C++을 배우고 있으며 내가 읽은 책 중 하나에서 GCF (최대 공통 인자)를 찾는 예제가 있습니다. 이 기능은 다음과 같다 :

int gcf(int a, int b) { 
    if(b == 0) { 
     return a; 
    } 
    else { 
     return gcf(b, a%b); 
    } 
} 

내가 이해하지 못하는 것은 그 그때

의미가 있지만,

a = 15 
b = 5 
b is not 0 so then the else statement executes 
(5, 15%5 = 0) so since b is now 0 it returns, a, which is 5. 

, 예를 들어 15 및 5에 넣으면 내가 숫자를 반전하는 경우, 왜/어떻게 같은 대답을 얻을 수 있습니까?

a = 5 
b = 15 
b is not 0 so then the else statement executes 
(15, 5%15) but 5%15 is .3 or 1/3, but in C++, 5%15 returns 5. 

5는 정수이기 때문에 어떤 경우에, 나는 그것이 어쩌면 0을 반환하지만 15을 반환하지 않는 생각, 어디에서 오는지 이해가 안, 그래서 수 없습니다.

Answer 1

여러분이하고있는 것은 정수 계산입니다. 부동 소수점 또는 분수는 포함되지 않습니다.

5 % 15은 실제로 5를 15로 나누고 나머지는 물론 5입니다 (몫은 0이됩니다). 정수 나눗셈에서

15 | 5 | 0 <-- this is the first call gcf(5, 15) 
     0 
    --- 
     5 | 15 | 3 <-- this is the first recursive call gcf(15, 5) 
      15 
     --- 
      0 | 5 | <-- this is the second recursive call gcf(5, 0), returns 5 

Answer 2

, 5%15 이후 5/15 = 0은 5. C 및 C++ 위임 할 필요가, 나머지의 부분 인 임의 a 및 b, a/b*b + a%b = a 대.

Answer 3

모듈러스 연산자는 나누기와 다르며 일반적으로 반환 값을 나눌 때 몫이지만 모듈러스 연산자를 사용하면 반환 값은 해당 알림입니다. 그래서

**

A = 5, B = 15이 반환 값 B A %은 0 케이스,

**

에 해당 그것이 돌아온 이유입니다. 모듈러스 연산자의 명확성을 위해 다음 링크를 확인하십시오. http://www.cplusplus.com/doc/tutorial/operators/

http://www.cprogramming.com/tutorial/modulus.html

Answer 4

당신이 거기서 작성한 코드는 유클리드의 보조 정리 (Euclid 's Lemma)에 기반한 유클리드 알고리즘이라고합니다. 교수님이 유클리드의 보조 정리의 다른 공식을 언급 할 수도 있다고 들었지만. 나의 Higher Alge 대수학 책은 특히 그것을 "동등한 gcd 's"로 언급한다. 상태 :

a, b, q 및 c를 a = qb + c로하는 정수로 둡니다. 그러면 gcd (a, b) = gcd (b, c)

gcd (a, b)는 a와 b의 최대 공약수를 나타냅니다. 이것은 프로그램에서 정확히 무엇을하고있는 것 같습니다.

임의의 정수 a는 b에 대해 qb + c로 쓸 수 있습니다. 이것은 a가 곱 qb와 약간의 나머지 c임을 의미합니다. 나머지는 % 연산자를 사용할 때 계산할 값입니다. a = 12와 b = 5라고하면 12 = 5q + c를 쓸 수 있습니다. q를 2로합시다. 그러면 나머지는 c는 2입니다. 아마도 이러한 것들은 초보적이지만, 이것은 책의 설명을 보완하는 좋은 배경이되기를 바랍니다.