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;
}

运行界面如下：

赞 (0)

相关推荐

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

    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 <

  • Java青蛙跳台阶问题的解决思路与代码

    Java青蛙跳台阶问题的解决思路与代码

    问题描述 一只青蛙一次可以跳上1级台阶,也可以一次跳上2级台阶,请问跳上n级台阶,该请娃一共有多少种跳法? 解决思路 ①如果只有1级台阶,那显然只有一种跳法. ②如果有2级台阶,那么就有2种跳法,一种是分2次跳.每次跳1级,另一种就是一次跳2级. ③如果台阶级数大于2,设为n的话,这时我们把n级台阶时的跳法看成n的函数,记为,第一次跳的时候有2种不同的选择:一是第一次跳一级,此时跳法的数目等于后面剩下的n-1级台阶的跳法数目,即为,二是第一次跳二级,此时跳法的数目等于后面剩下的n-2级台阶的跳法

  • PHP利用header跳转失效的解决方法

    本文实例讲述了PHP利用header跳转失效的解决方法,分享给大家供大家参考.具体方法分析如下: 一.问题: 今天header(\"Location: $url\"),以往跳转总是可以的,今天却不动,只是输出结果,以往自己要确认检查,$url的值获取的是否正确,所以在前面加了echo $url:来调试用,结果就导致了header函数的无效. 二.解决方法: 在PHP中用header("location:test.php")进行跳转要注意以下几点: 1.locatio

  • Android 表情面板和软键盘切换时跳闪问题的解决方法

    Android 表情面板和软键盘切换时跳闪问题的解决方法

    现在很多应用都会在让用户输入各种文本信息的时候同时多提供一个表情面板,这样就会出现一个问题,即表情面板的跳闪问题要输入文本信息,那固然是需要弹出软键盘,在软键盘显示的情况下,此时如果要切换显示出表情面板,由于表情面板不可能和用户的软键盘高度恰好一样,此外由于控件的上下移位,就会出现表情面板的跳闪现象 在点击切换按钮的时候,表情面板会先向上跳,然后再往下移,这样就会带来很差的用户体验,效果如下图所示: 这里提供一个解决方案,使软键盘和表情面板可以很自然地切换,效果如下图所示: 解决思路主要是这样:

  • 微信小程序出现wx.navigateTo页面不跳转问题的解决方法

    微信小程序出现wx.navigateTo页面不跳转问题的解决方法

    本文实例讲述了微信小程序出现wx.navigateTo页面不跳转问题的解决方法.分享给大家供大家参考,具体如下: 今天在做微信小程序的时候,做的商品购买流程.流程是这样的: 商品展示-->商品详情-->下单页面-->下单详情页面-->支付结果页面-->跳转订单详情页面. 但是在支付成功之后,点击按钮跳转,发现怎么也跳转不了到订单详情页面,前后log都能打印出来,证明已经执行了wx.navigateTo方法,但是跳转不成功,而且,坑爹的是也不报错. 翻看微信小程序开发文档,参考

  • vim配置go语言语法高亮问题的解决方法

    操作系统 : CentOS7.3.1611_x64 go 版本 : go1.8.3 linux/amd64 vim版本 :version 7.4.160 vim配置go语言语法高亮的问题已经遇到过好几次了,每次都去查找太麻烦,这里总结下. 安装git: yum install git 安装vim-go : cd ~ mkdir .vim cd .vim mkdir autoload plugged cd plugged git clone https://github.com/fatih/vim

  • c语言内存泄漏严重的解决方法

    摘要:通过介绍内存泄漏问题原理及检视方法,希望后续能够从编码检视环节就杜绝内存泄漏导致的网上问题发生. 1. 前言 最近部门不同产品接连出现内存泄漏导致的网上问题,具体表现为单板在现网运行数月以后,因为内存耗尽而导致单板复位现象.一方面,内存泄漏问题属于低级错误,此类问题遗漏到现网,影响很坏:另一方面,由于内存泄漏问题很可能导致单板运行固定时间以后就复位,只能通过批量升级才能解决,实际影响也很恶劣.同时,接连出现此类问题,尤其是其中一例问题还是我们老员工修改引入,说明我们不少员工对内存泄漏问题认

  • window.location.href IE下跳转失效的解决方法

    复制代码 代码如下: <a href="javascript:void(0)" >GoNext</a> $("a").click(function(){ window.location.href = "xxx.html"; }) 代码如上,在IE下,特别是在IE6中,点击超链接之后,浏览器并没有发生跳转行为. 原因可能是因为在href中的javascript:void(0)阻止的事件行为,解决方法如下: 1.在onclic

  • A标签触发onclick事件而不跳转的多种解决方法

    在web页面开发时,我们经常会遇到下列情况: 1.一个标签仅仅是要触发onclick行为: 2.表现上要有鼠标的pointer指针显示,或者其他类似a标签的视觉效果. 比如执行删除操作时,为了避免误操作,我们要弹出对话框让用户确定是否删除.因此我们经常会用链接<a></a>形式代替<button> 触发onclick事件. 代码如下: 复制代码 代码如下: <script type="text/javascript"> function

  • 易语言无法定位链接器解决方法

    易语言开发环境的诞生,影响了众多编程爱好者的关注的追捧.的确,很多编程爱好者在使用易语言的同时产生了很多的困惑,这些困惑很多,比如易语言无法定位链接器. 1.首先,打开易语言,创建一个"Windows窗口程序"空白工程,操作如下: 2.进入窗口界面以后,我们不编写任何的代码,就只有一个空白的窗口.如图: 3.然后,点击工具条中的"运行"按钮或者按下"F5"键运行程序,如图: 4.从运行结果可以看出,程序是没有问题的.那么,我们来静态编译一下,看看

随机推荐