递归之台阶问题

跳台阶

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

当n=1时,次数f(n)=1。
当n=2时,次数f(n)=2。(11或2)
当n>2时,当前一步可以跳一级,也可以跳两级,次数f(n)=f(n-1)+f(n-2)。

实现代码

class Solution {
public:
    int jumpFloor(int number) {
        if (number <= 2)
            return number;
        else
            return jumpFloor(number - 1) + jumpFloor(number - 2);
    }
};

变态跳台阶

一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

题目描述

一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路

当台阶数为n时,可以分为以下步骤来完成:
设第一次跳的台阶数为s,跳台阶方式数为T,则:
(1)s=1时,T(n) = T(n-1)
(2)s=2时,T(n) = T(n-2)
.
.
.
(n)s=n时,T(n) = T(0) = 1
所以总的跳台阶方式数T可以表示为:
T(n) = T(0) + T(1) + T(2) + … + T(n-1)
由于T(0) = T(1) = 1,所以T(n) = 2^(n-1)

实现代码

class Solution {
public:
    int jumpFloorII(int number) {
        return pow(2, number - 1);
    }
};
时间: 2024-12-23 18:38:37

递归之台阶问题的相关文章

使用C++递归求解跳台阶问题_C 语言

题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级.求总共有多少总跳法? 分析: 也是比较基础的题目,通过递归可以方便的求解. 用Fib(n)表示青蛙跳上n阶台阶的跳法数,青蛙一次性跳上n阶台阶的跳法数1(n阶跳),设定Fib(0) = 1:        当n = 1 时, 只有一种跳法,即1阶跳:Fib(1) = 1;        当n = 2 时, 有两种跳的方式,一阶跳和二阶跳:Fib(2) = Fib(1) + Fib(0) = 2;        当n = 3

递归与迭代

1.递归 当函数用自身来定义时就称为是递归(recursive)的. 递归必须满足四个基本法则: (1).基本情形:必须给出基准情况,不用递归就能求出,用于终止递归运算: (2).不断推进:对于那些要被递归求解的情形,递归调用必须能够朝着一个基准情形推进: (3).设计法则:假设所有的递归调用都能运行: (4).合成效益法则:在求解一个问题的同一个实例时,切勿在不同的递归调用中做重复性的工作. 2.迭代 迭代就是利用变量的原值推算出变量的一个新值. 若递归是自己调用自己的话,迭代就是自己不停的调

问一道acm题目,下楼梯递归的

问题描述 问一道acm题目,下楼梯递归的 下楼梯查看 提交 统计 提问总时间限制: 1000ms 内存限制: 1000kB描述从楼上走到楼下共有h个台阶,每一步有3种走法:走1个台阶,走2个台阶,走3个台阶.问可走出多少种方案,并打印出具体方案?输入台阶个数h输出各种走法方案及总方案个数样例输入5样例输出plan 1:32plan 2:311plan 3:23plan 4:221plan 5:212plan 6:2111plan 7:131plan 8:122plan 9:1211plan 10

利用简洁的C语言代码解决跳台阶问题与约瑟夫环问题_C 语言

跳台阶问题 题目: 一个台阶总共有 n 级,如果一次可以跳 1 级,也可以跳 2 级. 求总共有多少总跳法,并分析算法的时间复杂度. 分析: 也是比较基础的题目,通过递归可以方便的求解 代码实现如下(GCC编译通过): #include "stdio.h" #include "stdlib.h" int function(int n); int main(void) { int tmp; tmp = function(5); printf("%3d\n&q

2013蓝桥杯【初赛试题】第39阶台阶

第39阶台阶 小明刚刚看完电影<第39级台阶>,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!  站在台阶前,他突然又想着一个问题:  如果我每一步只能迈上1个或2个台阶.先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步.那么,上完39级台阶,有多 少种不同的上法呢?  请你利用计算机的优势,帮助小明寻找答案. 要求提交的是一个整数. 注意:不要提交解答过程,或其它的辅助说明文字.   思路:(原先用斐波那契额真是大错特错.....)这一题的重点是偶数步(先迈左右脚是

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 <

php通过递归方式复制目录和子目录的方法

 这篇文章主要介绍了php通过递归方式复制目录和子目录的方法,涉及php递归及目录操作的技巧,具有一定参考借鉴价值,需要的朋友可以参考下     本文实例讲述了php通过递归方式复制目录和子目录的方法.分享给大家供大家参考.具体实现方法如下: ? 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 <?php function recurse_copy($src,$dst){ $dir = opendir($src); @mkdir($dst); while(fa

不用递归实现论坛树型结构的算法

递归|树型结构|算法 <jsp:useBean id="mybbs" scope="session" class="netzero.mydb" /> <%@ page contentType="text/html;charset=gb2312" %> <%@ page import="java.io.*" %> <%@ page import="java.

java中父类与子类, 不同的两个类中的因为构造函数由于递归调用导致栈溢出问题

/* 对于类中对成员变量的初始化和代码块中的代码全部都挪到了构造函数中, 并且是按照java源文件的初始化顺序依次对成员变量进行初始化的,而原构造函数中的代码则移到了构造函数的最后执行 */ import static java.lang.System.out; public class PersonDemo { public static void main(String[] args) { //*********测试父类与子类之间的循环调用的问题 out.println("main1&quo