题目:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
(1)请用递归的方式求 n 级的台阶总共有多少种跳法: int jumpFloor(int n);
(2)给出此递归函数的时间复杂度。
解析:
当n = 0, jumpFloor(0) = 0;
当n = 1, jumpFloor(1) = 1;
当n = 2, jumpFloor(2) = 2;
当n > 3, jumpFloor(n) = jumpFloor(n - 1) + jumpFloor(n - 2);
#include <iostream> using namespace std; int jumpFloor(int n) { if (n < 3) return n; else return jumpFloor(n - 1) + jumpFloor(n - 2); } int main() { int n; cin >> n; int res = jumpFloor(n); cout << res << endl; return 0; }时间复杂度为递归调用 O ( 2 n ) O(2^n) O(2n)
该题为斐波那契数列,分析方法与其一致。数据结构算法每日一练(一)斐波那契数列
斐波那契数列递推公式 a n = 1 5 [ ( 1 + 5 2 ) n − ( 1 − 5 2 ) n ] a_n=\frac{1}{\sqrt{5}}[(\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n] an=5 1[(21+5 )n−(21−5 )n]