欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

编程:跳台阶问题

程序员文章站 2022-08-21 14:54:09
题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。 对于每次只跳1/2个台阶的情况来说: 1.假设第一次跳1个台阶,则剩下n-1个台阶的所有跳法数f(n-1); 2.假设第一次跳2个台阶,则剩下n-2个台阶的所有跳法数f( ......
  • 题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
 1 public class solution {
 2 
 3     public static int jumpfloor(int target) {
 4         if(target <=0)
 5             return 0;
 6         if(target ==1)
 7             return 1;
 8         if(target==2)
 9             return 2;
10         int one = 1;
11         int two = 2;
12         int result = 0;
13         for(int i = 2; i < target; i++){
14             result = one+ two;
15             one = two;
16             two = result;
17         }
18         return result;
19     }
20 }

对于每次只跳1/2个台阶的情况来说:

1.假设第一次跳1个台阶,则剩下n-1个台阶的所有跳法数f(n-1);

2.假设第一次跳2个台阶,则剩下n-2个台阶的所有跳法数f(n-2);

3.在此特定条件下,可以判断出符合斐波那契数列规律;

4.f(1)=1;f(2)=2;以此进行f(n)=f(n-1)+f(n-2)的计算;

  • 题目描述:一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
    public class solution {
        public int jumpfloorii(int target) {
                    if(target<1)
                return 0;
            if(target==1)
                return 1;
            int num=0;
            for(int i=1;i<target;i++) {
                num+=jumpfloorii(target-i);
            }
            return num+1;
        }
    }

 

  1. 整体思路与第一个问题一致:将f(n)的问题转化为f(n-1)、f(n-2)……的问题
  2. 本题采取递归方法;
  3. 返回num+1的问题尚待补充;