문제를 더 작은 동치 문제로 바꾼다.
유클리드 알고리즘은 두 정수의 공약수를 보존하면서 더 큰 문제를 빠르게 작아지는 나머지 순서쌍으로 바꿉니다.
생각해 볼 질문
a와 b를 b와 나머지로 바꿔도 최대공약수가 유지되는 이유는 무엇일까요?
- 나머지를 다음 문제 상태로 읽기
- 호출 사이에서 공약수가 유지되는 불변식 찾기
- 정확한 정수 프로세스를 0이라는 기저 사례까지 따라가기
- 줄어드는 호출 수열과 마지막 답 비교하기
어떤 수가 a와 b를 모두 나누면 a를 b로 나눈 나머지도 나눕니다. 반대 방향도 성립하므로 두 수의 순서쌍은 바뀌어도 최대공약수는 바뀌지 않습니다.
각 호출은 (a, b)를 (b, remainder(a, b))로 바꿉니다. 두 번째 값이 0이 되면 첫 번째 값이 보존된 최대공약수입니다. 재귀 호출 뒤로 미뤄 둔 계산은 없습니다.
SICP 코드UTF-8 111 / 1,048,576바이트
예제
결과—
- 출력
- —
- 값
- —
- 진단
- —
실행 추적0 / 0 개 이벤트
첫 프로그램은 2를 반환하고 두 번째 프로그램은 21을 반환합니다.
(206, 40), (40, 6), (6, 4), (4, 2), (2, 0)을 따라가세요. 두 번째 인수는 기저 사례에 닿을 때까지 계속 작아지고 마지막에 불변식으로 유지된 답이 드러납니다. 실행 흐름은 선택한 한 실행의 전체 나머지 수열을 기록합니다.
프로그램을 수정하고 결과를 비교해 보세요.
euclid를 1999와 97로 실행하세요. 마지막 최대공약수를 보기 전에 모든 인수 순서쌍을 적어 보세요.
힌트 보기
현재 순서쌍에 remainder를 적용하고 이전의 두 번째 값을 첫 번째 자리로 옮기세요.