第一章-构造过程抽象-2017.1.16

关于人对事物的认知主要有三个方面
  • 将若干简单认识组合为一个复合知识,由此产生出各种复杂的认识。
  • 将两个认识放在一起对照,不管他们如何简单或者复杂,在这样做时并不将它们合而为一。由此得到有关它们的相互关系的认识。
  • 将有关认识与那些在实际中和它们同在的所有认识隔离开,这就是抽象,所有具有普遍性的认识都是这样得到的。
习题1.4

这道题一开始我并没有得出比较正确的答案,我认为的答案是将两个数进行一个绝对值的相加。实际上的正确答案应该是通过这样子的一个define来进行一个高阶函数的运算,接受多个数据并对他们进行运算,是“数据” 和过程的统一

习题1.5

写这道题之前我其实一直对正则序应用序这两个玩意有点儿弄球不懂。在书上得出来的结果感觉是有限的。实际上正则序在小规模程序里面更容易被理解,它的做法实际上就是直接把问题展开,然后分布解决小的问题,这和早期的人工智能也有一定的相像之处。而应用序就有点儿像我们所说的暴力了,通过不断递归,一直到获得最终结果为止,实际上在应用的时候,应用序能够更容易被接受,我个人的观点认为可能是拆解问题所需要的模型和方法可能并不简单,有的时候在一定量级内应该是可以获得更好和快的结果的。这两者对于问题的求解不同的地方正是这道题的考核点。

(define (p) (p))
(define (test x y)
  (if(= x 0)
      0
      y))

这行代码在执行的时候,如果代入的x = 0, y = p,如果通过正则序求解可以直接获得0这个结果,如果通过应用序求解就会递归成无限循环,其中逻辑请各位也去结合上文想想嘿嘿。

关于牛顿法求平方根的证明

比如说需要求的是2的平方根。
猜测是1,2/1=2, (2+1)/2 = 1.5;
1.5, 2/1.5 = 1.3333, (1.5 + 1.3333)/2 = 1.4167
1.4167, 2/1.4167 = 1.4118, (1.4118 + 1.4167) / 2 = 1.4142;
方法很粗暴简单,但是为什么可以这样子求解?

  • 所求的X应为y的平方根
  • x*x = y;
  • y / x = x;
  • (x+x)/2 = x;

得证。

并可由此延伸出牛顿法的立方根求法

  • x*x*x = y;
  • y / x / x = x;
  • y / x / x + 2x / 3 = x;

得证。

习题1.6

这道题其实和1.5很相似,不需要再展开来说了,因为在lisp中cond函数是进行应用序求值的,它在这样子的一个函数中会对第三个参数进行循环调用使得最后进入一个不可跳出的死循环。

习题1.7

不难得出,因为牛顿法是通过求平均值来获得最后的结果的,所以基本不会获得一个精准的整数,所以在面对精度控制的问题上会出现问题,就如同10000的平方根是100,如果控制的精度卡死在0.000001的话,那么就会出现非常大的性能浪费,所以通过结果与前一个结果的比例关系来获得的话是相对来说比较简单而高性能的,不过必须要注意的就是除数为零的情况就是了。

习题1.8

已证明

习题1.9

第一个函数是递归的,第二个函数是迭代的。迭代和递归是不同的概念。递归会不断地调用本身进行运算,而迭代则是不断地进行求解获得结果,虽然可能会有重叠,但是在概念上面是有差别的。

尾递归

关于递归和迭代的差别,迭代所使用的内存空间是常数量级的,而递归则不一样。
简而言之如一下代码。

int recsum(int x)
{
  if (x == 1) return x
  else return x + recsum(x - 1)
}

看起来好像没有什么问题,在一开始的求解斐波那契数列的时候我们也曾经这样子写过,但是这样子的写法会炸。为什么?

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

这就是这个函数运行的时候的内存占用情况, 问题就显而易见了。当我进入下一个步骤的时候,上一个步骤的内存占用量并没有能够删除掉,也就是说在这样子的递归环境下我不断为recsum这个函数申请内存地址,最后达到峰值才不断地回落,这样的一个过程中是可能会造成爆栈的。
尾递归是可以在常数量级内解决问题的递归。
简而言之就是,我不断更新原本的内存空间,而不是去进行重新申请。

int recsum(int x,int y)
{
  if (!x)return y;
  else return recsum(x-1, y + x);
}
习题1.13

我TM。。我就不该好奇先证这道题。。。
花了一个多小时的时间,都没有想通为什么最后查了一下才发现原来是条件缺失了,我并没有拿到所有的条件我@#!@¥@#!¥直接用数学归纳法可以求解出后半部分的内容,前半部分的内容则通过特定定理求出,下面是证明过程。


QQ图片20170116170634.jpg
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 204,189评论 6 478
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,577评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,857评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,703评论 1 276
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,705评论 5 366
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,620评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,995评论 3 396
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,656评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,898评论 1 298
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,639评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,720评论 1 330
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,395评论 4 319
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,982评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,953评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,195评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 44,907评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,472评论 2 342

推荐阅读更多精彩内容