Problem
빼기 연산이 나머지를 계산하는 연산으로 대체되는 유클리드 알고리즘의 또 다른 버전이 있습니다.
이 버전은 평균적으로 상당히 적은 수의 단계를 포함하기 때문에 오늘날 선호되는 것으로 간주됩니다. 그러나 컴퓨터가 크고 느렸던 시절에는 분할 작업 자체가 복잡한 절차가 될 수 있었습니다. 그러면 알고리즘의 첫 번째 버전이 더 효율적일 수 있습니다.
빼기를 모듈로 연산으로 대체하여 유클리드 알고리즘을 구현합니다.
두 개의 자연수
A와
B가 주어진다.
A와
B의 최대 공약수를 반환하는 함수
nod(A, B)를 작성하세요.
프로그램 예시
<헤드>
<일>#
| 입력 |
출력 |
<몸>
| 1 |
12 42 |
6 |
솔루션에서는 루프를 사용할 수 없습니다.
함수만 작성하면 되고 아무것도 입력하거나 출력할 필요가 없습니다!
Запрещенные операторы: for;while;do;until;gcd