SICP 연습문제 풀이 일부
2013년도에 SICP 스터디를 하면서 풀었던 연습문제 일부를 취합했다.
Exercise 1.3
세 숫자를 인자로 받아 그 가운데 큰 숫자 두 개를 제곱한 다음, 그 두 값을 덧셈하여 내놓는 프로시저를 정의하라.
sort 함수 없이 가장 간단한 버전
(defn ex-1-3 [a b c]
(if (and (> a b) (> b c))
(+ (* a a) (* b b))
(if (and (> a b) (> c b))
(+ (* a a) (* c c))
(if (and (> a c) (> b c))
(+ (* a a) (* b b))
(+ (* b b) (* c c))))))
sort 함수를 사용한 버전
(defn ex-1-3 [a b c]
(let [[x y] (sort > [a b c])]
(+ (* x x) (* y y))))
Exercise 1.8
세제곱근 (cube root)을 구하는 뉴튼 법은, x의 세제곱근에 가까운 값을 y라고 할 때 다음 식에 따라 y보다 더 가까운 값을 계산하는 것이다.
$$\frac{x + y^{2} + 2y}{3}$$
제곱근 프로시저 처럼, 이 식을 써서 세제곱근 프로시저를 짜보자.
이미 앞에서 제곱근 구하는 코드를 짰기 때문에 필요한 부분만 수정하여 사용하면 된다.
(defn myabs [x]
(if (< x 0) (- x) x))
(defn cube [x]
(* x x x))
(defn good-enough? [guess x]
(< (myabs (- (cube guess) x)) 0.001))
(defn improve [guess x]
(/ (+ x (square guess) (* 2 guess)) 3))
(defn cubert-iter [guess x]
(if (good-enough? guess x)
guess
(cubert-iter (improve guess x) x)))
(defn cubert [x]
(cubert-iter 1.0 x))
그러나 실행하면, StackOverflowError 가 발생한다. 검색 결과, 위 문제에 중요한 오타가 있다. 정확한 식은 $(x/y^{2} + 2y) / 3$가 된다. 이에 따라 improve 함수를 고쳐 쓴다.
(defn improve [guess x]
(/ (+ (/ x (square guess)) (* 2 guess)) 3))
다시 돌려보면 정상 실행 확인할 수 있다.
=> (cubert 8)
(cubert 8)
2.000004911675504
=> (cubert 27)
(cubert 27)
3.0000005410641766
=> (cubert 64)
(cubert 64)
4.000017449510739
Exercise 1.11
$n < 3$일 때 $f(n) = n$ 이고, $n \geqq 3$ 일 때 $f(n) = f(n-1) + 2f(n-2) + 3f(n-3)$ 으로 정의한 함수 $f$가 있다. $f$의 프로시저를 되도는 프로세스 recursive process가 나오도록 짜라. 아울러, 반복 프로세스를 만들어 내는 프로시저도 만들어 보라.
먼저, 다음과 같이 scheme으로 재귀함수를 작성할 수 있다.
(define (f-recur n)
(cond ((= n 0) 0)
((< n 3) (+ 1 (f-recur (- n 1))))
(else (+
(f-recur (- n 1))
(* 2 (f-recur (- n 2)))
(* 3 (f-recur (- n 3)))))))
(define (f n)
(f-recur n))
clojure로는 다음과 같이 1:1로 변환할 수 있다.
(defn f-recur [n]
(cond
(= n 0) 0
(< n 3) (+ 1 (f-recur (- n 1)))
:else (+
(f-recur (- n 1))
(* 2 (f-recur (- n 2)))
(* 3 (f-recur (- n 3))))))
(defn f [n]
(f-recur n))
다음은 반복 버전 scheme 코드인데, 재귀 방식보다 더 성능이 좋지 않다.
(define (f-iter result cnt max-cnt)
(if (> cnt max-cnt)
result
(f-iter (cond
((= cnt 0) 0)
((< cnt 3) (+ 1 (f-iter 0 0 (- cnt 1))))
(else (+
(f-iter 0 0 (- cnt 1))
(* 2 (f-iter 0 0 (- cnt 2)))
(* 3 (f-iter 0 0 (- cnt 3)))))) ; result
(+ cnt 1)
max-cnt)))
(define (f n)
(f-iter 0 0 n))
다음은 clojure로 변환한 반복 버전. 역시 느리다.
(defn f-iter [result cnt max-cnt]
(if (> cnt max-cnt)
result
(f-iter
(cond
(= cnt 0) 0
(< cnt 3) (+ 1 (f-iter 0 0 (- cnt 1)))
:else (+
(f-iter 0 0 (- cnt 1))
(* 2 (f-iter 0 0 (- cnt 2)))
(* 3 (f-iter 0 0 (- cnt 3))))) ; result
(inc cnt)
max-cnt)))
(defn f [n]
(f-iter 0 0 n))
일단 이렇게 작성해놓고 나서 다른 사람들은 어떻게 작성했나 검색을 해봤더니, $n < 3$ 인 경우에는 대부분 그냥 간단하게 처리해버렸다. 내 경우에는 재귀로 처리할 수 있는 부분은 가급적 재귀로 처리하도록 했는데, 문제에서의 함수의 정의를 고려하면 다른 사람들이 작성한 것 처럼 간단하게 처리하는 쪽이 $f(n) = n$이라는 정의와 1:1 연관이 되어 좀더 알아보기 쉬우면서 같은 동작을 하는 함수를 작성할 수 있을 것 같다.
iteration 버전의 경우, 함수가 총 3개의 항으로 되어 있는데 반복할 때마다 각 항 별로 계산 값을 넘겨주어야 함수의 코드가 간단해지는 것 같다.
다음은 수정한 함수들이다. 먼저 재귀 버전.
(defn f-recur [n]
(if (< n 3)
n
(+ (f-recur (- n 1))
(* 2 (f-recur (- n 2)))
(* 3 (f-recur (- n 3))))))
(defn f [n]
(f-recur n))
다음은 반복 버전. 훨씬 간단해졌다. 실행해보니 overflow 전까지는 지연 없이 거뜬히 연산을 해낸다.
(defn f-iter [s1 s2 s3 cnt]
(if (< cnt 3)
s1
(f-iter (+ s1 (* 2 s2) (* 3 s3)) s1 s2 (dec cnt))))
(defn f [n]
(if (< n 3)
n
(f-iter 2 1 0 n)))
PS. 바로 위 반복 버전의 경우에는 인수를 다섯 개로 하거나 분량이 더 늘어나거나 하는 수정 삽질을 거치고 나니 코드를 수정하기 전에 잠깐 본 stackoverflow의 솔루션과 똑같아졌다.
몇초 잠깐 봤을 뿐인 내용이 무의식 중에 뇌리에 박혀서 유도를 하는 것일까.
Exercise 1.12
다음은 파스칼의 세모꼴 Pascal's triangle이다. 파스칼의 세모꼴 수를 만드는 프로시저를 짜되, 되도는 프로세스가 나오도록 하라.
1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 ...
지금까지 본 다른 예제는 n번째의 특정 값을 구하는 것이었는데, 이번 예제는 n번째 수열을 구해야 한다. scheme으로는 (찾으려면 찾을 수도 있지만) 리스트를 만들어 반환하는 함수는 아직 배우지 못했으므로, 바로 clojure로 작성하기로 했다. 어떻게 재귀 함수의 형태로 작성할 것인지 이리저리 궁리한 후, 다음과 같이 정리할 수 있었다.
위키피디아 의 내용을 참고하면, n번째 수열의 k번째 값 $P_{nk}$는 다음과 같이 정의할 수 있다.
\begin{equation} \begin{split} P_{nk} = & P_{(n-1)(k-1)} + P_{(n-1)k}, \newline P_{n1} = & P_{nn} = 1 \newline & where \quad n \geqq 1, 1 \leqq k \leqq n \end{split} \end{equation}
이에 따라 먼저, 1부터 n 번째까지 각 항의 파스칼의 삼각형 수를 구해 리스트에 더하는 함수를 짜고, 1과 n 사이의 k 번째 항의 파스칼의 삼각형 수를 구하는 함수는 재귀 함수로 작성을 했다. 작성한 코드는 다음과 같다.
(defn pascal-triangle-recur [n k]
(cond
(= k n) 1
(= k 1) 1
:else (+
(pascal-triangle-recur (dec n) (dec k))
(pascal-triangle-recur (dec n) k))))
(defn pascal-triangle [n]
(loop [result [] k n]
(if (zero? k)
result
(recur (cons (pascal-triangle-recur n k) result) (dec k)))))
실행 결과는 다음과 같다.
=> (pascal-triangle 1)
(1)
=> (pascal-triangle 2)
(1 1)
=> (pascal-triangle 3)
(1 2 1)
=> (pascal-triangle 4)
(1 3 3 1)
=> (pascal-triangle 5)
(1 4 6 4 1)
=> (pascal-triangle 6)
(1 5 10 10 5 1)
=> (pascal-triangle 7)
(1 6 15 20 15 6 1)
=> (pascal-triangle 8)
(1 7 21 35 35 21 7 1)
=> (pascal-triangle 9)
(1 8 28 56 70 56 28 8 1)
=> (pascal-triangle 10)
(1 9 36 84 126 126 84 36 9 1)
PS. scheme으로는 어떻게 작성했는지 웹 검색으로 좀 컨닝을 해봤더니, 대부분 n번째 행 k번째의 파스칼의 삼각형 값을 구하거나 (즉, (pascal-triangle-recur n k) 까지만 작성), 아니면 아예 1열부터 n열까지 구해서 삼각형 모양으로 출력하는 등 둘 중 하나를 따라서 했더군요.
Exercise 1.16
fast-expt처럼 계산 시간이 로그 비례로 늘어나면서 반복 프로세스를 수행하는 거듭제곱 프로시저 작성하기
(defn fast-expt [b n]
(fast-expt-iter b 1 n))
(defn fast-expt-iter [b a n]
(cond
(= n 0) a
(even? n) (fast-expt-iter (* b b) a (/ n 2))
:else (fast-expt-iter b (* a b) (dec n))))
Exercise 1.17
정수 값을 두 배로 하거나 반으로 나누는 프로시저가 있다고 가정하고, 이 프로시저를 써서
fast-expt처럼 계산 단계가 로그 비례로 자라나는 곱셈 프로시저를 작성하라.
정수 값을 두 배 또는 반으로 만드는 프로시저는 다음과 같다.
(defn twice [a]
(* a 2))
(defn halve [a]
(/ a 2))
재귀 버전을 작성하면 되는 것이므로 조금 더 쉽게 작성할 수 있다.
(defn fast-mul [a b]
(cond (= b 0) 0
(even? b) (twice (fast-mul a (halve b)))
:else (+ a (fast-mul a (- b 1)))))
Exercise 1.18
연습문제 1.16과 1.17에서 얻은 결과를 바탕으로, 계산 단계가 로그 비례로 자라나는 반복 프로세스가 되도록 곱셈 프로시저를 작성하라. (러시아 농사꾼 방식 Russian peasent method)
(defn twice [a]
(* a 2))
(defn halve [a]
(/ a 2))
(defn fast-mul-iter [a n p]
(cond
(= n 0) p
(even? n) (fast-mul-iter (twice a) (halve n) p)
:else (fast-mul-iter a (dec n) (+ p a))))
(defn fast-mul [a b]
(fast-mul-iter a b 0))
n 이 짝수나 아니냐 조건 비교 다음에 함수를 호출해줄 때 어떻게 인수를 갱신하여 넣는가 하는 것이 관건.
Exercise 1.19
피보나치 수열을 구하는 계산 단계가 다음과 같이 로그 차수로 자라나는 코드로 작성할 수 있다. 여기서 $p = 0, q = 1$이면 피보나치 수열을 구하는 함수가 된다. 여기서, $T_{pq}^{2} = T_{p'q'}$ 임을 증명하고, $p$와 $q$로 $p'$와 $q'$를 계산하는 식을 구하라. 이는 아래 코드의 update-p와 update-q 함수의 내용이 될 것이다.
(define (fib n)
(fib-iter 1 0 0 1 n))
(define (fib-iter a b p q count)
(cond ((= count 0) b)
((even? count)
(fib-iter a
b
(update-p p) ; calc p'
(update-q q) ; calc q'
(/ count 2)))
(else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(- count 1)))))
$T_{p'q'} = T_{pq}^{2}$ 는 다음과 같이 정리할 수 있다.
\begin{equation} \begin{split}a \leftarrow & \enspace bpq + aq^{2} + bq^{2} + aq^{2} + apq + bpq + apq + ap^{2} \newline \leftarrow & \enspace 2(a+b)pq + (2a+b)q^{2} + ap^{2} \newline = & \enspace bq' + aq' + ap' \end{split} \end{equation}
\begin{equation} \begin{split} b \leftarrow & \enspace bp^{2} + apq + bq^{2} + aq^{2} + apq \newline \leftarrow & \enspace 2apq + (a+b)q^{2} + bp^{2} \newline = & \enspace bp' + aq' \end{split} \end{equation}
윗 식을 정리하면, $p'$ 및 $q'$ 은 다음과 같이 구할 수 있다.
\begin{align} & p' = p^{2} + q^{2} \newline & q' = 2pq + q^{2} \end{align}
이를 update-p 및 update-q 함수로 표현하고 전체 코드를 clojure로 다시 작성한 답은 다음과 같다.
(defn update-p [p q]
(+ (* p p) (* q q)))
(defn update-q [p q]
(+ (* 2 p q) (* q q)))
(defn fib-iter [a b p q count]
(cond
(= count 0) b
(even? count) (fib-iter a
b
(update-p p q)
(update-q p q)
(/ count 2))
:else (fib-iter (+ (* b q) (* a q) (* a p))
(+ (* b p) (* a q))
p
q
(dec count))))
(defn fib [n]
(fib-iter 1 0 0 1 n))