我要招人

去企业版

首页 > 试题广场 >

青蛙跳台阶算法，每次可以跳1级或两级，请问有n级台阶，有多少

[问答题]

青蛙跳台阶算法，每次可以跳1级或两级，请问有n级台阶，有多少种算法，递归和非递归如何写

牛客5380090号

public int JumpFloor(int target) {

    if(target==0)
        return 1;
    if(target==1)
        return 1;
    else{
        return JumpFloor(target-1)+JumpFloor(target-2);
    }
}

编辑于 2017-08-06 16:45:25 回复(0)

更多回答

julian-wang

本质是斐波那契，思路：用f(n)表示n级台阶的算法数，因为“每次可以跳1级或两级”，所以

f(n) = f(n-1) +f(n-2)

代码：

#include <iostream>

using namespace std;

int Fibonacci( int n)

{

int *F= new int [n];

F[ 0 ]= 0 ;

F[ 1 ]= 1 ;

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

F[i]=F[i- 1 ]+F[i- 2 ];

return F[n];

}

int main(){

int num;

std::cin >> num;

std::cout << Fibonacci(num);

return 1 ;

}

发表于 2015-01-06 23:44:38 回复(2)

菜鸟葫芦娃

递归实现：

public int JumpFloor(int n)
     {
         if (n < 0)
             return 0;
         int[] fibArry = { 0, 1, 2 };
         if (n < 3)
             return fibArry[n];
         return JumpFloor(n - 1) + JumpFloor(n - 2);
     }

非递归实现：

public int JumpFloor(int n)
        {
            if (n < 0)
                return 0;
            int[] fibArry = { 0, 1,2 };
            if (n < 3)
                return fibArry[n];
            long nReturn = 0L;
            long fibFirst=1L;
            long fibTow=2L;
            for (int i = 3; i <= n; i++)
            {
                nReturn = fibFirst + fibTow;
                fibFirst=fibTow ;
                fibTow = nReturn;
            }
            return nReturn;
        }

发表于 2015-04-17 09:02:02 回复(4)

_ooops_

其实这道题，就是在考察斐波那契数列的问题，但是递归下的斐波那契数列可能存在有溢出等问题，所以针对斐波那契数列来说的，非递归的写法要优于递归的写法，下面给出递归和非递归的两种写法：
递归：

#include<stdio.h>
int fib(int n)
{
    if (n <= 2)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}
int main()
{
    int n = 0;
    int ret = 0;
    (void)scanf("%d", &n);
    ret = fib(n);
    printf("%d", ret);
    return 0;
}

非递归：

#include<stdio.h>
int main()
{
    int a = 1;
    int b = 1;
    int c = 1;
    int n = 0;
    (void)scanf("%d", &n);
    while (n >= 3)
    {
        c = a + b;
        a = b;
        b = c;
        n--;
    }
    printf("%d", c);
    return 0;
}

发表于 2020-01-27 13:32:37 回复(0)

华电美男

本质是斐波那契数列

递归：

def Fibonacci(n):
    if n<=1:
        return n
    return Fibonacci(n-1)+Fibonacci(n-2)

循环：

def Fibonacci(n):
    a=0;b=1
    if n<=1:
        return n
    for i in range(n):
        a,b=b,a+b
    return a

发表于 2020-07-01 16:14:44 回复(0)

AI风口的猪

def fib(n):
    if n <=2:
        return n
    else:
        return fib(n-1) + fib(n-2) 
if __name__=="__main__":
    n=input("Enter a num:")
    n=int(n)  
    print(fib(n))

发表于 2018-04-21 16:39:21 回复(0)

Shmily

function getC($n,$start=1){
    $num = 1;
    for(;$start<=$n;$start++){
        $num *= $start;
    }
    return $num;
}
function getJump($x,$y){
    //echo $x.":".$y;
    if($x<=0 || $y <= 0){
        if($x <= 0 && $y <= 0){
            return 0;
        }
        return 1;
    }
    $n = $x +$y;
    $num = getC($n,$n-$y+1)/getC($y);
    return $num;
}
function jumpType($n){
    $count = 0;
    for($x=0;$x<=$n;){
        if(($n - $x)%2 == 0){
            $y = ($n - $x)/2;
            $num = getJump($x,$y);
            //echo "=".$num."<br/>";
            $count += $num;
            $x = $x + 2;
        }else{
            $x = $x + 1;
        }
    }
    return $count;
}
echo jumpType(11);

编辑于 2015-06-20 16:35:47 回复(0)

已注销

   public class Solution {  

        public int JumpFloor(int target) {  
       if (target <=0)  
         return 0;  
       if(target ==1)  
         return 1;  
       if(target == 2)  
         return 2;  
             

        return JumpFloor(target-1)+JumpFloor(target-2);  
       }  
   }  

发表于 2015-06-05 17:35:08 回复(0)

牛客785026号

│#include <stdio.h>
│
│int jump(int n)
│{
│
│ if(n==1) return(1);
│ if(n==2) return(2);
│
│ return( jump(n-1)+jump(n-2) );
│
│
│}
│
│main()
│{
│
│int n;
│
│ scanf("%d",&n);
│
│ printf("\n\rn=%d, m=%d",n,jump(n) );
│
│}

发表于 2015-04-22 09:04:33 回复(0)

提交观点

问题信息

动态规划百度递归

上传者：四人组

难度：

9条回答 11收藏 18204浏览

青蛙跳台阶算法，每次可以跳1级或两级，请问有n级台阶，有多少

问题信息

热门推荐

相关试题