Skip to content

SICP习题解答:第一章(上)


Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304

Warning: preg_replace_callback(): Unknown modifier 'c' in /home/tianyicui/cuitianyi.com/wp-content/plugins/wp-codebox/geshi/geshi.php on line 3304
?View Code SCHEME
;; 1.1-2 略
;; 1.3
; 或
;; 1.4 (if (> b 0) + -) 根据b的正负性返回函数+或-。
;; 1.5 函数p的定义 (define (p) (p)) 是不断递归调用自己,所以欲对其进行求值/展开会产生死循环。调用 (test 0 (p)) 时,若采用应用序求值,会先对函数的参数,包括 (p) 求值,因而产生死循环,无法输出结果;若采用正则序求值,则由于 (p) 的值事实上不会被展开,故会正常返回0。
;; 1.6 将在调用函数 new-if 时,应用序要求先算出其所有参数的值,new-if 的后两个参数——代表 if 的两个分支的代码都将被执行。所以 (sqrt-iter guess x) 必然需要调用 (sqrt-iter (improve guess x) x),这导致死循环。
;; 1.7
;; 1.8
;; 1.9 第一个过程是递归的,表达式被递归地逐渐展开再合并;第二个过程中的递归是尾递归,不妨理解为迭代的。
;; 1.10 (f n)是n的2倍,(g n)是2的n次方,(h n)是2的(h (- n 1))次方。
;; 1.11
; 递归方式
; 迭代方式
;; 1.12
;; 1.13 可利用归纳法和定义直接证。
;; 1.14 空间复杂度为 O(amount),因为任何时刻调用链的长度(栈上的函数数量)不超过 amount+1;时间复杂度为 O(amount * result),因为每得到一种方案都调用一次 (cc 0 kinds-of-coins)。
;; 1.15 空间与时间复杂度均为O(log a)。
;; 1.16 prod*a^m是不变量。
;; 1.17
;; 1.18
;; 1.19 p’ = pp + qq,q’ = qq + 2pq。
;; 1.20 应用序需要4次;正则序需要更多,没仔细数,因为gcd函数体中出现了三处b,当b是调用remainder的形式时,它需要被展开若干次。
;; 1.21 略。
;; 1.22-24 我用的DrScheme没有定义runtime……555
;; 1.25 如果不在计算乘幂时随时取模,每次乘法将由于被乘数位数的迅速增长而不能被看做单位时间的原子操作。
;; 1.26 每次(expmod base exp m)当exp为正偶数时会调用两次而非一次(expmod base exp m),f(N)=2*f(N/2)+Θ(1)导致f(N)=Θ(N),而原始版本的f(N)=f(N/2)+Θ(1)导致f(N)=Θ(log N)。
;; 1.27 以下程序中,(find-carmichael n)找出不超过n的Carmichael数
"\n";; 1.28
 

5 Comments

  1. SGi wrote:

    WP里面不是有个很好用的代码插件么..WP-Codebox用Geshi做的..效果不错..支持的语言高亮大概上60种了..

    Wednesday, November 26, 2008 at 23:43 | Permalink
  2. mces89 wrote:

    1.7运行不了,提示是reference to an identifier before its definition: cube-root,我自己写了个也是类似的错误提示,大牛帮忙看看

    Sunday, December 7, 2008 at 12:28 | Permalink
  3. Karl wrote:

    1.3的第二个程序有个小bug,比如输入为1,1,2的时候程序结果不对
    DrScheme有个current-milliseconds可以代替runtime的

    Thursday, January 1, 2009 at 14:44 | Permalink
  4. Karl wrote:

    哦,貌似millisecond精度不够……

    Thursday, January 1, 2009 at 14:54 | Permalink
  5. XeCycle wrote:

    没有看到上面的说明还以为是lisp呢,看来远离编程一段时间很快就落伍了。比赛完毕了,总有这苦恼。

    Tuesday, January 6, 2009 at 12:31 | Permalink

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*