Tag Archives: SICP

SICP 연습문제 1.10

Posted on by
1

 연습문제 1.10

 다음 프로세스를 이용하여 f, g, h 프로시저의 기능을 수학으로 정의하는 문제이다.

(Language : text)
  1. (define (A x y)
  2.     (cond ((= y 0) 0)
  3.         ((= x 0) (* 2 y))
  4.         ((= y 1) 2)
  5.         (else (A (- x 1) (A x (- y 1))))))

사용자 삽입 이미지
 프로시저 실행 문제의 답은 위와 같다.

 실질적인 문제는 바로 다음인데…..나는 노가다(?)로 풀었다.
 

(Language : text)
  1. (define (f n) (A 0 n))
  2.  
  3. (define (g n) (A 1 n))
  4.  
  5. (define (h n) (A 2 n))

 (f n) 의 경우

(Language : text)
  1. (f 1) = 2
  2. (A 0 1) = 4
  3.  
  4. (f 2) = 4
  5. (A 0 2) = 4
  6.  
  7. 즉 (f n) = 2n

 (g n)의 경우

(Language : text)
  1. (g 1) = 2
  2. (A 1 1) = 2
  3.  
  4. (g 2) = 4
  5. (A 1 2)
  6. (A 0 (A 1 1))
  7. (A 0 2) = 4
  8.  
  9. (g 3) = 8
  10. (A 1 3)
  11. (A 0 (1 2))
  12. (A 0 (A 0 (A 1 1)))
  13. (A 0 (A 0 2))
  14. (A 0 4) = 8
  15.  
  16. 즉, (g n) = g^n

 (h n)의 경우

(Language : text)
  1. (h 1) = 2
  3. (A 2 1) = 2
  5. (h 2) = 4
  6. (A 2 2)
  7. (A 1 (2 1))
  8. (A 1 2)
  9. (A 0 (A 1 1))
  10. (A 0 2) = 4
  12. (h 3) = 16
  13. (A 2 3)
  14. (A 1 (A 2 2))
  15. (A 1 (A 1 (A 2 1)))
  16. (A 1 (A 1 2))
  17. (A 1 (A 0 (A 1 1)))
  18. (A 1 (A 0 2))
  19. (A 1 4)
  20. (A 0 (A 1 3))
  21. (A 0 (A 0 (A 1 2)))
  22. (A 0 (A 0 (A 0 (A 1 1))))
  23. (A 0 (A 0 (A 0 2)))
  24. (A 0 (A 0 4))
  25. (A 0 8) = 16
  27. (h 4) = 65536
  28. (A 2 4) = 65536
  30. 즉, (h n) = 2^(A 2 n-1)

SICP 연습문제 1.9

Posted on by
Reply

 연습문제 1.9
 

(Language : xml)
  1. (define (+ a b)
  2.     (if (= a 0)
  3.         b
  4.         (inc (+ dec a) b))))
  5.  
  6. (define (+ a b)
  7.     (if (= a 0)
  8.         b
  9.         (+ (dec a) (inc b))))

 같은 프로시져가 있을 때, 각각의 프로시저가 (+ 4 5)를 계산한다고 한다면 반복 프로세스인지 재귀 프로세스인지를 알아보는 문제이다.

 솔직히 처음에 이 문제를 봤을때…둘다 재귀인 줄 알았다.

 프로시저가 끝나기 전에 자신을 호출하고 호출하고….하지만 이것은 C언어가 아니었다.

 역시나 한참을 헤매이다…노슈님의 블로그에서 해답을 찾았다.

 관련 링크 : http://nosyu.egloos.com/4058585

  첫 번째 프로시저의 실행 순서이다.

(Language : text)
  1. (+ 3 4)
  2.  
  3. (inc (+ 2 4))
  4. (inc (inc (+ 1 4)))
  5. (inc (inc (inc (+ 0 4))))
  6. (inc (inc (inc 4)))
  7. (inc (inc 5))
  8. (inc 6)
  9.  
  10. 7

 두 번째 프로시저의 실행 순서이다.
 

(Language : text)
  1. (+ 3 4)
  2. (+ 2 5)
  3. (+ 1 6)
  4. (+ 0 7)
  5.  
  6. 7

 역시나 실행 순서를 보면 한눈에 들어온다.

 즉, 첫 번째 프로시저는 재귀 프로세스(되도는 프로세스)이고, 두 번째 프로세스는 반복하는 프로세스이다.

사용자 삽입 이미지

SICP 연습문제 1.8

Posted on by
1

 참으로 허무한 문제다.

 분명 나의 계산에는 이상이 없었다.

 보고 또 보고, 계속 봐도 나는 틀린게 없었다.

 뭐가 문제지?

 답은 책이 잘못된 것이었다…..

 관련 링크 : http://www.buggymind.com/72

 한참을 끙끙대다가 인터넷의 도움을 받기로 하고 검색한 결과 어이없는 내용없다…(하하…)

 문제인즉, 세제곱을 구하는 공식이 틀렸던 것이다.

 아래의 공식이 정확한 공식이다.

사용자 삽입 이미지
 아래는 바뀐 코드 내용이다.

사용자 삽입 이미지

SICP 연습문제 1.7

Posted on by
Reply

 앞서만든 제곱근 구하기 프로그램의 개량된 버전을 만드는 내용이다.

 좀더 정확한 근사치를 구할 수 있도록 하는 프로그램인데…..

 결과적으로 못풀었다.

 알고리즘은 머리에 있는데….자세한 문법을 몰라 못풀었다.(…라고 말하고 싶다.)

 앞으로의 숙제이다.

 언제고 문제를 해결한다면 다시 이 포스팅을 다시 할 것이다. : )

 아래에 미처 못 푼 코드를 남겨둔다.

 사용자 삽입 이미지

SICP 연습문제 1.6

Posted on by
3

 제곱근을 구하는 식에서 사용한 if 라는 특별문을 임의의 프로시져로 바꾸어서 사용하는 문제이다.

 즉,

(Language : text)
  1. (define (sqrt-iter guess x)
  2.     (if (good-enough? guess x)
  3.         guess
  4.         (sqrt-iter (improve guess x)
  5.                 x)))

를 다음과 같이 바꾸어서 실행했을 때 어떤 결과 값이 나오겠느냐….이다.

(Language : text)
  1. (define (new-if predicate then-clause else-clause)
  2.     (cond (predicate then-clause)
  3.         (else else-clause)))

 처음에 혼자서 문제를 풀어 보았다. 잘 되지 않아서 정답을 찾아 보았다…

 관련 링크 : http://nosyu.egloos.com/4016689

 아하! 안되는 것이 맞구나…근데 내꺼는 코드가 약간 이상한데…다시 수정을 한 후, 실행을 해 보았다.

 그런데 결코 실행되어서는 안되는 코드가 척척 실행되는 것이다.

 왜 이럴까…한참을 고민하고 또 고민했다…

 나중에서야 어이없이 답을 알게 되었다.

 깜박하고 제일 마지막….

(Language : text)
  1. (define (sqrt x)
  2.     (sqrt-iter 1.0 x))

 부분을 입력을 안했던 것이다…..그런데 이상하게 실행을 척척 잘 되더라.

 원래는 되지 않아야 하는것이 정상일텐데…아마도 아직 내가 모르는 무언가가 있는 듯 하다.

 아무튼 문제를 해결하니 예상값이 정확하게 나왔다.

 참, 답은 무한 루프이다.

 변경된 new-if 에서 인자를 먼저 계산하니, (sqrt-iter (improve guess x) x) 부분에서 자꾸만 루프가 발생하는 것이다.

사용자 삽입 이미지
 오른쪽 하단에 러닝이 계속 돌아가는 것이 보인다.

 Stop을 누르니 kill 하겠냐는 메시지가 나온다. 당연히(?) Kill 했다.

사용자 삽입 이미지