SICP-1.2.3节练习
练习 1.14 - 1.15:
练习 1.14:
Draw the tree illustrating the process generated by the count-change procedure of section 1-2-2 in making change for 11 cents. What are the orders of growth of the space and number of steps used by this process as the amount to be changed increases?
我的解答：
一、使用 Guile 的 trace 命令
scheme@(guile-user)> ,trace (count-change 11)
trace: (count-change 11)
trace: (cc 11 5)
trace: | (cc 11 4)
trace: | | (cc 11 3)
trace: | | | (cc 11 2)
trace: | | | | (cc 11 1)
trace: | | | | | (cc 11 0)
trace: | | | | | 0
trace: | | | | | (first-denomination 1)
trace: | | | | | 1
trace: | | | | | (cc 10 1)
trace: | | | | | | (cc 10 0)
trace: | | | | | | 0
trace: | | | | | | (first-denomination 1)
trace: | | | | | | 1
trace: | | | | | | (cc 9 1)
trace: | | | | | | | (cc 9 0)
trace: | | | | | | | 0
trace: | | | | | | | (first-denomination 1)
trace: | | | | | | | 1
trace: | | | | | | | (cc 8 1)
trace: | | | | | | | | (cc 8 0)
trace: | | | | | | | | 0
trace: | | | | | | | | (first-denomination 1)
trace: | | | | | | | | 1
trace: | | | | | | | | (cc 7 1)
trace: | | | | | | | | | (cc 7 0)
trace: | | | | | | | | | 0
trace: | | | | | | | | | (# 1)
trace: | | | | | | | | | 1
trace: | | | | | | | | | (cc 6 1)
trace: | | | | | | | | | | (cc 6 0)
trace: | | | | | | | | | | 0
trace: | | | | | | | | | | (# 1)
trace: | | | | | | | | | | 1
trace: | | | | | | | | | | (cc 5 1)
trace: | | | | | | | | | | | (cc …)
trace: | | | | | | | | | | | 0
trace: | | | | | | | | | | | (# 1)
trace: | | | | | | | | | | | 1
trace: | | | | | | | | | | | (cc …)
trace: | | | | | | | | | | | | #
trace: | | | | | | | | | | | | 0
trace: | | | | | | | | | | | | #
trace: | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | 0
trace: | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | 0
trace: | | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | | 0
trace: | | | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | | | | #
trace: | | | | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | | 1
trace: | | | | | | | | | | | | 1
trace: | | | | | | | | | | | 1
trace: | | | | | | | | | | 1
trace: | | | | | | | | | 1
trace: | | | | | | | | 1
trace: | | | | | | | 1
trace: | | | | | | 1
trace: | | | | | 1
trace: | | | | 1
trace: | | | | (first-denomination 2)
trace: | | | | 5
trace: | | | | (cc 6 2)
trace: | | | | | (cc 6 1)
trace: | | | | | | (cc 6 0)
trace: | | | | | | 0
trace: | | | | | | (first-denomination 1)
trace: | | | | | | 1
trace: | | | | | | (cc 5 1)
trace: | | | | | | | (cc 5 0)
trace: | | | | | | | 0
trace: | | | | | | | (first-denomination 1)
trace: | | | | | | | 1
trace: | | | | | | | (cc 4 1)
trace: | | | | | | | | (cc 4 0)
trace: | | | | | | | | 0
trace: | | | | | | | | (first-denomination 1)
trace: | | | | | | | | 1
trace: | | | | | | | | (cc 3 1)
trace: | | | | | | | | | (cc 3 0)
trace: | | | | | | | | | 0
trace: | | | | | | | | | (# 1)
trace: | | | | | | | | | 1
trace: | | | | | | | | | (cc 2 1)
trace: | | | | | | | | | | (cc 2 0)
trace: | | | | | | | | | | 0
trace: | | | | | | | | | | (# 1)
trace: | | | | | | | | | | 1
trace: | | | | | | | | | | (cc 1 1)
trace: | | | | | | | | | | | (cc …)
trace: | | | | | | | | | | | 0
trace: | | | | | | | | | | | (# 1)
trace: | | | | | | | | | | | 1
trace: | | | | | | | | | | | (cc …)
trace: | | | | | | | | | | | 1
trace: | | | | | | | | | | 1
trace: | | | | | | | | | 1
trace: | | | | | | | | 1
trace: | | | | | | | 1
trace: | | | | | | 1
trace: | | | | | 1
trace: | | | | | (first-denomination 2)
trace: | | | | | 5
trace: | | | | | (cc 1 2)
trace: | | | | | | (cc 1 1)
trace: | | | | | | | (cc 1 0)
trace: | | | | | | | 0
trace: | | | | | | | (first-denomination 1)
trace: | | | | | | | 1
trace: | | | | | | | (cc 0 1)
trace: | | | | | | | 1
trace: | | | | | | 1
trace: | | | | | | (first-denomination 2)
trace: | | | | | | 5
trace: | | | | | | (cc -4 2)
trace: | | | | | | 0
trace: | | | | | 1
trace: | | | | 2
trace: | | | 3
trace: | | | (first-denomination 3)
trace: | | | 10
trace: | | | (cc 1 3)
trace: | | | | (cc 1 2)
trace: | | | | | (cc 1 1)
trace: | | | | | | (cc 1 0)
trace: | | | | | | 0
trace: | | | | | | (first-denomination 1)
trace: | | | | | | 1
trace: | | | | | | (cc 0 1)
trace: | | | | | | 1
trace: | | | | | 1
trace: | | | | | (first-denomination 2)
trace: | | | | | 5
trace: | | | | | (cc -4 2)
trace: | | | | | 0
trace: | | | | 1
trace: | | | | (first-denomination 3)
trace: | | | | 10
trace: | | | | (cc -9 3)
trace: | | | | 0
trace: | | | 1
trace: | | 4
trace: | | (first-denomination 4)
trace: | | 25
trace: | | (cc -14 4)
trace: | | 0
trace: | 4
trace: | (first-denomination 5)
trace: | 50
trace: | (cc -39 5)
trace: | 0
trace: 4
二、编写程序来产生调用流程：
程序：
===program start===
#!/usr/local/bin/guile -s
!#
(use-modules (ice-9 format))
(define (count-change amount)
(cc amount 5))
(define (cc amount kinds-of-coins)
(format #t "Goto (cc ~d ~d)~%" amount kinds-of-coins)
(cond ((= amount 0)
(format #t "(cc ~d ~d) => 1~%" amount kinds-of-coins)
1)
((or (< amount 0) (= kinds-of-coins 0))
(format #t "(cc ~d ~d) => 0~%" amount kinds-of-coins)
0)
(else
(+ (cc amount
(- kinds-of-coins 1))
(cc (- amount (first-denomination kinds-of-coins))
kinds-of-coins)))))
(define (first-denomination kinds-of-coins)
(cond ((= kinds-of-coins 1) 1)
((= kinds-of-coins 2) 5)
((= kinds-of-coins 3) 10)
((= kinds-of-coins 4) 25)
((= kinds-of-coins 5) 50)))
(count-change 11)
===program end===
结果：
===result start===
Goto (cc 11 5)
Goto (cc 11 4)
Goto (cc 11 3)
Goto (cc 11 2)
Goto (cc 11 1)
Goto (cc 11 0)
(cc 11 0) => 0
Goto (cc 10 1)
Goto (cc 10 0)
(cc 10 0) => 0
Goto (cc 9 1)
Goto (cc 9 0)
(cc 9 0) => 0
Goto (cc 8 1)
Goto (cc 8 0)
(cc 8 0) => 0
Goto (cc 7 1)
Goto (cc 7 0)
(cc 7 0) => 0
Goto (cc 6 1)
Goto (cc 6 0)
(cc 6 0) => 0
Goto (cc 5 1)
Goto (cc 5 0)
(cc 5 0) => 0
Goto (cc 4 1)
Goto (cc 4 0)
(cc 4 0) => 0
Goto (cc 3 1)
Goto (cc 3 0)
(cc 3 0) => 0
Goto (cc 2 1)
Goto (cc 2 0)
(cc 2 0) => 0
Goto (cc 1 1)
Goto (cc 1 0)
(cc 1 0) => 0
Goto (cc 0 1)
(cc 0 1) => 1
Goto (cc 6 2)
Goto (cc 6 1)
Goto (cc 6 0)
(cc 6 0) => 0
Goto (cc 5 1)
Goto (cc 5 0)
(cc 5 0) => 0
Goto (cc 4 1)
Goto (cc 4 0)
(cc 4 0) => 0
Goto (cc 3 1)
Goto (cc 3 0)
(cc 3 0) => 0
Goto (cc 2 1)
Goto (cc 2 0)
(cc 2 0) => 0
Goto (cc 1 1)
Goto (cc 1 0)
(cc 1 0) => 0
Goto (cc 0 1)
(cc 0 1) => 1
Goto (cc 1 2)
Goto (cc 1 1)
Goto (cc 1 0)
(cc 1 0) => 0
Goto (cc 0 1)
(cc 0 1) => 1
Goto (cc -4 2)
(cc -4 2) => 0
Goto (cc 1 3)
Goto (cc 1 2)
Goto (cc 1 1)
Goto (cc 1 0)
(cc 1 0) => 0
Goto (cc 0 1)
(cc 0 1) => 1
Goto (cc -4 2)
(cc -4 2) => 0
Goto (cc -9 3)
(cc -9 3) => 0
Goto (cc -14 4)
(cc -14 4) => 0
Goto (cc -39 5)
(cc -39 5) => 0
===result end===
最不会的就是分析复杂度了，参考网上的：
Each time procedure cc is called, it returns 1, 0 or the sum of two subtrees. Let's say, then, that each invocation of cc, that is,
each node in the evaluation tree, performs one operation.
For amount n and kinds-of-coins 5, the number of operations performed by procedure cc is 1 plus the number of operations performed
by the subtree generated by (cc n 4), plus the number of operations performed by the subtree generated by (cc (- n 50) 5). Let's
use N(n,m) to denote the number of operations performed by a subtree (cc n m). Then we have:
N(n,5) = 1 + N(n,4) + N(n − 50,5)
Let's expand the first N term by repeating this process for (cc n 4):
N(n,4) = 1 + N(n,3) + N(n − 25,4)
Keep expanding the first N term of each subtree:
N(n,3) = 1 + N(n,2) + N(n − 10,3)
N(n,2) = 1 + N(n,1) + N(n − 5,2)
N(n,1) = 1 + N(n,0) + N(n − 1,1)
(cc n 0) is a termination case: it performs only a single operation (returns 0):
N(n,0) = 1
N(n,1) = 1 + 1 + N(n − 1,1)
Let's now consider the other subtree of (cc n 1), (cc (- n 1) 1):
N(n − 1,1) = 1 + N(n − 1,0) + N(n − 2,1)
Once again, (cc (- n 1) 0) is a termination case and performs only a single operation. This process continues until the amount argument
of cc is (- n n), at which point we've fully evaluated the (cc n 1) subtree:
N(n − n,1) = 1
Working our way back up:
N(n − (n − 1),1) = 1 + 1 + 1 = 3
N(n − (n − 2),1) = 1 + 1 + N(n − (n − 1),1) = 1 + 1 + 3 = 5
N(n − (n − 3),1) = 1 + 1 + N(n − (n − 2),1) = 1 + 1 + 5 = 7
N(n − (n − 4),1) = 1 + 1 + N(n − (n − 3),1) = 1 + 1 + 7 = 9
It's easy to see that this process continues until we're back to (cc n 1):
N(n,1) = 1 + 1 + N(n − 1,1) = 2n + 1
We can verify this by drawing the graph for (cc 11 1) and counting the number of nodes. Note that the amount of storage required for
an applicative-order evaluation of the (cc n 1) subtree is also proportional to 2n + 1, since the + operations are deferred until the
value of each subtree is calculated.
When we're dealing with θ-notation orders of growth, we can ignore constant factors, so it's sufficient to say that evaluating (cc n 1)
requires order n number of steps and order n storage, since 2n + 1 is linear in n. Dropping these constant terms makes it easier to
calculate orders of growth for the other terms in the process tree.
(count-change n) generates a tree-recursive process. We know from the text that tree-recursive processes require space proportional
to the depth of the tree, and we know that (cc n 1) generates the deepest subtree of the process (since other subtrees reduce the
size of n), so we can say at this point that count-change requires space of order n (i.e., linear).
We also know from the text that tree-recursive processes require a number of operations proportional to the number of nodes in the
tree, so we have to count the remaining number of operations before we can answer the second part of the question,
i.e., count-change's order of growth of operations.
Let's go back to the root of the subtree which generated (cc n 1):
N(n,2) = 1 + N(n,1) + N(n − 5,2)
We know the value of the first N term. The 2nd N term is:
N(n − 5,2) = 1 + N(n − 5,1) + N(n − 10,2)
This expansion continues until n is <= 0, or roughly n/5 times, since each expansion of the 2nd term subtracts 5 from its amount argument.
Each one of these expansions produces an N(a 1) term, where a is the amount, and each of those terms produces 2a + 1 operations.
Subtracting a constant from n at each step doesn't change the fact that each step is a linear (order n) process, so we can
ignore the subtraction when calculating the order of growth. n times n/5 steps is n2 / 5 steps. This term overwhelms the 2n + 1
steps we calculated for the previous branch, so we can ignore the 2n + 1 term now and say that calculating (cc n 2) has order n2 / 5 steps.
Now we consider the next node up the tree, the one which generated (cc n 2):
N(n,3) = 1 + N(n,2) + N(n − 10,3)
The analysis for this step is similar to the one we performed for N(n,2): calculating (cc (- n 10) 3) produces roughly n/10 more
nodes, each of which evaluates (cc x 2). We know that evaluating (cc x 2) is order x2 / 5, so (cc n 3) is roughly n/10 times that,
n3 / 50. Again, the n3 term dominates the growth of the process, so we can ignore the lesser orders of growth of the other nodes
we've considered and say that (cc n 3) has order n3 / 50 growth.
Calculating N(n,4) and N(n,5) follows similar logic. It's then straightforward to show that the number of steps required to
evaluate (cc n 5) is θ(n^5).
练习 1.15:
The sine of an angle (specified in radians) can be computed by making use of the approximation sin xapprox x if x is sufficiently
small, and the trigonometric identity
x x
sin x = 3 sin --- - 4 sin^3 ---
3 3
to reduce the size of the argument of sin. (For purposes of this exercise an angle is considered “sufficiently small” if its magnitude
is not greater than 0.1 radians.) These ideas are incorporated in the following procedures:
(define (cube x) (* x x x))
(define (p x) (- (* 3 x) (* 4 (cube x))))
(define (sine angle)
(if (not (> (abs angle) 0.1))
angle
(p (sine (/ angle 3.0)))))
How many times is the procedure p applied when (sine 12.15) is evaluated?
What is the order of growth in space and number of steps (as a function of a) used by the process generated by the sine procedure
when (sine a) is evaluated?
我的解答：
scheme@(guile-user)> ,trace (sine 12.15) trace: (sine 12.15) trace: | (abs 12.15) trace: | 12.15 trace: | (sine 4.05) trace: | | (abs 4.05) trace: | | 4.05 trace: | | (sine 1.35) trace: | | | (abs 1.35) trace: | | | 1.35 trace: | | | (sine 0.45) trace: | | | | (abs 0.45) trace: | | | | 0.45 trace: | | | | (sine 0.15) trace: | | | | | (abs 0.15) trace: | | | | | 0.15 trace: | | | | | (sine 0.05) trace: | | | | | | (abs 0.05) trace: | | | | | | 0.05 trace: | | | | | 0.05 trace: | | | | (p 0.05) trace: | | | | | (cube 0.05) trace: | | | | | 1.25e-4 trace: | | | | 0.1495 trace: | | | (p 0.1495) trace: | | | | (cube 0.1495) trace: | | | | 0.003341362375 trace: | | | 0.4351345505 trace: | | (p 0.4351345505) trace: | | | (cube 0.4351345505) trace: | | | 0.0823892795830307 trace: | | 0.975846533167877 trace: | (p 0.975846533167877) trace: | | (cube 0.975846533167877) trace: | | 0.929275678493614 trace: | -0.789563114470823 trace: (p -0.789563114470823) trace: | (cube -0.789563114470823) trace: | -0.492221471499782 trace: -0.39980345741334 从上面可以看到，p 被调用了五次 对于空间和步数的阶应该为:R(n)=Θ(log_3^n)
评论 (0)