详解SICP习题1.19

  高中读完我就把数学都忘光了,看SICP的习题1.19硬是看不明白,网上找了好久,有幸看到一篇文章说得很详细,下面是我看完此文章后的个人理解。

斐波那契的定义

F(n)={0,if n=01,if n=1F(n1)+F(n2),if n>1F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-1) + F(n-2), & \text{if } n > 1 \end{cases}

题目

  题目给出以下代码要我们补全:

(define (fib n) (fib-iter 1 0 0 1 n)) (define (fib-iter a b p q count) (cond ((= count 0) b) ((even? count) (fib-iter a b <??> ; compute p' <??> ; compute q' (/ count 2))) (else (fib-iter (+ (* b q) (* a q) (* a p)) (+ (* b p) (* a q)) p q (- count 1)))))

先理解普通算法

  最原始的解法,从F(0)F(0)F(1)F(1)开始,运算n次才能算出F(n)F(n)F(n+1)F(n+1)

  • F(2)=F(1)+F(0)F(2) = F(1) + F(0)
  • F(3)=F(2)+F(1)F(3) = F(2) + F(1)
  • F(4)=F(3)+F(2)F(4) = F(3) + F(2)
  • ......
  • F(n)=F(n1)+F(n2)F(n) = F(n-1) + F(n-2)
  • F(n+1)=F(n)+F(n1)stopF(n+1) = F(n) + F(n-1) \leftarrow stop

翻译翻译"T"到底代表什么

  题目给出了一个很巧妙的算法,可以降低时间复杂度到O(logn)O(logn)。由于我的数学水平差,所以这里先不考虑算法的原理是什么,只考虑:这个算法是怎么运作的。   对于任意一个斐波那契对,我们假设左边较大的是aa,右边较小的是bb。例如假设F(6)=a,F(5)=bF(6) = a,F(5) = b。那么对于下一对新的序列F(7)=aF(7)=a'F(6)=bF(6)=b'

{aa+bba\begin{cases} a' \leftarrow a + b \\ b' \leftarrow a \end{cases}

  我们把这种a,ba,b转化为a,ba',b'的转化方式记为T(ab)T(ab)。那么对于原始的计算斐波那契的方式,等价于执行n次T(ab)T(ab)——即T(ab)nT(ab)^{n}

引入p和q

  题目这里开始不说人话了,无缘无故引入了两个变量ppqq,并且给出了一个新的转化方式,我们称为T(abpq)T(abpq)

{abq+aq+apbbp+aq\begin{cases} a' \leftarrow bq + aq + ap \\ b' \leftarrow bp + aq \end{cases}

  然后题目说,假设这里的p=0,q=1p = 0,q = 1,那么这个表达式和上面的表达式是等价的,这不是屁话吗?!   最难理解的地方来了。题目又说:有一种方式可以由ppqq计算出pp'qq',新的pp'qq'的作用是一次性执行两次TT,即T(abpq)=T(T(abpq))T(abp'q')=T(T(abpq)),至于为什么,我也不知道sticker。   例如我们要计算F(11)F(11),原始解法是T(ab)11T(ab)^{11},过程如下:(第四步应该为a,ba''',b''',第五步应该为a,ba'''',b'''',第六步应该为a,a''''',...等等等,写太长会很难看,所以省略)

F(1)+F(0),剩余T(ab)11F(2)+F(1),剩余T(ab)10F(3)+F(2),剩余T(ab)9F(4)+F(3),剩余T(ab)8F(5)+F(4),剩余T(ab)7F(6)+F(5),剩余T(ab)6F(7)+F(6),剩余T(ab)5F(8)+F(7),剩余T(ab)4F(9)+F(8),剩余T(ab)3F(10)+F(9),剩余T(ab)2F(11)+F(10),剩余T(ab)1F(12)+F(11),剩余T(ab)0\begin{array}{c} F(1) + F(0),剩余T(ab)^{11} \\ \downarrow \\ F(2) + F(1),剩余T(a'b')^{10} \\ \downarrow \\ F(3) + F(2),剩余T(a''b'')^{9} \\ \downarrow \\ F(4) + F(3),剩余T(ab)^{8} \\ \downarrow \\ F(5) + F(4),剩余T(ab)^{7} \\ \downarrow \\ F(6) + F(5),剩余T(ab)^{6} \\ \downarrow \\ F(7) + F(6),剩余T(ab)^{5} \\ \downarrow \\ F(8) + F(7),剩余T(ab)^{4} \\ \downarrow \\ F(9) + F(8),剩余T(ab)^{3} \\ \downarrow \\ F(10) + F(9),剩余T(ab)^{2} \\ \downarrow \\ F(11) + F(10),剩余T(ab)^{1} \\ \downarrow \\ F(12) + F(11),剩余T(ab)^{0} \\ \end{array}

  而它这个解法,过程如下:

F(1)+F(0),剩余T(abpq)11指数是奇数,pq不变F(2)+F(1),剩余T(abpq)10偶数,第一次计算pq,并且n/2F(7)+F(6),剩余T(abpq)5奇数,pq不变F(8)+F(7),剩余T(abpq)4第二次计算pq,并且n/2F(10)+F(9),剩余T(abpq)2第三次计算pq,并且n/2F(11)+F(10),剩余T(abpq)1奇数,pq不变F(12)+F(11),剩余T(abpq)0结束\begin{array}{c} F(1) + F(0),剩余T(abpq)^{11} \leftarrow 指数是奇数,p和q不变 \\ \downarrow \\ F(2) + F(1),剩余T(a'b'pq)^{10} \leftarrow 偶数,第一次计算p'和q',并且n/2 \\ \downarrow \\ F(7) + F(6),剩余T(a''b''p'q')^{5} \leftarrow 奇数,p'和q'不变 \\ \downarrow \\ F(8) + F(7),剩余T(a'''b'''p'q')^{4} \leftarrow 第二次计算p''和q'',并且n/2 \\ \downarrow \\ F(10) + F(9),剩余T(a''''b''''p''q'')^{2} \leftarrow 第三次计算p'''和q''',并且n/2 \\ \downarrow \\ F(11) + F(10),剩余T(a'''''b'''''p'''q''')^{1} \leftarrow 奇数,p'''和q'''不变 \\ \downarrow \\ F(12) + F(11),剩余T(a''''''b''''''p'''q''')^{0} \leftarrow 结束 \\ \end{array}

  注意这里的过程,p,qp,q的值和a,ba,b一样是迭代计算的,如果指数是奇数——则p,qp,q不变,如果指数是偶数——则算出新的p,qp',q'作为下一步迭代。

如何计算p'和q'

  注意:只有指数是偶数的情况下,才需要计算p,qp',q'   已知T(T(abpq))  T(abpq)T(T(abpq)) \xrightarrow{~~} T(abp'q'),我们把表达式左边计算出来,就可以得到p,qp',q'了。先通过TTT(T(abpq))T(T(abpq))计算出来:

T(T(abpq)){abq+aq+apbbp+aq{abq+aq+apbbp+aqExpression1={a(bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)pb(bp+aq)p+(bq+aq+ap)q\begin{array}{c} T(T(abpq)) \\ \downarrow \\ \begin{cases} a' \leftarrow bq + aq + ap \\ b' \leftarrow bp + aq \end{cases} \\ \downarrow \\ \begin{cases} a'' \leftarrow b'q + a'q + a'p \\ b'' \leftarrow b'p + a'q \end{cases} \\ \downarrow \\ Expression1 = \begin{cases} a'' \leftarrow (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p \\ b'' \leftarrow (bp + aq)p + (bq + aq + ap)q \end{cases} \\ \end{array}

  T(abpq)T(abp'q')同样可以通过TT计算为:

T(abpq)Expression2={abq+aq+apbbp+aq\begin{array}{c} T(abp'q') \\ \downarrow \\ Expression2 = \begin{cases} a'' \leftarrow bq' + aq' + ap' \\ b'' \leftarrow bp' + aq' \end{cases} \\ \end{array}

  用观察法,可以把上面复杂的Express1Express1改写为:

Expression1={a(bp+aq)q+(bq+aq+ap)q+(bq+aq+ap)pb(bp+aq)p+(bq+aq+ap)qExpression1={ab(2pq+qq)+a(2pq+qq)+a(pp+qq)bb(pp+qq)+a(2pq+qq)\begin{array}{c} Expression1 = \begin{cases} a'' \leftarrow (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p \\ b'' \leftarrow (bp + aq)p + (bq + aq + ap)q \end{cases} \\ \downarrow \\ Expression1 = \begin{cases} a'' \leftarrow b(2pq + qq) + a(2pq + qq) + a(pp+qq) \\ b'' \leftarrow b(pp+qq) + a(2pq + qq) \end{cases} \\ \end{array}

  对比Expression1Expression1Expression2Expression2的右边可知:

{bq+aq+ap=b(2pq+qq)+a(2pq+qq)+a(pp+qq)bp+aq=b(pp+qq)+a(2pq+qq){p=(pp+qq)q=(2pq+qq)\begin{array}{c} \begin{cases} bq' + aq' + ap' = b(2pq + qq) + a(2pq + qq) + a(pp+qq) \\ bp' + aq' = b(pp+qq) + a(2pq + qq) \end{cases} \\ \downarrow \\ \begin{cases} p' = (pp+qq) \\ q' = (2pq + qq) \end{cases} \end{array}

算法的原理

To be determined

标签:杂谈
11个月前
0