Structure and Interpretation of Computer Programs 1.2

1.2 Procedures and the Processes They Generate

一开始用阶乘讲解了Linear Recursion和Iteration，Linear Recursion实现阶乘的时候如下所示:
(factorial 6)
( 6 (factorial 5))
( 6 ( 5 (factorial 4)))
( 6 ( 5 ( 4 (factorial 3))))
( 6 ( 5 ( 4 ( 3 (factorial 2)))))
( 6 ( 5 ( 4 ( 3 ( 2 (factoral 1))))))
( 6 ( 5 ( 4 ( 3 ( 2 1)))))
( 6 ( 5 ( 4 ( 3 2))))
( 6 ( 5 ( 4 6)))
( 6 ( 5 24))
( 6 120)
720
但是Iteration的方式是下面这样的
(factorial 6)
(fact-iter 1 1 6)
(fact-iter 1 2 6)
(fact-iter 2 3 6)
(fact-iter 6 4 6)
(fact-iter 24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720
这里可以看出后面一种基本不要什么多余的空间消耗，但是第一种是要消耗多余的空间的，第二种貌似就是尾递归。

1.2.2讲述了树递归，用的是fibonacci数列的例子。首先给出一张图，直观的看到算fib[5]的时候需要算哪些值，而且很多都重复的算了很多次。然后给出fibonacci数列的每一项都近似于Φ^n/sqrt(5).其中，然后还把fibonacci数列的求值改了方式，变成了O(n)的。

接下来讲了一个分钱的例子。给你100块，然后你手上有50,25,10,5,1块的足够多，问你用这些面值的钱可以由多少种方式来换这100块。这个你可以选中1中钱币，然后看是否需要，如果需要，就看到底要多少个，不用的话，就只剩下其他的其中钱币了。这样就可以解决这个问题

1.2.3大致讲了函数的增长趋势，也就是传说中是算法复杂度。这个讲的比较简略，具体参看算法书籍

1.2.4讲了快速幂的想法，就是通过二进制一直求，这样得到复杂度是log_2(n)的其中n是指数。

1.25 求最大公约数，用欧几里得算法

1.26 找一个数的最小因子，费马小定理判定一个数是否是素数
习题如下:

1.9 给出a+b的两种不同实现，然后让你写具体的执行步骤，这个一步一步写就行了，最后你得到的第一种就Linear Recursion，第二种是Iteration。

1.10 给出Ackermann’s function的procedure，然后让你算几个Ackermann 值，当然你可以直接执行就可以了，也可以自己手动算，然后又几个定义：
(define (f n) (A 0 n)) (1)
(define (g n) (A 1 n)) (2)
(define (h n) (A 2 n)) (3)
(define (k n) ( 5 n n)) (4) 其中procedure A就是Ackermann’s function
这里你可以看到(1)==>2n (2)===>2^n (3)===>2^2^….^2(n次) (4)===>5n^2

1.11给一个函数定义f(n) = n if n<3 and f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3)让你写一个procedure，这个可以仿照fibonacci就行

1.12写一个求Pascal’s triangle 的第i行第j列的procedure。只要照着C[n,m]=C[n-1,m-1]+C[n-1,m]就行了，另外注意下边界

1.13 证明Fib(n) = (ⁿ - ⁿ)/5 其中 = (1 + 5)/2 = (1 - 5)/2，我们可以计算F[0],F[1],F[2]得到F[0],F[1],F[2]满足条件，然后假设对于所有的kn - ⁿ)/5可以知道F[i]可以表示成(A+B*5)/5 对所有的i都成立，那么我们可以假设F[n-2]=(A+B5)/5(其中A,B是常数)，那么我们可以得到F[n-1]=((A+5B)+(A+B)5)/2.再根据F[n]=F[n-1]+F[n-2]可以得到F[n]，和用(ⁿ - ⁿ)/5计算得到的一样，这样就得证了。也可以看这里和这里

1.14要你写出11个cents分解成其他钱币值的具体过程，这个可以看这个链接，画的很好

1.15给出，和相应的procedure，然后让你求sin x的值。问你求sin 12.15的时候，具体的步骤如何，这个一步步慢慢做就行了。另外让你求这个函数的复杂度，可以分析得到是log_3(n)的，可以类似二分那样分析，二分的时候，除以2，所以得到log_2(n)，这里除以3，所以是log_3(n)

1.16用successive squaring求a^b而且要求复杂度是log级别的。

1.17 只用+ ，double， halve写一个procedure实现ab，要求步数是log级别的。

1.18让你用1.16和1.17的相关知识，写一个procedure，来实现两个数相乘，也是用log级别的步数，我认为代码和1.17类似

1.19给出fibonacci数列的一种转移，然后让你推一个公式，这个自己认真推导下就行了，我推出的是p’=(+ ( q q) ( p q)) q’=(+ ( 2 q p) ( q q))

1.20用两种(normal-order 和applicative-order)不同的方式，要得到GCD（206,40）的具体步骤，步数有点多，具体请移步这里，只要知道normal-order和applicative-order的区别就行了，具体的问题分析起来还是比较容易的

1.21用书中给出的smallest-divisor procedure求出199，1999和19999的最小因子，这个直接求就行

1.22算procedure运行的时间，这个时间我运行的时候是不稳定的，在DrRacket里面没有runtime这个原语。我用的是time和apply-time。然后分别让你求大于100，1000,10000,100000的最小的3个素数，然后看运行时间。这个时间也不是固定的，每次都会变，而且很多时候都是0。另外，实现的时候，我自己2了好久，(+ cnt 2)是不会改变cnt的值的，一般改变一个变量的值用set!。

1.23 求最小因子的procedure中，如果2不是n的最小因子，那么所有偶数都不可能是n的因子，因此我们可以略掉所有的偶数。这里就是需要你写这样一个procedure。这里只要把每次的(+ test 1)改变成(next test)而next是一个procedure，如果test==2，那么(next test)返回3，其他的返回test+2，小于2则出错(对于这题来说)。

1.24测试费马小定理测素数所用的时间。用类似1.22中的方法

1.25我认为会溢出(以前C/C++中这样会溢出，受数据类型的限制)，不过在scheme中却不会溢出，不过是时间用的比较多一点而已。

1.26 把1.24中的procedure改了，改成(remainder (* (expmod base (/ exp 2) m) (expmod base (/ exp 2) m)) m))，也就是会算两次(expmod base (/ exp 2) m),这样的话复杂度就变成了O(n)的了

1.27 测试Carmichael数，测试所有的a<n a^n % n是否等于n。对于Carmichael数，费马小定理肯定是可以通过的，这样就Fool了费马小定理的测试。然后可以通过改变素数测试的参数，来得到最后的输出，看是否Fool了费马小定理的测试。可以围观这里

1.28素数检测的Miller-Rabin测试,要求写出相应的procedure。看以google相应的Miller-Rabin 知识，然后写出procedure。这个测试可以把Carmichael刷选出来。可以到这里围观procedure

表示这一节看了好久，继续加油。好好学习，天天向上。