SICP-1.3.2节练习
SICP-1.3.4节练习

SICP-1.3.3节练习

lispor posted @ Feb 23, 2011 12:20:55 PM in Scheme with tags SICP , 1558 阅读

练习 1.35 - 1.39

 
练习 1.35:
Show that the golden ratio [phi] (section 1-2-2) is a fixed point of the transformation x |-> 1 +
1/x, and use this fact to compute [phi] by means of the fixed-point procedure.
我的解答:
将 [phi] 值带入方程 x = 1 + 1/x, 等式成立。
用 fix-point 函数计算 [phi] 值:
scheme@(guile-user)> (fixed-point (lambda (y) (+ 1 (/ 1.0 y))) 1.0)
1.61803278688525
 
练习 1.36:
Modify fixed-point so that it prints the sequence of approximations it generates, using the newline
and display primitives shown in Exercise 1-22. Then find a solution to x^x = 1000 by finding a fixed
point of x |-> log(1000)/log(x). (Use Scheme's primitive log procedure, which computes natural
logarithms.) Compare the number of steps this takes with and without average damping. (Note that you
cannot start fixed-point with a guess of 1, as this would cause division by log(1) = 0.)
我的解答:
修改程序:
(define (fixed-point f first-guess)
  (define (close-enough? x y)
    (< (abs (- x y)) tolerance))
  (define (try guess)
    (let ((next (f guess)))
      (cond ((close-enough? guess next)
             next)
            (else
             (display next)
             (newline)
             (try next)))))
  (try first-guess))

运行结果:
scheme@(guile-user)> (fixed-point (lambda (y) (/ (log 1000) (log y))) 2.0)
9.96578428466209
3.00447220984121
6.27919575750716
3.75985070240154
5.2158437849259
4.1822071924014
4.82776509834459
4.38759338466268
4.6712500857639
4.48140361689505
4.6053657460929
4.52308496787189
4.57711468204734
4.54138248015145
4.56490324523083
4.54937267930334
4.55960649191329
4.55285387578827
4.55730552974826
4.55436906443618
4.556305311533
4.55502826357355
4.55587039670285
4.55531500119208
4.55568126354333
4.55543971573685
4.55559900999829
4.55549395753139
4.55556323729288
4.55551754841765
4.5555476793064
4.55552780851625
4.55554091291796
4.55553227080365
 
练习 1.37::
An infinite continued fraction is an expression of the form
           N_1
f = ---------------------
               N_2
    D_1 + ---------------
                   N_3
          D_2 + ---------
                D_3 + ...
As an example, one can show that the infinite continued fraction expansion with the n_i and the D_i
all equal to 1 produces 1/[phi], where [phi] is the golden ratio (described in section 1-2-2). One
way to approximate an infinite continued fraction is to truncate the expansion after a given number
of terms. Such a truncation—a so-called finite continued fraction k-term finite continued
fraction—has the form
       N_1
-----------------
          N_2
D_1 + -----------
      ...    N_K
          + -----
             D_K
Suppose that n and d are procedures of one argument (the term index i) that return the n_i and D_i
of the terms of the continued fraction. Define a procedure cont-frac such that evaluating (cont-frac
n d k) computes the value of the k-term finite continued fraction. Check your procedure by
approximating 1/[phi] using
(cont-frac (lambda (i) 1.0)
           (lambda (i) 1.0)
           k)
for successive values of k. How large must you make k in order to get an approximation that is
accurate to 4 decimal places?

If your cont-frac procedure generates a recursive process, write one that generates an iterative
process. If it generates an iterative process, write one that generates a recursive process.
 
我的解答:
a.<递归计算过程>
(define (cont-frac n d k)
  (define (iter i)
    (if (> i k)
        0
        (/ (n i)
           (+ (d i)
              (iter (+ i 1))))))
  (iter 1))

(define (count-k)
  (define  value-of-1/phi (/ 2.0 (+ 1 (sqrt 5))))
  (define (close-enough? x)
    (< (abs (- x value-of-1/phi)) 0.0001))
  (define (iter i)
    (if (close-enough? (cont-frac (lambda (i) 1.0)
                                  (lambda (i) 1.0)
                                  i))
        i
        (iter (+ i 1))))
  (iter 1))
运行结果:
scheme@(guile-user)> (count-k)
10

b.<迭代计算过程>
(define (cont-frac n d k)
  (define (iter i result)
    (if (= i 0)
        result
        (iter (- i 1)
              (/ (n i)
                 (+ (d i)
                    result)))))
    (iter k 0))
 
练习 1.38:
In 1737, the Swiss mathematician Leonhard Euler published a memoir De Fractionibus Continuis, which
included a continued fraction expansion for e - 2, where e is the base of the natural logarithms. In
this fraction, the n_i are all 1, and the D_i are successively 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8,
.... Write a program that uses your cont-frac procedure from Exercise 1-37 to approximate e, based
on Euler's expansion.
我的解答:
scheme@(guile-user)> (+ 2 (cont-frac (lambda (x) 1.0)
                                     (lambda (x) (if (= 2 (remainder x 3))
                                                     (* 2/3 (+ x 1))
                                                     1))
                                     100))
2.71828182845905
 
练习 1.39:
A continued fraction representation of the tangent function was published in 1770 by the German
mathematician J.H. Lambert:
                   x
tan x = ---------------
                x^2
        1 - -----------
                  x^2
            3 - -------
                5 - ...
where x is in radians. Define a procedure (tan-cf x k) that computes an approximation to the tangent
function based on Lambert's formula. K specifies the number of terms to compute, as in Exercise
1-37.
我的解答:
运行结果:
scheme@(guile-user)> (tan-cf 4 100)
5252071305022827679633892945355329000458775586554386376350796675515098676387084502784995236575995603
193471321746645790060683539341155042217553047538969423238486906032306673915891553895900/453616752869
2122622641176628273895210907169900405520519486694334700539204832950653748200748042845804482536605950
409820103108395215140024455079993196604417727792577095226749156626924652199
scheme@(guile-user)> (rationalize (tan-cf 4 100) 0.00001)
1.15782122905028
scheme@(guile-user)> (tan 4)
1.1578212823495

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter