HW3 解答

每小題 2 分

Ex1.19

　　p' = p*p + q*q
　　q' = 2*p*q + q*q
　　注意：寫成 Scheme 的 code 時是：
　　　　　(+ (* p p) (* q q)) 及 (+ (* 2 p q) (* q q))

Ex1.22

　　此題分為四個部份：
　　(1) Scheme 的程式碼。
　　(2) 分別找出大於 1000, 10000, 100000, 1000000 的三個質數。
　　(3) 計算這些質數所需要的時間。
　　(4) 說明你的數據是不是支持 √n 的複雜度。
　　少一個部分扣 0.5 分。

Ex1.26

　　這題幾乎沒有人寫得完全正確，所以只要寫到以下兩點，就可以拿到 1.5 分：
　　(1) 造成差別的是在於 (expmod　base　(/　exp　2)　m) call 了兩次。
　　(2) 解釋為何 call 兩次就會造成複雜度從 log(n) 變到 n。
　　正解：
　　Observation:
　　　No matter 'exp' is even or odd, the program should run the following instructions
　　　　(1) (= exp 0)
　　　　(2) (even? exp)
　　　　(3) (remainder ... )
　　　　(4) (* ... )
　　　So, we can assume run time of the above 4 instruction is equal to C。
　　　Because runtime of (expmod based exp m) depends only on exp,
　　　　we can assume run time of the program is T(exp).
　　Proof:
　　　from the program, we have:
　　　　T(exp) = C + T(exp - 1) 　　 if exp is odd.
　　　　T(exp) = C + 2*T(exp/2) 　　 if exp is even.
　　　solve this recurrence relation, we have:
　　　　T(exp) = C * exp - C
　　　So, the time complexity of the program is Θ(n).
　　Note that,
　　　for simplification, we don't take (/ exp 2) and (- exp 1) into consideration,
　　　but even take all of them into consideration, only the constant C will be changed.

Ex1.32

　　此題請直接參看下面的 Sample Code。

Ex1.43

　　此題請直接參看下面的 Sample Code。

Scheme Sample Code

download sample code

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;       Ex1.19
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; recursive fib
(define (fib-rec n)
   (cond ((= n 0) 0)
         ((= n 1) 1)
         (else (+ (fib-rec (- n 1))
                  (fib-rec (- n 2)) ))))
; iterative fib
(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
                    (+ (* p p) (* q q))
                    (+ (* 2 p q) (* q q))
                    (/ count 2)))
         (else (fib-iter (+ (* b q) (* a q) (* a p))
                         (+ (* b p) (* a q))
                         p
                         q
                         (- count 1)))))


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Ex1.22
;;    You can test:
;;     (search-for-prime 1000 3)
;;     (search-for-prime 10000 3)
;;     (search-for-prime 100000 3)
;;     (search-for-prime 1000000 3) 
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (timed-prime-test n)
   (start-prime-test n (runtime)))

(define (start-prime-test n start-time)
   (if (prime? n)
       (begin
         (newline)
         (display n)
         (report-prime (- (runtime) start-time)))
       #f ))

(define (report-prime elapsed-time)
   (display " *** ")
   (display elapsed-time)
   #t )

(define (prime? x)
   (define (iter n bound)
      (if (> n bound)
          #t
          (if (= (modulo x n) 0)
              #f
              (iter (+ n 1) bound) ) ) )
   (iter 2 (sqrt x)) )

(define (search-for-prime x n)
   (cond ((even? x) (search-for-prime (+ x 1) n))
         ((> n 0)
          (if (timed-prime-test x)
              (search-for-prime (+ x 2) (- n 1))
              (search-for-prime (+ x 2) n) ) ) ) ) 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Ex1.32
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
; a. (recursive version)
(define (accumulate combiner null-value term a next b)
   (if (> a b)
       null-value
       (combiner (term a)
                 (accumulate combiner
                             null-value
                             term
                             (next a)
                             next
                             b ) ) ) )
(define (sum term a next b)
        (accumulate + 0 term a next b))
(define (product term a next b)
        (accumulate * 1 term a next b))

; b. (iterative version)
(define (accumulate-iter combiner null-value term a next b)
   (define (iter x result)
      (if (> x b)
          result
          (iter (next x) (combiner result (term x)) ) ) )
   (iter a null-value) )

(define (sum-iter term a next b)
        (accumulate-iter + 0 term a next b))
(define (product-iter term a next b)
        (accumulate-iter * 1 term a next b)) 


;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;;  Ex1.43
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;

(define (repeated f n)
   (lambda (x)
      (if (<= n 0)
          x
          ((repeated f (- n 1)) (f x)) ) ) )