矩阵 原来不是没有生命的数字列表
一切应该从斐波那契数列开始说起。 求第n项的方法 可以通过递归的方法求,只是调用栈可能会很长。 当然,也可以通过缓存减少调用次数。可是下面的方法确实让孤陋寡闻的我眼界大开。
(f(n−1)0f(n−2)0)∗(1110)=(f(n−1)+f(n−2)0f(n−1)0)=(f(n)0f(n−1)0)
即
(f(n)0f(n−1)0)=(f(2)0f(1)0)∗(1110)n−2
至于对于某数x的n次方,我们可以通过的方式达到log(n)的效果
int ans =
1;
while (n) {
if (n &
1) {
ans *= x;
}
n >>=
1;
x = x^
2;
}
为什么会这样呢?
总结一下,应该是迭代二字。如果我们需要求的结果是可以通过迭代的方法求出 例如此时的 f(n) = f(n-1) + f(n-2),这个时候可以考虑用矩阵的方法。 例如现在有个规律是f(n) = 2f(n-1) + 13f(n-2) 那么相关的矩阵应该是:
(21310)
或者说,其实就是找出公共算子,乘积也好,乘方也罢,最终都是可以用更快的方法求出结果。
希望还会有更多的添加。。。
转载请注明原文地址: https://ju.6miu.com/read-200215.html