SICP 读书笔记 - 构造过程抽象

一、求平方根问题
 
虽然,以前使用递归解决过问题,但从未像使用scheme一样,如此直观地编写递归过程。
这也是一种自上而下地分解问题、解决问题的思维方式,即将一个复杂的问题按过程进行拆解。
递归求解问题,需要有一种接近解和结束递归的机制,否则计算过程将无限地递归下去。
接近解的机制是由数据性质决定的,即按照(y+x/y)/2递归下去,将无限地从x/2接近x的平方根;
而这个问题比较有意思的是,结束解的方式:
第一种,也是最容易想到的方式就是比较当前解与上一次解之间的差值,差值越小说明越接近解,因此可以取一个极小数作为阀值,如0.0001,当差值小于此阀值时,即表示可以接受当前解作为待求的平方根。
换句话说,这是一种用绝对距离来判断当前解是否接近真实解。从字面上也可以理解,绝对距离只针对某一区域有效。比如,如果求0.00001的平方根,那么很明显用0.0001这个绝对距离去度量针对0.00001的平方根的前后两次解,是不准确的(粒度太大)。因为由于接近解的分布非常密集,以至于任意相邻两个解的距离都会大于0.0001,从而无法得到较精确的解。
按理说,求一个大数,如果采用0.0001作为阀值终止计算,应该是可以了,实际是也存在问题。
原因就在于计算机实质是一种离散模型计算,这就导致计算机在表达实数集合时,只能妥协地采取地离散化表示。
即计算计中的浮点数(符号位:阶数:尾数)无法像数轴一样将所有的实数表达出来,对于大的浮点数,由于尾数数位有限,能将整数部分表达出来就错了,有时可能整数部分都要截断。
因此,如果一个数的平方根恰好为 计算机无法表达的数字,且其前后相邻的浮点数差值又大于0.0001,或甚至相差的都是整数部分,而非小数部分(小数表达不出来了)。这样,在递归计算时,可能就会在真实值左右来回计算,前后两次差值永远不会小于阀值。
仅从数学上说,一个绝对的阀值只会影响一侧的实数集计算,
即任意选一个数作为阀值,只会影响比其更小数的求解,但由于计算机的限制,对大数也产生了影响。
那么如何才能避免这个问题呢?
这时就体现了数学的魅力,我不用绝对距离,因为绝对距离只适用于特定区域。
由于上述公式是无限地逼近,相邻数之间的距离会越来越近,即(y1-y2)越来越小,同时由于上面推理我们知道这个差值会在实数的两个端相对于固定阀值不是太小就是太大。但无论你在哪个区域,如果快要接近解时,相对于那个区域的数值而言,变化会越来越小。即取其变化率:|y1-y2|/y1,即当前相对于上一个解变化了多少。以此来作为判断递归终止就将上述两个问题FIX掉了。

二、分钱问题

这是在讲树型递归过程的一个例子,即其递归计算过程展开平面上像一棵树一样,而且树中存在重复计算过程。
实际上就是动态规划中的0-1背包高级算法问题,但在SICP中却用来讲递归计算过程,可见SICP的高度。
SICP中有一句话,觉得算是解决分钱问题的核心思想:
“递归地归约为对更少的钱或更少的硬币种类的问题”
具体为将任何一种分钱分钱划分为两个集合:
1. 采用除x类型硬币外,其它硬币来分钱y
2. 采用所有各类的硬币,来分钱y-(x),其中(x)代表x类型硬币的面额,即先使用x类型硬币分了一次,剩下的钱再进行分
这样,每次剩下的钱再用上述这两个步骤进行计算,一直递归下去。
如同Fibonacci递归一样:
对问题进行递归拆解,但最后都必须要进行退化处理,否则会一直递归拆解下去。
即什么是终点,终点的计算值是多少。
对于分钱问题而言,由于有两个变量,即当前硬币种类k,和剩余的钱y。
那么枚举来看,无非有:
k >0 && y=0,这时是钱已分完,但还剩下几种类型硬币没用,算一种分法,所以应该返回1
k >0 && y<0,  这时是钱不仅分完,而且还出现负数,即上一种硬币分钱时,钱根本不够分的,所以这种分法失败,返回0
k >0 && y>0,  这时表示分钱还没进行完,需要继续应用上述递归算法
k =0 && y=0,  这时表示,硬币类型也用完了,钱也分完了,算一种分法,所以返回1
k =0 && y<0,  这时表示,硬币类型用完了,但上一次分钱失败,返回0
k =0 && y>0,  这时表示,硬币类型用完了,但钱也没分返回,即这种分法失败,返回0
k <0             ,这时表示,不管还有没有钱,硬币类型上次就没有了,分钱失败,返回0
即退化处理条件归纳为:
if k < 0,返回0
else
   y = 0,返回1
   y < 0,返回0
另外一个需要分析的是书中对硬币类型的处理,其原话是
“过程first-denomination以可用的硬币种数作为输入,返回第一种硬币的币值。这里认为硬币已经从最大到最小排列好了,其实采用任何顺序都可以”
 
即从上面两个递归子过程可以看出,计算关心的硬币类型x的面值|x| 和 当前剩余钱数;
同时从后面的退化处理可以看出,还关心当前还有多少种硬币类型没有使用。
因此,我们可以对硬币类型固定一个顺序,在所有的递归过程中都保持这个顺序,
这样能保证在递归树中,从根到叶子,对硬币的使用不会重复。
同时为了取到硬币的面值,书中就有了first-denomination这个函数,即在一个固定的使用顺序中:
剩余硬币类型个数 与 其将要使用的类型硬币面值 的映射关系。
这里蕴含这样一个常理:
对于一种分钱方式中采用的硬币类型,不同类型的使用顺序并不影响分钱的最终结果。
所以才有上面“采用任何顺序都可以”。

发表评论