`
阿尔萨斯
  • 浏览: 4108310 次
社区版块
存档分类
最新评论

SICP 习题 (1.10)解题总结

 
阅读更多

SICP 习题 1.10 讲的是一个叫“Akermann函数”的东西,去百度查可以查到对应的中文翻译,叫“阿克曼函数”。


就像前面的解题总结中提到的,我是一个数学恐惧者,看着稍微复杂一点的什么函数我就怕。所以这道题放了很久都没去动它,不过有担心跳过这道题对后面的学习不利,所以最终还是鼓足勇气尝试做这个题目。


做完了我才发现,其实这道题真的可以跳过,做不做这道题似乎对后面的学习没什么影响。从题目的内容来看,作者应该是希望在习题中引入“树形递归”,让学生在下一节课的学习中有所准备,相当于是预习题。事实上,这个“预习题”太难了,比后面介绍的“斐波那契数”难好多,所以起不到什么“预习”的作用。

所以,如果你也害怕数学的话,可以考虑跳过这道题,就当它从来没有在你生命中出现过。


当然,如果你愿意挑战自己,和我一样尝试一下,你也会发现其实所谓的“阿克曼函数”也没什么太神秘的。

大家都说数学是“大脑的体操”,我没有数学天分,做不了“大脑的体操”,不过我慢慢爬上去,看看“大脑的单杠”啥样子还是可以的嘛。


先看看“阿克曼函数”的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),(A2 4),(A 3 3)展开,从而总结出(A 0 n),(A 1 n)和 (A 2 n)的数学含义,因为我就是这么做出这道题的。

后来写了一半发现不对路,把那么繁琐的展开和归约步骤写下来太麻烦,大家也不会花时间去看,真是浪费时间。

所以就希望通过其它方式和大家解释这个“阿克曼函数”,不过你如果希望自己完成这个练习,像我一样那张纸直接进行展开和归约是可行的,也不会花太长时间。

另外,如果你只是希望了解“阿克曼函数”本身,建议你直接去百度搜索,那里能找到专业的解释,读起来比读程序简单。

如果你是希望了解这里定义的(A x y)过程如何简单地通过递归调用实现“阿克曼函数”,那就让我们来做点事情吧。

第一个可以要做的首先是照猫画猫,将(A x y)过程抄到你的Scheme解释器中,执行一下(A 1 10), (A 2 4), (A 3 3)看看有什么结果,同时可以针对(A 1 n)和 (A 2 n)多做几次试验,比如(A 1 7), (A 1 6), (A 2 2), (A 2 3)之类的,注意,跑(A 2 5)以上会达到递归嵌套限制。

跑完以上过程以后大概会有个认识。(A 0 n)比较简单,就是返回(2*n),这个从过程的代码里也能看出来。(A 1 n)复杂一点点,不过做多了计算机工作,对1024,2048之类的数字还是比较敏感的,大概可以猜出来(A 1 n)返回的是2的n次方,具体为什么会返回2的n次方就需要分析一下才知道。(A 2 n)就比较难猜了,需要看看程序到底怎么跑的才行。

怎么来分析(A x y)的运行过程呢?简单一点的方法是在(A x y)过程中加入(format #t )输出,看看到底是怎么调用的。

比如我仿照(A x y)过程写了一个(A-with-info x y)过程,代码如下:


(define (A-with-info x y)
  (format #t  "Evaluating (A ~S ~S) " x y)
  (cond ((= y 0)  (format #t "the result is 0~%"))
	((= x 0)  (format #t "the result is ~S~%" (* 2 y)))
	((= y 1)  (format #t "the result is 2~%"))
	(else (format #t "transforming to (A ~S (A ~S ~S))~%" (- x 1) x (- y 1))))
  (cond ((= y 0)  0)
	((= x 0)  (* 2 y))
	((= y 1)  2)
	(else (A-with-info (- x 1)
			     (A-with-info x (- y 1))))))



以上代码几乎完全和(A x y)的代码一样,就是增加了一些format的输出而已,这样可以在代码运行过程中跟踪过程的变换。

比如,调用(A-with-info 1 8)的结果如下,通过以下输出可以比较明了地看清过程的变换。



1 ]=> (A-with-info 1 8)

Evaluating (A 1 8) transforming to (A 0 (A 1 7))

Evaluating (A 1 7) transforming to (A 0 (A 1 6))

Evaluating (A 1 6) transforming to (A 0 (A 1 5))

Evaluating (A 1 5) transforming to (A 0 (A 1 4))

Evaluating (A 1 4) transforming to (A 0 (A 1 3))

Evaluating (A 1 3) transforming to (A 0 (A 1 2))

Evaluating (A 1 2) transforming to (A 0 (A 1 1))

Evaluating (A 1 1) the result is 2

Evaluating (A 0 2) the result is 4

Evaluating (A 0 4) the result is 8

Evaluating (A 0 8) the result is 16

Evaluating (A 0 16) the result is 32

Evaluating (A 0 32) the result is 64

Evaluating (A 0 64) the result is 128

Evaluating (A 0 128) the result is 256

;Value: 256


如果你愿意花时间,可以想一些办法让上面的输出更清晰一些,比如我写的另一个过程(A-with-detail)的输出如下:

1 ]=> (A-with-detail 1 8 "" "")

(A 1 8)

(A 0 (A 1 7))

(A 0 (A 0 (A 1 6)))

(A 0 (A 0 (A 0 (A 1 5))))

(A 0 (A 0 (A 0 (A 0 (A 1 4)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 1 1) is 2])))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 2) is 4]))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))

(A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 4) is 8])))))

(A 0 (A 0 (A 0 (A 0 (A 0 8)))))

(A 0 (A 0 (A 0 (A 0 [(A 0 8) is 16]))))

(A 0 (A 0 (A 0 (A 0 16))))

(A 0 (A 0 (A 0 [(A 0 16) is 32])))

(A 0 (A 0 (A 0 32)))

(A 0 (A 0 [(A 0 32) is 64]))

(A 0 (A 0 64))

(A 0 [(A 0 64) is 128])

(A 0 128)

[(A 0 128) is 256]

;Value: 256


这里就可以清晰地看见(A 1 8)的展开和归约过程。


同样,我们可以看看(A 2 4)的变换过程:

1 ]=> (A-with-detail 2 4 "" "")

(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 [(A 2 1) is 2])))

(A 1 (A 1 (A 1 2)))

(A 1 (A 1 (A 0 (A 1 1))))

(A 1 (A 1 (A 0 [(A 1 1) is 2])))

(A 1 (A 1 (A 0 2)))

(A 1 (A 1 [(A 0 2) is 4]))

(A 1 (A 1 4))

(A 1 (A 0 (A 1 3)))

(A 1 (A 0 (A 0 (A 1 2))))

(A 1 (A 0 (A 0 (A 0 (A 1 1)))))

(A 1 (A 0 (A 0 (A 0 [(A 1 1) is 2]))))

(A 1 (A 0 (A 0 (A 0 2))))

(A 1 (A 0 (A 0 [(A 0 2) is 4])))

(A 1 (A 0 (A 0 4)))

(A 1 (A 0 [(A 0 4) is 8]))

(A 1 (A 0 8))

(A 1 [(A 0 8) is 16])

(A 1 16)

(A 0 (A 1 15))

(A 0 (A 0 (A 1 14)))

(A 0 (A 0 (A 0 (A 1 13))))

(A 0 (A 0 (A 0 (A 0 (A 1 12)))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 1 11))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 10)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 9))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 8)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 7))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 6)))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 5))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 4)))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 3))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 2)))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 1 1))))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 1 1) is 2])))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 2)))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 2) is 4]))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 4))))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 4) is 8])))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 8)))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 8) is 16]))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 16))))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 16) is 32])))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 32)))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 32) is 64]))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 64))))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 64) is 128])))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 128)))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 128) is 256]))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 256))))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 256) is 512])))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 (A 0 512)))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 512) is 1024]))))))

(A 0 (A 0 (A 0 (A 0 (A 0 (A 0 1024))))))

(A 0 (A 0 (A 0 (A 0 (A 0 [(A 0 1024) is 2048])))))

(A 0 (A 0 (A 0 (A 0 (A 0 2048)))))

(A 0 (A 0 (A 0 (A 0 [(A 0 2048) is 4096]))))

(A 0 (A 0 (A 0 (A 0 4096))))

(A 0 (A 0 (A 0 [(A 0 4096) is 8192])))

(A 0 (A 0 (A 0 8192)))

(A 0 (A 0 [(A 0 8192) is 16384]))

(A 0 (A 0 16384))

(A 0 [(A 0 16384) is 32768])

(A 0 32768)

[(A 0 32768) is 65536]

;Value: 65536


最后就是有关(A 2 n)的数学含义,仔细看看上面的变换过程大概可以想明白,就是2的右上角有n个不断变小的2,就是取2 的2次方,赋予A,然后取2的A次方,赋予B,再取2的B次方,赋予C,一直下去,做n次。从上面的分析看,这个“阿克曼函数”有迭代实现喔。是否还记得我们之前讨论过的“迭代计算过程”和“递归计算过程”?书中的“阿克曼函数”的实现使用的是“递归计算过程”,而这个函数显然有“迭代计算过程”的实现方法。有关这个我们在这里就不详细讨论了,另找时间再讲这个东西。


如果看完上面的内容不明白的话最好自己做完成以上步骤,应该会有一些认识。如果还是不明白就去看看网上有关“阿克曼函数”的具体解释,看了还是不明白的话就放弃吧,“数学不是个买卖,想买就能买”。


对于已经明白过来的同学们,可以想想(A 3 n)的数学含义是什么,有点花脑筋哟!想明白就再想想(A 4 n), (A 5 n),想想(A m n)函数中m 和n分别起到什么作用,(A m n)的广泛含义是什么?

问完这些问题,我似乎看到了很多好学的同学们抓破脑袋毫无头绪的样子,于是我开心地笑了,愉快地关上了我的MacBook,深藏功与名。


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics