'sicp'에 해당되는 글 2건

  1. 2008.04.01 [연습문제] - 1.20
  2. 2008.04.01 [연습문제] - 1.3세수의 입력......

[연습문제] - 1.20

Study/SICP 2008. 4. 1. 23:49

문제)프로시저가 만들어 내는 프로세스는 마땅히 실행기의 계산 규칙에서 영향을 받는다. 앞서 나온 gcd프로시저를 보기 삼아서, 이런 문제를 살펴보자. 먼저 이번에는 (1.1.5절에서 선보인) normal-order evaluation을 따른다고 하자. (if를 normal-order evaluation방법은 연습문제 1.5에 있다.) substitution으로 (gcd 206 40)를 (normal-order)구하는 프로세스를 보이고, remainder 연산을 어디에서 쓰는지 표시하자. 프로세스가 끝날 때까지 remainder 연산을 얼마나 쓰는가? applicative-order evaluation하는 경우라면 또 어떠한가?


풀이)

normal-order로 구하는 프로세스는 따로 정의 할 필요 없을듯 해서 앞에서 나온 gcd프로시저를 그대로 사용

(define (gcd a b)

      (if (= b 0) a (gcd b (remainder a b))))

(remainder a b) 는 a를b로 나눈 수의 나머지를 취하는 프로시저다.. c언어에서의 %연산이라 생각하면됨.


normal-order evaluation 일때 remainder연산의 사용횟수 = 'rmd' 라 두고!!

(gcd 206 40)

    (if (= 40 0)  206  (gcd 40 (remainder 206 40)))       40 = 0 아니므로 뒤의 결과를 취함 rmd = 0

-> (gcd 40 (remainder 206 40)                                                                               rmd = 0

-> (if (= (remainder 206 40) 0)

        40

        (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))                          rmd = 0

-> (if (= 6 0)

        40

        (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))                          rmd = 1

-> (gcd (remainder 206 40) (remainder 40 (remainder 206 40)))                                rmd = 1

-> (if (= (remainder 40 (remainder 206 40)) 0)

        (remainder 206 40)

        (gcd (remainder 40 (remainder 206 40))

                (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))         rmd = 1

-> (if (= 4 0)

         (remainder 206 40)

        (gcd (remainder 40 (remainder 206 40))

                (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))         rmd = 3

-> (gcd (remainder 40 (remainder 206 40))

                (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))          rmd = 3

-> (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0)

        (remainder 40 (remainder 206 40))

        (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

                (remainder (remainder 40 (remainder 206 40))

                                 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))

                                                                                                                           rmd = 3

-> (if (= 2 0)

          (remainder 40 (remainder 206 40))

        (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

                (remainder (remainder 40 (remainder 206 40))

                                 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))

                                                                                                                           rmd = 7

-> (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

           (remainder (remainder 40 (remainder 206 40))

                            (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))

                                                                                                                           rmd = 7

-> (if (= (remainder (remainder 40 (remainder 206 40))

                            (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0)

         (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

         (gcd (remainder (remainder 40 (remainder 206 40))

                                 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

                 (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

                                 (remainder (remainder 40 (remainder 206 40))

                                 (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))))

                                                                                                                           rmd = 7

-> (if (= 0 0)

        (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

         (gcd (remainder (remainder 40 (remainder 206 40))

                                 (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))

                 (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))

                                 (remainder (remainder 40 (remainder 206 40))

                                 (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))))))

                                                                                                                           rmd = 14

-> (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))                       rmd = 14

-> 2                                                                                                                      rmd = 18

normal-order evaluation 하는 경우에는

프로세스가 끝날때 까지 사용한 remainder연산은 18번 이다.



applicative-order evaluation 일때 .... 마찬가지로 remainder연산을 rmd로 두고....

(gcd 206 40)

-> (if (= 40 0)

         206

         (gcd 40 (remainder 206 40))                                                                          rmd = 0

-> (gcd 40 (remainder 206 40))                                                                               rmd = 0

-> (gcd 40 6)                                                                                                         rmd = 1

-> (if (= 6 0)

        40

        (gcd 6 (remainder 40 6)))                                                                               rmd = 1

-> (gcd 6 (remainder 40 6))                                                                                    rmd = 1

-> (gcd 6 4)                                                                                                           rmd = 2

-> (if (= 4 0)

         6

         (gcd 4 (remainder 6 4)))                                                                                rmd = 2

-> (gcd 4 (remainder 6 4))                                                                                       rmd = 2

-> (gcd 4 2)                                                                                                           rmd = 3

-> (if (= 2 0)

         4

         (gcd 2 (remainder 4 2)))                                                                                 rmd = 3

-> (gcd 2 (remainder 4 2))                                                                                       rmd = 3

-> (gcd 2 0)                                                                                                            rmd = 4

-> (if (= 0 0)

         2

         (gcd 0 (remainder 2 0)))                                                                                 rmd = 4

-> 2

applicative-order evaluation 하는 경우에는

프로세스가 끝날때 까지 사용한 remainder 연산은 4번이다.

Posted by hazeyun

댓글을 달아 주세요

저번 스터디 모임때 화두가 됐던 문제입니다.

할일도 없고 잼있을거 같아서 겸사겸사 풀어봤는데요;;ㅋ

.

.

문제) 세개의 수를 입력받아서 그중에 두개의 큰수를 찾아서 그 두수의 제곱의 합을 구하는 프로시저를

작성하라..(대략 이런듯ㅋ)


풀이)  

(define (big x y)
  (if (< x y)
      y
      x))
(define (square x) (* x x))

(define (sum-of-square x y)
  (+ (square x) (square y)))

(define (check x y z)
  (if (< x y)
      (sum-of-square y (big x z))
      (sum-of-square x (big y z))))


저나름의 풀이는

일단 기존의 제곱함수인 square와 제곱의 합을 구하는 sum-of-square를 정의해주고 추가로 두 수를 입력

받아서 큰수를 찾아주는 big이라는(작명센스꽝ㅠ.ㅠ) 함수를 정의 해줬습니다. 

그리고 최종적으로 check라는 프로시저를 작성 했습니다.

.

.

이보다 더나은 해법도 물론 많겠지만 저의 머리로는....ㅋ

Posted by hazeyun

댓글을 달아 주세요