Jan
24

SICP 연습문제 1.10

 연습문제 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)

Tags: , ,

Posted by pchero SICP(Structure and Interpretation of Computer Program Subscribe to RSS feed

Leave a Reply