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

SICP习题 (1.12)解题总结

 
阅读更多

SICP 习题 1.12 要完成的工作是帕斯卡三角,有没有觉得“帕斯卡”这三个字很熟悉呀,在你人生知识水平的最高点上你应该接触过他,不过现在你可能忘了。


仔细回想的话,你可能会有点印象,物理中的压强单位就是“帕斯卡”。很开心地告诉你,这两个“帕斯卡”是同一个人。帕斯卡不仅是个物理学家,还是个数学家,百度百科里这样描述:“布莱士.帕斯卡是法国数学家、物理学家、哲学家、散文家。” 。


人家还是个散文家!! 牛人就是牛人,完全无视我等庸才地存在着。


所谓帕斯卡三角就是像下面这样的三角型:


1

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

注意我这里的排列方式和书中的不一样。书中是一个正立的等腰三角型的样子,所以可以说每个数是它上面两个数的和。


我这里将帕斯卡三角形向左对齐了,所以我这里每个数等于它左上方和正上方两个数的和。

我这样做不是为了偷懒,不是觉得这样排版简单,是因为这样比较容易对应上数据模型。


如果是按书中的排列方式,我们怎么定位每一个数呢,按行号和列号编排的话,第一行的第一个数应该算是number(1,1),既然是number(1,1),不如就将它放到第一排的第一列,不要放在一行的中间了。


然后就是对于number(x,y)中x和y的约定,我使用的是以左上角为原点,x轴向右,y轴向下的坐标系,不好意思,做窗口绘制做多了,习惯使用这样的坐标系。


也就是说number (3,4)是指的由上往下第4排的第3列。


好,接着就是如何求帕斯卡三角形某一个位置上的数,我定义的过程如下,没有做太多调用参数的判断,使用的时候需要小心一点,不要用错参数。


(define (pascal-recrusive-element x y)
  (if (= x 1) 1
      (if (= x y) 1
	  (+ (pascal-recrusive-element x (- y 1)) (pascal-recrusive-element (- x 1) (- y 1))))))


求以上结果使用的还是递归方法,求某一个位置的数就通过求它左上方"(x-1)(y-1)"和正上方“(x) (y -1)”的数来得到,一直递归求值。


完成以上工作以后我们觉得还有好多事情要做,就是求得每一行的每一个数,将它们按正确的方式打印出来。可能是做以前的c编程题做的太多,习惯了这个方式。


后来我全做完了去网上查答案,发现很多人做到我这步就算成功了,根本没有去求完整的帕斯卡三角形,可惜是做完了才发现这一点,不然可以省点时间。


既然已经做了,就和大家分享一下,我先是做了一个pascal-recrusive-line过程,用来打印某一行帕斯卡数,过程如下:


(define (pascal-recrusive-line x n)
  (format #t " ~S "  (pascal-recrusive-element x n))
   (if (> x 1)
   (pascal-recrusive-line (- x 1) n)))


然后又做了一个pascal-recrusive过程,用来迭代指定数量的行,过程如下:


(define (pascal-recrusive n)
  (if (> n 1)
      (pascal-recrusive (- n 1)))
  (pascal-recrusive-line n n)
  (format #t "~%"))



不知道大家有没有留意我的过程名使用的是recrusive,既然有recrusive版本的实现,应该有迭代版本的实现吧。


我真做了一个,因为这个帕斯卡数确实有迭代解,我用迭代方式算出每一行的帕斯卡数,记录在一个列表里,将这些列表又保存在一个大的列表里形成一个类型二维数组的东西来记录产生的帕斯卡数。


做的函数不是很漂亮,就不在这里现眼了,大家有时间可以去试试做一个迭代版本的帕斯卡三角形生成函数。



分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics