10.1.斐波那契数列 (Easy)*
题目描述*
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项。斐波那契数列的定义如下：
F(0) = 0, F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。
提示*
0 <= n <= 100
代码*
递归或迭代，迭代就不用求重复解了。
剑指 offer 提供了以下的公式：
\begin{bmatrix} f(n) & f(n - 1) \\ f(n - 1) & f(n - 1) \end{bmatrix} = {\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}}^{n - 1}
使用快速幂算法计算矩阵的幂。
class Solution {
public:
int fib(int n) {
if(n <= 1) {
return n;
}
int res = 0, n1 = 1, n2 = 0;
while(n-- >= 2) {
res = (n1 + n2) % 1000000007;
n2 = n1;
n1 = res;
}
return res;
}
};
struct Matrix2By2 {
Matrix2By2 (long long m00 = 0, long long m01 = 0, long long m10 = 0, long long m11 = 0) : m_00(m00), m_01(m01), m_10(m10), m_11(m11) { }
long long m_00;
long long m_01;
long long m_10;
long long m_11;
};
Matrix2By2 MatrixMultiply(const Matrix2By2& matrix1, const Matrix2By2& matrix2) {
return Matrix2By2(
(matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10) % 1000000007,
(matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11) % 1000000007,
(matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10) % 1000000007,
(matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11) % 1000000007);
}
Matrix2By2 MatrixPower(unsigned int n) {
Matrix2By2 matrix;
if(n == 1) {
matrix = Matrix2By2(1, 1, 1, 0);
} else if(n % 2 == 0) {
matrix = MatrixPower(n / 2);
matrix = MatrixMultiply(matrix, matrix);
} else if(n % 2 == 1) {
matrix = MatrixPower((n - 1) / 2);
matrix = MatrixMultiply(matrix, matrix);
matrix = MatrixMultiply(matrix, Matrix2By2(1, 1, 1, 0));
}
return matrix;
}
class Solution {
public:
int fib(int n) {
if (n <= 1) {
return n;
}
Matrix2By2 res = MatrixPower(static_cast<unsigned int>(n - 1));
return res.m_00 % 1000000007;
}
};
最后更新: July 23, 2022