这是SICP纸质笔记的整理。

你可以在这里下载到重新排版过的英文原版或者直接在线阅读点击这里购买中文纸质版(右侧)。

这里是我第一章的习题

第一章 构造过程抽象

  1. (P9) 1.1, 强有力语言提供的三种机制:

    • 基本表达形式
    • 组合的方法
    • 抽象的方法
  2. (P10-P11) 1.1.3,两种求值顺序:

    • 正则序求值:完全展开后规约

      1
      2
      3
      4
      5
      
      (square (square (+ (square 5) (square 6))))
      ;; 这里因为遇到了(square 5),所以先求值,得到25
      ;; => (square (square (+ 25 (square 6)))
      ;; => (square (square (+ 25 36)))
      ;; 只在必要时求值

    非严格求值(Non-strict Evalutaion),只在必要时才进行求值。

    • 应用序求值:先求值参数后应用:

      1
      2
      3
      4
      
      (square (square (+ (square 5) (square 6))))
      ;; 这里(+)需要两个参数才能应用,所以立即对这两个参数进行求值
      ;; => (square (square (+ 25 36)))
      ;; 应用前就求值完毕

    严格求值(Strict Evalutaion),应用前就求职完毕

    拓展阅读:维基百科

  3. (P18-P19) 1.1.8,局部变量:

    • 约束变量:一个过程的定义约束了所有变量,与名字无关,以这个过程的体为它们的作用域
    • 自由变量:非约束变量,一般可以被子作用于捕获。
  4. (补充内容) 1.1.8,作用域:

    • 动态作用域 (Dynamic Scope):Lisp采用。全局绑定栈,当我们在局部过程定义一个变量时,它的绑定会被推入全局栈,离开时栈顶弹栈,无论何时使用该变量时我们总是使用栈顶绑定。
    • 词法作用域 (Lexical Scope):Scheme采用。局部环境,即无论何时定义一个变量,我们总在局部环境绑定中操作,使用时也在局部环境寻找。

    拓展阅读:维基百科

  5. (P23) 1.2.1,计算过程(Process)与过程(Procedure):

    • 过程:语法上的形式。如递归过程:在定义中直接或间接调用自己的过程。

    例:

    1
    2
    3
    4
    
      (define (fib n)
        (cond ((= n 0) 0)
              ((= n 1) 1)
              (else (+ (fib (- n 1)) (+ (fib (- n 2)))))))

    这一过程直接调用了自己,是一个递归过程(Recursive procedure)。

    • 计算过程:这一过程的进展形式。例如迭代计算过程:可能是以递归为形式,但是进展上是一种迭代的方式。

    例:

    1
    2
    3
    4
    5
    6
    
      (define (fib n)
        (define (iter count a b)
          (if (= count n)
              b
              (iter (+ count 1) b (+ a b))))
        (iter 0 1 0))

    这一过程虽然是一个递归过程,但是在进展上,是迭代的进展方式,所以这是一个迭代计算过程(Iterate process)。

    辨析:*过程*指的是语法本身的含义,而*计算过程*指的是所描述的计算过程。

  6. (P23) 1.2.1,尾递归:

    尾递归可以在$O(1)$空间内执行迭代计算过程,即使这一计算使用的是递归过程描述的。

  7. (Ex 1.13) 证明$Fib(n)$为最接近$\frac{\phi^n}{\sqrt{5}}$的整数,其中$\phi=\frac{1+\sqrt{5}}{2}$。

    证:若要证明$Fib(n)$为最接近$\frac{\phi^n}{\sqrt{5}}$的整数,可以证明$|Fib(n)-\frac{\phi^n}{\sqrt{5}}|<\frac{1}{2}$

    若证上式,可证$Fib(n)=\frac{\phi^n-\psi^n}{\sqrt{5}}$,其中$\psi=\frac{1-\sqrt{5}}{2}$。

    使用归纳法证明上式:$Fib(0)=\frac{\phi^0-\psi^0}{\sqrt{5}}=0$,成立;$Fib(1)=\frac{\phi^1-\psi^1}{\sqrt{5}}=\frac{\sqrt{5}}{\sqrt{5}}=1$,成立。

    假设$Fib(n-1)=\frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}$与$Fib(n-2)=\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt{5}}$成立,

    由定义,

    $$ \begin{aligned} Fib(n) &= Fib(n-1)+Fib(n-2)
    &= \frac{\phi^{n-1}-\psi^{n-1}}{\sqrt{5}}+\frac{\phi^{n-2}-\psi^{n-2}}{\sqrt{5}}
    &= \frac{\phi^n(\phi^{-2}+\phi^{-1})+\psi^n(\psi^{-2}+\psi^{-1})}{\sqrt{5}} \end{aligned} $$

    由于$\phi^{-2}+\phi^{-1}=\frac{3-\sqrt{5}}{2}+\frac{\sqrt{5}-1}{2}=1$,$\psi^{-2}+\psi^{-1}=\frac{3+\sqrt{5}}{2}-\frac{\sqrt{5}+1}{2}=1$,

    立即可得$Fib(n)=\frac{\phi^n+\psi^n}{\sqrt{5}}$,得证。

    那么立即有$Fib(n)-\frac{\phi^n}{\sqrt{5}}=-\frac{\psi^n}{\sqrt{5}}$。

    又由$|\frac{1}{\sqrt{5}}|<1, |\psi^n|<\frac{1}{2}$,可得$|\frac{\psi^n}{\sqrt{5}}|<\frac{1}{2}$,也就是$|Fib(n)-\frac{\phi^n}{\sqrt{5}}|<\frac{1}{2}$,$\mathtt{Q.E.D.}$

  8. (P28) 1.2.3,增长阶(渐进紧确界):

    令$n$为可度量问题规模的参数,$R(n)$为计算$n$规模问题时所需的资源,我们称$R(n)$具有$\Theta(f(n))$的增长阶,记为$R(n)=\Theta(f(n))$,满足: $$ \forall n, \exists k_1,k_2\in\mathbb{Z}, k_1f(n)\le R(n)\le k_2(f(n)) $$ 其中$k_1,k_2$为与$n$无关的参量。

    拓展阅读:算法复杂度的记号表示法,《算法导论》。

    增长阶计算练习

    1. Ex 1.14,把$n$元换成$k$枚硬币:

    首先考虑(cc n 1)的情况,在这种情况下,每一个$n$都会带来以下两种展开:(cc (- n 1) 1)(cc n 0),也就是说,这样情况下总共会有$2n+1$个节点,时间复杂度自然为$O(n)$。由于$n$每增长$1$,这棵树的层数就增加$1$,所以空间复杂度为$O(n)$。

    接下来考虑(cc n 2),这样的情况会展开为(cc (- n 5) 2)(cc n 1),根据上述讨论得知(cc n 1)复杂度为$O(n)$,而这棵树一共有$\frac{n}{5}$棵这样的子树,所以总共复杂度为$O(n^2)$。空间复杂度不变,仍然是$n$每增长$1$多一层调用。

    那么根据如上考虑,(cc n k)总计的时间复杂度就为$O(n^k)$,空间复杂度为$O(n)$。

    1. Ex 1.15,计算三角恒等式复杂度。

    计算的核心代码为:(p (sine (/ angle 3.0))),也就是说,对于每一个数,求得答案时,假如p调用了$n$次,那么一定满足$a\le 0.1\cdot 3^n$,对两边取对数,有$\log{a}\le \log{0.1}+n\log{3}$,也就是说,$n$和$\log{a}$正相关。那么算法的时间复杂度和空间复杂度都为$O(\log{a})$。

  9. (P35) 概率算法:

    在满足条件的情况下,有一定概率能保证解的正确性的算法,如费马素数检测。

  10. (P35-P36) Ex 1.22~1.24,算法复杂度的讨论:

    算法复杂度是用于衡量增长率的工具,而不是描述实际增长率的工具。

    运算时间一般受以下因子影响:

    • 运算环境:如瞬时I/O速度,CPU调度等
    • 常数因子,如$O(kn)=O(n)$,此时$k$为常数因子,那么$O(2n)=O(n)=O(3n)$的两个算法速度并不一样。

    等等。

    我们使用算法复杂度来衡量增长速度,尤其是数据量比较大的情况下。

  11. (P37) Ex 1.28,Miller-Rabin算法:

    实现参照:1.28.scm

    理论依据:费马小定理,若$n$为质数,那么$\forall a<n,a\in \mathbb{N}, a^{n-1}\equiv1\pmod n$,取$a$检查即可。

    Miller-Rabin算法中会遇上$1$取模$n$的非平凡平方根,即:$\exists b\in\mathbb{N}, 1<b<n-1, b^2\mod n=1$。这样的数表示$n$不为素数。证明也很简单,考虑: $$ (x^2-1)\mod n=0\implies(x+1)(x-1)\mod n =0 $$

    也就是说,假如$x$为非$2$的质数,上面的式子一定不成立(因为此时只会有$\pm1$两个解)。

    在Miller-Rabin算法运行过程中,我们大概有$50\%$的几率遇上这样的数,所以测试总计$\frac{n}{2}$次可以保证准确性。在实际使用中,一般取8次即可,大约$\frac{1}{2}^8\approx0.3\%$的几率会遇到例外。

  12. (P37) 1.3,高阶过程:以过程为参数,或者以过程为返回值的过程。

  13. (P37) 1.3.1,求和记法:$\sum^b_{n=a}f(n)=f(a)+\cdots+f(b)$。

  14. (P45-P46) 1.3.3,不动点:若$x$满足$f(x)=x$,则称$x$为$f(x)$的不动点。

    用途:求方程$x=f(x)$的解,如可利用不动点求平方根:$y=x^2\implies x=y/x$,也就是求$f(x)=y/x$的不动点。

  15. (P51) 1.3.4,第一级过程(First-class procedure):

    第一级过程有如下特点:

    • 可以用变量命名
    • 可以由过程作为结果返回
    • 可以提供给过程作为参数
    • 可以包含在数据结构中

    等等。这一要求给实现增加了难度。

    一般的第一级对象有:字面量,变量等。

  16. (P51) Ex 1.41:分析过程(((double (double double)) inc) 5)

    上述过程返回值为21

    重点在于分析(double (double double))部分。首先分析内部的(double double),得到(double (double f)),也就是$4$次调用f。接下来我们对这个过程取别名,例如(define (g f) ((double double) f)),那么上述过程可以重写为(double g),这里展开即得到(g (g f)),那么内部首先是调用$4$次f,外部再对这个新的函数调用$4$次,总计调用了$4\times4=16$次。

    上述过程即$5+16=21$。