文档章节

【SICP练习】8 练习1.12

NoMasp
 NoMasp
发布于 2015/09/08 21:47
字数 601
阅读 1
收藏 0


这道练习的翻译有误。原文是:Write a procedure that computes elements of Pascal’s triangle bymeans of a recursive process.正确的翻译应该是计算帕斯卡三角形的各个元素。

y :

0       1

1      1 1

2    1 2  1

3   1 3  3  1

4 1 4  6 4  1

5

x: 0 1  2 3  4

 

如果用x代表帕斯卡三角形中列的元素的值,y则代表行的元素的值。那么(x,y)上的值等于(x-1,y-1)(x-1,y)上的元素的和。当y=0,或者x=y时,该处的值为1

综合以上的两个性质,就可以写出递归版本的pascal函数了:

(define (pascal y x)

        (cond((> x y)   (error ‘unvalid col value”))

                  ((or (= x 0) (= x y)) 1)

                  (else (+ (pascal (- y 1) (- x 1))

                            (pascal (- y 1) x)))))

下面我们来检验一下:

(pascal 5 4)

;Value: 5

(pascal 5 3)

;Value: 10

虽然题目中只要求用递归,但作为学习者,不妨也用迭代试试看。更何况在前面的学习中,我们遇到了好几次超过最大递归深度。就像书中的斐波那契一样,带有太多的重复计算。利用刚才的函数,博主测试了一下(pascal 100 49),结果毫无疑问了。

帕斯卡三角形我们在数学中也学过的吧,另外在维基百科中也有相关介绍。除了刚才的计算方法之外还有一种:

(pascal y x)=y!/(x!*(y-x)!)

传说中的什么排版东东我都不太会用,大家将就着看了。

阶乘可以用第22页的注释中的代码:

(define (factorial n)

        (define(iter product counter)

                 (if(> counter n)

                   product

                   (iter (* counter product)

                  (+ counter 1))))

        (iter1 1))

迭代版本的pascal

(define (pascal y x)

        (/  (factorial y)

            (* (factorial x)

                   (factorial (- y x)))))

迭代的好处书中有大篇幅介绍,像什么空间需求。另外计算的值的大小不受递归栈深度的控制。我们再将前文中的10049两个参数测试一下:

(pascal 100 49)

;Value: 98913082887808032681188722800

即便是用10000499两个参数也可以算出来,结果大概有110位数,这就是递归和迭代最显而易见的区别了。

下一节的习题因为太难以输入到电脑中,就先搁置了。

版权声明:本文为 NoMasp柯于旺 原创文章,未经许可严禁转载!欢迎访问我的博客:http://blog.csdn.net/nomasp

本文转载自:http://blog.csdn.net/nomasp/article/details/43529137

NoMasp
粉丝 7
博文 334
码字总数 0
作品 0
镇江
程序员
私信 提问
加载中

评论(0)

邢洁 2016-12-30 工作日报

業務内容 8:00~9:00 处理乐酷天网络订单4张 1.友盛売上伝票4张 2.友利売上伝票4张 3.友利仕入伝票4张 4.送り状4张 5.登录乐天订单送状番号4件 9:00~12:00 代引伝票送状番号的登录 1.12/26号...

邢洁
2016/12/30
1
0
邢洁 2016-12-8 工作日报

業務内容 8:00~10:30 处理乐酷天网络订单17张 1.友盛売上伝票17张 2.友利売上伝票25张 3.友利仕入伝票17张 4.送り状17张 5.登录乐天订单送状番号17件 10:30~12:00 代引伝票送状番号的登录 ...

邢洁
2016/12/08
1
0
于志豪 2017-12-5工作日报

8:00~9:00处理乐酷天网络订单27张 9:00~10:00代引伝票子伝票与母伝票的登录 1.12/1号yamato代引SCAN登录9张 2.12/1号yamato代引SCAN登录31张 10:00~11:00代引伝票送状番号的登录 1.12/1号...

yuzhihao
2017/12/05
0
0
邢洁 2016-12-7 工作日报

業務内容 8:00~10:00 处理乐酷天网络订单13张 1.友盛売上伝票14张 2.友利売上伝票13张 3.友利仕入伝票14张 4.送り状14张 5.登录乐天订单送状番号13件 10:00~10:30 代引伝票SCAN的登录 1.12...

邢洁
2016/12/07
3
0
邢洁 2016-12-26 工作日报

業務内容 8:00~10:30 处理乐酷天网络订单26张 1.友盛売上伝票29张 2.友利売上伝票8张 3.友利仕入伝票29张 4.送り状29张 5.登录乐天订单送状番号26件 10:30~11:00 代引伝票SCAN的登录 1.12...

邢洁
2016/12/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

如何在PHP中定义一个空对象

用一个新的数组,我这样做: $aVal = array();$aVal[key1][var1] = "something";$aVal[key1][var2] = "something else"; 对象有类似的语法吗 (object)$oVal = "";$oVal->key1->var1 =......

javail
10分钟前
13
0
从centos服务器上导出项目,记录一次做憨批的工作记录

遇到一个客户,说要从他的centos上导出网站和数据库,以前操作centos都是直接putty上shell,装宝塔,然后面板操作就完事儿了.然后遇到这种dos操作linux,还是第一次. 首先xshell,登录上去后,安装一...

老bia同学
13分钟前
27
0
Linuxprobe第五天

shell命令脚本 一个完整的shell脚本 脚本声明 #!/bin/bash 脚本注释 #xusikkwusxshuusnxu 脚本命令 ls pwd 1、接收参数 2、判断参数 3、流程控制 && 若前面成功,则执行后面 || 若前面失败,...

nt狮子男人
18分钟前
13
0
array_map,array_walk和array_filter之间的区别

array_map , array_walk和array_filter之间究竟有什么区别。 我从文档中看到的是,您可以传递一个回调函数来对提供的数组执行操作。 但我似乎没有发现它们之间有任何特别的区别。 他们做同样...

技术盛宴
26分钟前
41
0
MySQL字符串截取的4个函数

1、从左开始截取字符串 left(str, length) 说明: left(被截取字段,截取长度) 例如: select left(content,200) as abstract from my_content_t 从左边(字符串开始位置)截取指定长...

fairy1674
今天
92
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部