SICP-1.3.3节练习
练习 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
评论 (0)