运维开发网

c语言 跳台阶问题的解决方法

运维开发网 https://www.qedev.com 2020-02-12 15:51 出处:网络 作者: 网络整理
本篇文章是对c语言中跳台阶问题的解决方法进行了详细的分析介绍,需要的朋友参考下
题目:一个台阶总共有n级,如果一次可以跳1级,也可以跳2级。求总共有多少种跳法,并分析算法的时间复杂度。

答:用一个函数f(n)来表示n级台阶总的跳法。

1、只有1个台阶,则f(1) = 1;

2、有2个台阶,则f(2) = 2;

3、当有n个台阶时,如果第一次跳1级,有f(n-1)种跳法,如果第一次跳2级,有f(n - 2)种跳法,即f(n) = f(n-1) + f(n-2)。

即为Fibonacci序列。

复制代码 代码如下:

#include "stdafx.h"

#include <iostream>

using namespace std;

//循环

int TotalStep(int n)

{

    if (n <= 0)

    {

        return 0;

    }

    else if (1 == n || 2 == n)

    {

        return n;

    }

    int first = 1;

    int second = 2;

    int total = 0;

    for (int i = 3; i <= n; i++)

    {

        total = first + second;

        first = second;

        second = total;

    }

    return total;

}

//递归

int RecurTotalStep(int n)

{

    if (n <= 0)

    {

        return 0;

    }

    else if (n == 1 || n == 2)

    {

        return n;

    }

    else

    {

        return RecurTotalStep(n - 1) + RecurTotalStep(n - 2);

    }

}

int _tmain(int argc, _TCHAR* argv[])

{

    cout<<TotalStep(20)<<endl;

    cout<<RecurTotalStep(20)<<endl;

    return 0;

}

运行界面如下:

扫码领视频副本.gif

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号