算法-sicp中练习1.19的变换规则是怎么推导出来的

Question

练习1.19中说
a <- a+b, b <- a被称为T变换， Tpq 变换 a <- ap + a q + bq, b <- bp + a*q, 所以T变换是Tpq 变换 q=1 p=0的特例.

这个Tpq变化

T(pq) (a,b) = T(pq) (bq+aq+ap,bp+aq);

是怎么推导出来的？

Answer 1

以前的回答已经删除，我误解了。这个是斐波那契矩阵快速降幂。根据斐波那契数列的定义有：

F(n)=f(n-1)+f(n-2)
F(1)=1
F(2)=1

再看看这个问题，我们添加一个 a = 1 于是：

a = 1；   // 也就是 F(1)
b = a;    // 也就是 F(2)
a = a+b,  // 也就是 F(n)

同时我们可以将 b a 看做一个向量[b a]，前面的操作就可以乘以矩阵：

1 1
1 0