数据结构算法每日一练(三)青蛙跳台阶

数据结构算法每日一练(三)青蛙跳台阶

题目:一只青蛙一次可以跳上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]

上一篇:C++语言导学 第三章 模块化 - 3.1 引言


下一篇:C51单片机_day_01(定时器和中断系统)