跳台阶问题
题目描述：
一个台阶总共有 n 级，如果一次可以跳 1 级，也可以跳 2 级。求总共有多少种跳法，并分析算法的时间复杂度。
分析和解法：
我们可以将原问题转化为斐波那契数列问题。
解法一：经典递归
我们把 n 级台阶时的跳法看成是 n 的函数，记为 f(n) 。
- 当 n = 1 时，f(n) = 1;
- 当 n = 2 时，f(n) = 2;
- 当 n > 2 时，f(n) = f(n-1) + f(n-2)
原来上述问题就转化为我们平常所熟知的 Fibonacci 数列问题了。
源代码如下：
#include <iostream>
using namespace std;
long long Fibonacci(int n)
{
int result[3] = {0, 1, 2};
if (n <= 2)
return result[n];
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
int main()
{
int n;
cin >> n;
cout << Fibonacci(n) << endl;
return 0;
}
分析：时间复杂度约为 O（2 ^ n）。当然 Fibonacci 数列还有更快的实现算法。
解法二：从下往上计算
解法一之所以慢是因为重复的计算太多，只要避免重复计算就行了。比如我们可以把已经得到的数列中间项保存起来，如果下次需要计算的时候我们先查找一下，如果前面已经计算过了就不用再次计算了。更简单的办法是从下往上计算，首先根据 f(0) 和 f(1) 算出 f(2)，在根据 f(1) 和 f(2) 算出 f(3) ……依此类推就可以算出第 n 项了。很容易理解，这种思路的时间复杂度是 O(n) 。
源代码如下：
#include <iostream>
using namespace std;
long long Fibonacci_Solution2(unsigned n)
{
int result[3] = {0, 1, 2};
if (n <= 2)
return result[n];
long long fibNMinusOne = 2;
long long fibNMinusTwo = 1;
long long fibN = 0;
for(unsigned int i = 3; i <= n; ++ i)
{
fibN = fibNMinusOne + fibNMinusTwo;
fibNMinusTwo = fibNMinusOne;
fibNMinusOne = fibN;
}
return fibN;
}
int main()
{
unsigned int n;
cin >> n;
cout << Fibonacci_Solution2(n) << endl;
return 0;
}
分析：时间复杂度为 O（n）。
特别注意：
下面介绍一种时间复杂度是 O(logn) 的方法计算 Fibonacci 数列。（目前还没有修改适用于上面的问题）在介绍这种方法之前，先介绍一个数学公式：
Fibonacci 数列公式
因而计算 f(n) 就简化为了计算矩阵的 (n-2) 次方，而计算矩阵的 (n-2) 次方，我们又可以进行分解，即计算矩阵 (n-2) / 2 次方结果的平方，逐步分解下去，由于折半计算矩阵次方，因而时间复杂度为 O(log n) 。
#include <iostream>
#include <cassert>
using namespace std;
///////////////////////////////////////////////////////////////////////
// A 2 by 2 matrix
///////////////////////////////////////////////////////////////////////
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;
};
///////////////////////////////////////////////////////////////////////
// Multiply two matrices
// Input: matrix1 - the first matrix
// matrix2 - the second matrix
//Output: the production of two matrices
///////////////////////////////////////////////////////////////////////
Matrix2By2 MatrixMultiply
(
const Matrix2By2& matrix1,
const Matrix2By2& matrix2
)
{
return Matrix2By2(
matrix1.m_00 * matrix2.m_00 + matrix1.m_01 * matrix2.m_10,
matrix1.m_00 * matrix2.m_01 + matrix1.m_01 * matrix2.m_11,
matrix1.m_10 * matrix2.m_00 + matrix1.m_11 * matrix2.m_10,
matrix1.m_10 * matrix2.m_01 + matrix1.m_11 * matrix2.m_11);
}
///////////////////////////////////////////////////////////////////////
// The nth power of matrix
// 1 1
// 1 0
///////////////////////////////////////////////////////////////////////
Matrix2By2 MatrixPower(unsigned int n)
{
assert(n > 0);
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;
}
///////////////////////////////////////////////////////////////////////
// Calculate the nth item of Fibonacci Series using devide and conquer
///////////////////////////////////////////////////////////////////////
long long Fibonacci_Solution3(unsigned int n)
{
int result[2] = {0, 1};
if(n < 2)
return result[n];
Matrix2By2 PowerNMinus2 = MatrixPower(n - 1);
return PowerNMinus2.m_00;
}
int main()
{
unsigned int n;
cin >> n;
cout << Fibonacci_Solution3(n) << endl;
return 0;
}
参考资料：《编程之法》The Art of Programming By July
斐波那契数列时间复杂度分析
