E1.19要求实现一个O(log n)的求斐波那契数列的函数T
及根据要求,T(n)=T(T(n/2))
观察得:
A=[1 11 0]
A2=[2 11 1].......
利用........,
[FibnFibn−1]=[1 11 0][Fibn−2Fibn−3]
同时,根据矩阵幂的性质,
在原题中,count为偶数时,将矩阵自身幂一次就好了?
于是乎:
[D pp q]2=[D′ Dq+pqDq+pq pp+qq]
其中,D=p+q
于是乎:
p←p∗p+q∗q
q←D∗q+p∗q
emmmmmm.....
希望没有搞错 