LISP Programming 1062_ex9

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 9: enumerating tuples
•Define a procedure, (enum-tuples list-1 list-2 .... list-k) which will
generate a list of k-tuples. The tuples contains all combinations of
elements from each list.

$ scheme48
> ,load ex9-enum-tuples.scm
> 
> (enum-tuples)
()
> (enum-tuples '(x y z))
((x) (y) (z))
> (enum-tuples '(a b c) '(hello world))
((a hello) (b hello) (c hello) (a world) (b world) (c world))
> (enum-tuples '(1 2) '(h i j k))
((1 h) (2 h) (1 i) (2 i) (1 j) (2 j) (1 k) (2 k))
> (enum-tuples '(hello ohio) '(101 39 11) '(good fine))  
((hello 101 good) (ohio 101 good) (hello 39 good) (ohio 39 good)
(hello 11 good) (ohio 11 good) (hello 101 fine) (ohio 101 fine)
(hello 39 fine) (ohio 39 fine) (hello 11 fine) (ohio 11 fine))
> ,exit
$

解答:

;exer9 enumerating tuples
(define proc-list
    (lambda (lst f)
        (cond
            ((null? lst) '())
            (else
            (append (f (car lst)) (proc-list (cdr lst) f)))))
) ;proc-list END
(define combine
  (lambda (list1 list2)
    (proc-list list1 (lambda (x)
                     (map (lambda (y) (list x y)) list2))))
) ;combine END
(define enum-tuples
  (lambda (x-lst . y-lst*)
    (cond
      ((null? y-lst*) (map list x-lst)) ;case1: (enum-tuples '(x y z))
      ((null? (cdr y-lst*)) (combine x-lst (car y-lst*)))
      (else
          (proc-list x-lst (lambda (x)
                           (map (lambda (y) (cons x y))
                                (apply enum-tuples y-lst*)))))))
) ;enum-tuples END

執行結果：

LISP Programming 1062_ex8

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 8: enumerate a tree with sequence interface
•Rewrite (enum-tree T) with accumulate and map.

解答:

;enumerate tree
(define (enumerate-tree tree)
  (cond ((null? tree) '())
        ((not (pair? tree))
              (list tree))
        (else (append (enumerate-tree (car tree))
                      (enumerate-tree (cdr tree))))))
;use map list a tree to see ex2.30
;(1) map a tree
(define (lst x) (append x))
(define (map-tree t)
    (enumerate-tree
        (map (lambda (sub-tree)
             (if (pair? sub-tree)
                 (map-tree sub-tree)
                 (lst sub-tree)))
                t)))
(define nil '())

;p78 accumulate.scm
(define (accumulate op initial sequence)
    (if (null? sequence)
        initial
        (op (car sequence)
            (accumulate op initial (cdr sequence))))
)
;(2) accumulate a tree
(define (enum-tree t )
   (accumulate cons
               (list)         ;empty list
               (map-tree t)))

執行結果：

LISP Programming 1062_ex7

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 7: mapping over trees
•Refer to exercise 2.31.

解答:

(define l (list 1 (list 2 3 (list 4 5))))

(define (sq x) (* x x))

(define (tree-map f tree)
  (cond ((null? tree)
          '())
        ((not (pair? tree))
          (f tree))
        (else
          (cons (tree-map f (car tree))
                (tree-map f (cdr tree))))))

執行結果：

LISP Programming 1062_ex6

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 6: representing a pair with a number
•Refer to exercise 2.5.
•Note the requirement of nonnegative is removed. Your method 
should accept two integers.

解答:

(define (num-cons a b)
    (* (expt 2 a) (expt 3 b)))

(define (num-car n)
  (if (= 0 (modulo n 2))
      (+ 1 (num-car (/ n 2)))
      0))

(define (num-cdr n)
  (if (= 0 (modulo n 3))
      (+ 1 (num-cdr (/ n 3)))
      0))

執行結果： 

LISP Programming 1062_ex5

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 5: calculating continued-fraction
•Refer to exercise 1.37.(參考這篇：黃金分割)
•You have to write two procedures. One is (cont-frac n d k) and another is (pi epsilon).
•The "cont-frac" should be implemented in linear iterative way.
•To calculate pi, the sequence N_i is: 4, 1^2, 2^2, 3^2, ...
 and the sequence D_i is: 1, 3, 5, 7, ...
•To approximate pi, calculate (cont-frac n d 1), (cont-fract n d 2), .. until two consecutive values
 are  close enough, that is, the distance between them is less than epsilon.

$ scheme48
> ,load ex5.scm
> (cont-frac (lambda (i) 1.0) (lambda (i) 1.0) 100)
0.6180339887498948
> (pi 0.001)
3.141463414634146
> (pi 0.0001)
3.1415888250921244
> (pi 0.0000000000001)
3.141592653589791
> ,exit
$
解答說明請參考：【Scheme】連分法求pi

解答:

;continued fraction calc pi
(define (cont-frac n d k)
   (define (frac-iter i result)
       (if (= i 0)
           result
           (frac-iter (- i 1.0) (/ (n i) (+ (d i) result)))))
   (frac-iter (- k 1.0) (/ (n k) (d k))))
(define (calc-pi k)
    (define (d i)
        (- (* 2 i) 1))
    (define (n i)
        (if (= i 1)
            4
            (* (- i 1) (- i 1))))
    (cont-frac n d k))
(define (calc-enough index accuracy)
    (define next_i index) ;next_i=index
    (if (< (abs (- (calc-pi index) (calc-pi (+ next_i 1)))) accuracy)
        (calc-pi (+ next_i 1))               ;true
        (calc-enough (+ index 1) accuracy))) ;false
(define (pi accuracy)
    (calc-enough 1 accuracy))

執行結果：

【Scheme】連分法求Pi

題目要求:
•Refer to exercise 1.37.
•You have to write two procedures. One is (cont-frac n d k) and another is (pi epsilon).
•The "cont-frac" should be implemented in linear iterative way.
•To calculate pi, the sequence N_i is: 4, 1^2, 2^2, 3^2, ...
 and the sequence D_i is: 1, 3, 5, 7, ...
•To approximate pi, calculate (cont-frac n d 1), (cont-fract n d 2), .. until two consecutive values
 are  close enough, that is, the distance between them is less than epsilon.

參考SICP ex 1.37，寫兩個程序
1.  (cont-frac n d k) and (pi epsilon)
2. "cont-frac" 使用迭代法
3. 計算 Pi，序列N_i 是4，1^2，2^2，3^2 . . .D_i是 1，3，5，7 . . .
4. 近似求Pi，直到(cont-frac n d 1), (cont-fract n d 2)值小於精確值

首先 π 的連分公式如下:

其中4,1,4,9,16就是N_i 項; 而 1,3,5,7,9就是Ｄ_i項,
參考上一篇的(cont-frac)，迭代法程式:

(define (cont-frac-iter n d k)
   (define (frac-iter i result)
       (if (= i 0)
           result
           (frac-iter (- i 1) (/ (n i) (+ (d i) result)))))
   (frac-iter (- k 1) (/ (n k) (d k))))

接著解釋 n項 與 d項:
這裡要注意的是 
d項就是迭代 i值的(2*i-1)，例如第一項是(2*1-1)=1，第二項是(2*2-1)=3 . . .依此類推
而n項就是 迭代 i值的平方(i^2)，但要注意第一項是4，第二項是((2-1)^2)，第三項是((3-1)^2) . . .

(define (calc-pi k)
    (define (d i)
        (- (* 2 i) 1)) ;((2*i)-1)
    (define (n i)
        (if (= i 1)
            4
            (* (- i 1) (- i 1))))
    (cont-frac n d k))

這樣就可以求Pi，例如(calc-pi 10)，求出聯分法10項的Pi值: 
(calc-pi 10)
3.14159254044654 
(calc-pi 20)
3.14159265358979
用這種方式求Pi因為收斂很快所以不會花費太多時間。

接著要給精確值求出Pi，就是用迭代法每一次求出的Pi值與下一個項次比較，直到小於精確值為止
如:
(calc-pi 5)-(calc 6) < accuracy ?
如果是則停止
如果不是則(calc-pi 6)-(calc-pi 7)

(define (inc x)
    (+ x 1))
(define (enough-pi index accuracy)
    (define next_i index) ;next_i=index
    (if (< (abs (- (calc-pi index) (calc-pi (inc next_i)))) accuracy)
        (calc-pi (inc next_i))            ;true
        (enough-pi (inc index) accuracy)) ;false
)
(define (pi accuracy)
    (enough-pi 1 accuracy))

輸入與結果:
(pi 0.001)
3.14146341463415
(pi 0.0001)
3.14158882509212
(pi 0.0000000000001)
3.14159265358979
如果將各項的輸出印出

index:5 next_i:5 err:0.001
3.14146341463415
在第5項的時候收斂到0.001

index:7 next_i:7 err:0.0001
3.14158882509212
在第7項的時候收斂到0.0001

index:19 next_i:19 err:1e-13
3.14159265358979
在第19項的時候收斂到0.0000000000001


參考:
1.維基百科圓周率
2. SICP Ex 1.37

LISP Programming 1062_ex3

http://erdos.csie.ncnu.edu.tw/~klim/scheme/lisp-1062.html

exercise 3: linear recursive and linear iterative
Refer to exercise 1.11 but the formula is changed to
  f(n) = n if n < 3
  f(n) = 2*f(n-1) + f(n-2) + f(n-3) if n ≥ 3 and n is even
  f(n) = 2*f(n-1) - f(n-2) + f(n-3) if n ≥ 3 and n is odd
Note that you have to write two procedures. One is written
in recursive way and another in linear iterative way.

解答:

;f by means of a recursive process
(define (f-res n)
    (if (< n 3)
        n  ; n<3 , f(n)=n
        (if (odd? n)
            (+ (- (* 2 (f-res (- n 1))) 
               (f-res (- n 2))) 
            (f-res (- n 3))) ; n is odd
            
            (+ (+ (* 2 (f-res (- n 1))) 
               (f-res (- n 2))) 
            (f-res (- n 3)))))) ; n is even
(define (f n)
    (f-res n))

執行結果：


 

LISP Programming 1062_ex2

exercise 2: improving the good-enough?
Refer to exercise 1.7

解答:
;exercise 2: improving the good-enough?
(define (average x y)
    (/ (+ x y) 2))
(define (improve guess x)
    (average guess (/ x guess))
)
(define (good-enough? old-guess new-guess)
    ;(> 0.01 (/ (abs (- new-guess old-guess)) old-guess))
    (< (/ (abs (- new-guess old-guess)) old-guess) 0.01)
)
(define (sqrt-iter guess x)
    (if (good-enough? guess (improve guess x))  ;調用新的good-enough?
        (improve guess x)
        (sqrt-iter (improve guess x) x)
    )
)
(define (sqrt x)
    (sqrt-iter 1.0 x))

執行結果：

LISP Programming 1062_ex1

exercise 1: figure out the sum of squares of the minimum two arguments
Write a procedure named 'sum-of-square-min-two' which accepts three  
arguments and will figure out the sum of squares of the minimum two
arguments. 

$ scheme48
> ,load ex1-sum-square-min-two.scm
> 
> (sum-of-square-min-two 1 2 3)
5
> (sum-of-square-min-two 1 2 -3)
10
> (sum-of-square-min-two 2 2 2)
8
> ,exit
$

解答:
;figure out the sum of squares of the minimum two arguments 
(define (square x)
      (* x x))
(define (min-two-square a b c)
    (if (<= a b)
        (if (<= b c)
            (list (square a) (square b))
            (list (square a) (square c)))
        (if (<= a c )
            (list (square b) (square a))
            (list (square b) (square c)))))
(define (sum-data x y)
    (+ x y))
(define (sum-of-square-min-two a b c)
    (apply sum-data (min-two-square a b c)))

執行結果：