欢迎来到入门教程网!

C语言

当前位置:主页 > 软件编程 > C语言 >

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

来源:本站原创|时间:2020-01-10|栏目: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;
}

运行界面如下:


上一篇:如何判断一个数是否为2的幂次方?若是,并判断出来是多少次方?

栏    目:C语言

下一篇:数据结构课程设计- 解析最少换车次数的问题详解

本文标题:c语言 跳台阶问题的解决方法

本文地址:https://www.xiuzhanwang.com/a1/Cyuyan/4545.html

网页制作CMS教程网络编程软件编程脚本语言数据库服务器

如果侵犯了您的权利,请与我们联系,我们将在24小时内进行处理、任何非本站因素导致的法律后果,本站均不负任何责任。

联系QQ:835971066 | 邮箱:835971066#qq.com(#换成@)

Copyright © 2002-2020 脚本教程网 版权所有