Lisp 程式設計 (1042)

課本全文
How to run your programs?
exercise 1: exercising the scheme48 interpreter
- Practice the code examples in 1.1.
- Write your comment about this course in a file.
- The file should be put under ~/scheme-1042/exer1
- Deadline: 2016/Mar/02 00:05 AM.

exercise 2: find the median of the three numbers

Write a function which will return the median of the three arguments

      $ scheme48
      > ,load exer2.scm
      > (median 1 2 3)
      2
      > (median 3 1 2)
      2
      > (median 1 3 3)
      3
      > (median 2 2 2)
      2
      > (median 1 1 4)
      1
      > (median 2 1 3)
      2
      > ,exit
      $

Your program should be put under ~/scheme-1042/exer2
Deadline: 2016/Mar/09 00:05 AM.

exercise 3: calculate the sum of an arithmetic sequence
- Write a function, (sum a b step), which will return the sum of the arithmetic sequence: a, a+step, a+2*step, .......
```
      $ scheme48
      > ,load exer3.scm
      > 
      > (sum 1 10 1)
      55
      > (sum 1 10 2)
      25
      > (sum 1 100 1)
      5050
      > (sum 11 20 9)
      31
      > (sum 21 10 2)
      0
      > ,exit
      $ 
      
```
- For your convenience, the step is a positive number.
- When a is greater than b, the sum is zero.
- Your program should be put under ~/scheme-1042/exer3
- Deadline: 2016/Mar/16 00:05 AM.
exercise 4: find the solution of a formula.
- Write a function, (solve x), which will return y such that y^2 + y = x.
- The idea is like sqrt, but you have to design a new `improve' procedure.
- The good-enough? procedure should adopt the idea of exercise 1.7.
- Your program should be put under ~/scheme-1042/exer4
- Deadline: 2016/Mar/23 00:05 AM.
exercise 5: recursive and linear iterative
- Refer to exercise 1.11 but the formula is changed to
  f(n) = f(n-1) - 2*f(n-2) + 3*f(n-3)
- Note that you have to write two procedures. One is written in recursive way and another in linear iterative way.
- Your program should be put under ~/scheme-1042/exer5
- Deadline: 2016/Mar/30 00:05 AM.
exercise 6: fast exponentiation
- You have to write two procedures. One is the linear-iterative fast exponentiation as specified in exercise 1.16. Another is linear-recursive fast exponentiation which is like the one in text but uses ``cube'' instead of ``square''.
- Your program should be put under ~/scheme-1042/exer6
- Deadline: 2016/Apr/06 00:05 AM.
exercise 7: linear-iterative expmod
- Write a linear-iteraitve expmod.
- Your program should be put under ~/scheme-1042/exer7
- Deadline: 2016/Apr/13 00:05 AM.
exercise 8: generalizing fast-expt
- Deadline: 2016 Apr 27 00:05 am
- Put your file(s) under ~/scheme-1042/exer8
exercise 9: 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" can be implemented in either linear-recurse or linear iterative way. Only one version is required.
- 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 ex9.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
       $ 
      
```
- Deadline: 2016 May 11 00:05 am
- Put your file(s) under ~/scheme-1042/exer9
exercise 10: iterative improve
- Refer to exercise 1.46.
- First you have to write a procedure, (iterative-improve ok? improve), which accepts two arguments. First argument is a procedure used to test if the current guess is good enough. Second argument is also a procedure used to improve the current guess. That is, both arguments are like (lambda (x) .....).
- After "iterative-improve" is written, you have to use it to rewrite "sqrt" and "fixed-point".
- The return value of "iterative-improve" is a procedure which when invoked with an initial guess will return the approximated answer. That is, the usage is like:
  ((iterative-improve your-ok? your-improve) guess).
- Deadline: 2016 May 19 00:05 am
- Put your file(s) under ~/scheme-1042/exer10

exercise 11: manipulating vectors

Refer to chap 2.1.1.
You have to write 4 interface procedures: (make-vec a b c), (first v), (second v), and (third v).

Based on the above procedures, write (add-vec v1 v2), (sub-vec v1 v2), (mul-vec a v), (inner-prod v1 v2), and (print-vec v).
For example, (ignore #{Unspecific})

        $ scheme48
        > ,load ex11.scm
        > (define a (make-vec 3.5 2.9 0.9))
        ; no values returned
        > (define b (make-vec 1.9 2.3 4.5))
        ; no values returned
        > (inner-prod a b)
        17.369999999999997
        > (print-vec (add-vec a b))
        
        (5.4 5.199999999999999 5.4)#{Unspecific}
        > (print-vec (mul-vec 2.0 b))
        
        (3.8 4.6 9.0)#{Unspecific}
        > (print-vec (sub-vec a b))

        (1.6 0.6000000000000001 -3.6)#{Unspecific}
        > ,exit
        $

Deadline: 2016 May 26 00:05 am
Put your file(s) under ~/scheme-1042/exer11

exercise 12: handling variable number of arguments
- Refer to exercise 2.20.
- You have to write a procedure, (same-ret-value f a b1 b2 b3 ....), which takes at least two arguments. The procedure will compute (f b1), (f b2), ... and check if the value is equal to (f a). The final return value is a list which contains 'a', and the remaining b's which (f b) is the same as (f a). For example,
```
        $ scheme48
        > ,load ex12.scm
        > 
        > (same-ret-value (lambda (x) (remainder x 2)) 8 9 7 6 5 4 3)
        (8 6 4)
        > (same-ret-value (lambda (x) (remainder x 3)) 1 2 3 4 5 6 7 8 9 10)
        (1 4 7 10)
        > ,exit
        $ 
      
```
- Deadline: 2016 June 01 00:05 am
- Put your file(s) under ~/scheme-1042/exer12
exercise 13: practicing sequence interface
- Write a procedure (prod-relative-prime n) which will first compute the product of numbers which are less than n and relative prime to n, and then compute the remainder of product by n. For example
```
 
        $ scheme48
        > ,load ex13.scm
        > (prod-relative-prime 12)
        1
        > (prod-relative-prime 13)
        12
        > (prod-relative-prime 60)
        1
        > (prod-relative-prime 59)
        58
        > ,exit
        $ 
      
```
- Compose your program with "enumerate-interval", "accumulate", and "filter".
- Deadline: 2016 June 08 00:05 am
- Put your file(s) under ~/scheme-1042/exer13