문제를 더 작은 동치 문제로 바꾼다.
유클리드 알고리즘은 두 정수의 공약수를 보존하면서 더 큰 문제를 빠르게 작아지는 나머지 순서쌍으로 바꿉니다.
생각해 볼 질문
a와 b를 b와 나머지로 바꿔도 최대공약수가 유지되는 이유는 무엇일까요?
- 나머지를 다음 문제 상태로 읽기
- 호출 사이에서 공약수가 유지되는 불변식 찾기
- 정확한 정수 프로세스를 0이라는 기저 사례까지 따라가기
- 줄어드는 호출 수열과 마지막 답 비교하기
어떤 수가 a와 b를 모두 나누면 a를 b로 나눈 나머지도 나눕니다. 반대 방향도 성립하므로 두 수의 순서쌍은 바뀌어도 최대공약수는 바뀌지 않습니다.
각 호출은 (a, b)를 (b, remainder(a, b))로 바꿉니다. 두 번째 값이 0이 되면 첫 번째 값이 보존된 최대공약수입니다. 재귀 호출 뒤로 미뤄 둔 계산은 없습니다.
(begin
(define (euclid a b)
(if (= b 0)
a
(euclid b (remainder a b))))
(euclid 206 40))리스펙스 학습용 런타임리스펙스 SICP 프로필 1.0.0
리스펙스 SICP 런타임 불러오는 중
리스펙스 · 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를 적용하고 이전의 두 번째 값을 첫 번째 자리로 옮기세요.