跳台阶问题

题目:

给定一个有N个台阶的楼梯,一个人从下到上开始跳台阶,这个人有两种跳的方式:一次跳一个台阶,一次跳两个台阶;

问:从台阶底端跳到台阶顶端,有多少种跳台阶的方式?

分析:

首先我们考虑最简单的情况。如果只有1个台阶,那么显然只有一种跳法;如果 是2级台阶,那么有2种跳法。对于一个有n级台阶的楼梯来说,我们设跳法为 f(n) ,假如我们先跳1个台阶,则剩下有 n-1 个台阶,跳法为 f(n-1) 次,假如我们先跳2个台阶,则剩下 n-2 阶,跳法为 f(n-2);由此可以推出,对于一个n阶的楼梯,有以下这个跳台阶的公式:

代码如下:

[cpp] view plaincopy

 #include <iostream> 
 using namespace std;  
  
 int JumpStep(int n)  
 {  
  if(n <= 0)  
  return -1;  
  if(n == 1)  
  return 1;  
  if(n == 2)  
  return 2;  
  return JumpStep(n-1)+JumpStep(n-2);  
 }  
 int main()  
 {  
     cout<<"5 step jumps : "<<JumpStep(5)<<endl;  
  return 0;  
 }  

扩展:

当跳台阶的选择多了呢?比如说 每次可以跳3个台阶;按照同样的方法分析,如下公式:

解题代码如下:

[cpp] view plaincopy

 /** 
 题目描述: 
 有N个台阶,一个人从台阶下向上跳台阶,有两种跳的选择 
 1次跳一个台阶,1次跳两个台阶 这两种选择; 
 */ 
 #include <iostream> 
 using namespace std;  
  
 int JumpStep(int n)  
 {  
  if(n <= 0)  
  return -1;  
  if(n == 1)  
  return 1;  
  if(n == 2)  
  return 2;  
  return JumpStep(n-1)+JumpStep(n-2);  
 }  
 int JumpStep3(int n)  
 {  
  if(n <= 0)  
  return -1;  
  if(n == 1)  
  return 1;  
  if(n == 2)  
  return 2;  
  if(n == 3)  
  return 4;  
  return JumpStep3(n-1)+JumpStep3(n-2)+JumpStep3(n-3);  
 }  
 int main()  
 {  
     cout<<"5 step jumps : "<<JumpStep(5)<<endl;  
     cout<<"5 step jumps : "<<JumpStep3(5)<<endl;  
  return 0;  
 }  

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ml

hdu------1281 棋盘游戏(最小覆盖点)

棋盘游戏 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java...

31840
来自专栏机器人网

别让接线这件小事,拉开你与工程师的差距

导线与导线的连接、线头与接线桩的连接,事情小,责任大。本文图文并茂,让你清清楚楚看懂! 导线与导线的连接 导线的连接情况有:单股铜芯导线的直线连接、T字形连接;...

34670
来自专栏xingoo, 一个梦想做发明家的程序员

剑指OFFER之变态跳台阶(九度OJ1389)

题目描述: 一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 输入: 输入可能包含多个测试样例,对...

19480
来自专栏开发与安全

算法:最短路径之弗洛伊德(Floyd)算法

为了能讲明白弗洛伊德(Floyd)算法的主要思想,我们先来看最简单的案例。图7-7-12的左图是一个简单的3个顶点的连通网图。 ? 我们先定义两个二维数组D[3...

89870
来自专栏专知

【代码资源】GAN | 七份最热GAN文章及代码分享(Github 1000+Stars)

【导读】专知团队整理了七份当前最热的GAN相关文章和代码,每篇文章代码均在Github上开源,Stars数量超1000+。

15960
来自专栏非著名程序员

Palette让你的应用风格统一,绚丽多彩

今天这个是Android Material Design系列之Palette,Material Design系列的第五篇文章了,由于最近这个系列文章浏览量比较低...

19180
来自专栏数据结构与算法

点双连通分量与割点

前言 在图论中,除了在有向图中的强连通分量,在无向图中还有一类双连通分量 双连通分量一般是指点双连通分量 当然,还有一种叫做边双连通分量 点双连通分量 对于一个...

38180
来自专栏GIS讲堂

ArcGIS Image Server简介以及OL2中的加载

本文讲述Arcgis Image Server相关以及在OL2中如何加载Arcgis Server发布的影像服务。

12320
来自专栏张善友的专栏

Prism Training Kit 4.0

上周刚刚发布的支持Windows Phone 7的Prism 4.0最终版,Damian, Diego, Guido 和Ezequiel更新了Prism Tra...

192100
来自专栏Python小屋

Python两种方法求解登楼梯问题(京东2016笔试题)

问题:假设一段楼梯共15个台阶,小明一步最多能上3个台阶,那么小明上这段楼梯一共有多少种方法? 解析:从第15个台阶上往回看,有3种方法可以上来(从第14个台阶...

47290

扫码关注云+社区

领取腾讯云代金券