SICP学习笔记02 vvipi 发表于2018年11月3日,阅读：1468 # 练习1.10 下面过程计算一个称为Ackermann函数的数学函数： ```scheme (define A x y) (cond ((= y 0) 0) ((= x 0) (* 2 y)) ((= y 1) 2) (else (A (- x 1) (A x (- y 1)))))) ``` 下面各表达式的值是什么： `(A 1 10)` `(A 2 4)` `(A 3 3)` 请考虑下面的过程，其中的A就是上面定义的过程： `(define (f n) (A 0 n))` `(define (f n) (A 1 n))` `(define (f n) (A 2 n))` 请给出过程f、g和h对给定整数值n所计算的函数的数学定义。 # 理解 - `(A 1 10)`可用代换模型如下展开： ```scheme (* 2 (A 1 9)) (* 2 (* 2 (A 1 8))) ... (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (* 2 (A 1 1)))))))))) ``` 其中`（A 1 1）= 2`，结果即`2^10` 也可以用迭代的思路发现规律: ```scheme (A 1 1) = 2 (A 1 2) = (* 2 (A 1 1)) = 2^2 (A 1 3) = (* 2 (A 1 2)) = 2^3 ... (A 1 n) = (* 2 (A 1 n-1)) = 2^n ``` - `(A 2 4)`可用代换模型如下展开： ```scheme (A 2 4) (A 1 (A 2 3)) (A 1 (A 1 (A 2 2))) (A 1 (A 1 (A 1 (A 2 1)))) (A 1 (A 1 (A 1 2))) (A 1 (A 1 4)) (A 1 16) ``` 根据我们刚刚发现的规律，`(A 1 16) = 2^16` ```scheme (A 2 1) = 2 (A 2 2) = (A 1 (A 2 1)) = 2^2 (A 2 3) = (A 1 (A 2 2)) = 2^2^2 ... (A 2 n) = (A 1 (A 2 n-1)) = 2^2...^2 # 共n个2 ``` - `(A 3 3)`可用代换模型如下展开： ```scheme (A 3 3) (A 2 (A 3 2)) (A 2 (A 2 (A 3 1))) (A 2 (A 2 2)) (A 2 4) ``` 恰好就是刚刚计算的,`(A 3 3) = (A 2 4) = 2^16` - 数学定义 `(f n) = 2n` `(g n) = 2^n` `(h n) = 2^(h n-1)` ， 不知道准确的写法，姑且写个递推公式
