查看原文
其他

356,青蛙跳台阶相关问题

山大王wld 数据结构和算法 2021-01-30

问题一:

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


我们来分析一下:

当n等于1的时候,只需要跳一次即可,只有一种跳法,记f(1)=1

当n等于2的时候,可以先跳一级再跳一级,或者直接跳二级,共有2种跳法,记f(2)=2

当n等于3的时候,他可以从一级台阶上跳两步上来,也可以从二级台阶上跳一步上来,所以总共有f(3)=f(2)+f(1);

同理当等于n的时候,总共有f(n)=f(n-1)+f(n-2)(这里n>2)种跳法。

所以大家一看就知道这就是个斐波那契数列,只不过有一点不同的是斐波那契数列一般是以1,1,2,3,5,8,13……开始的,而我们这是以1,2,3,5,8,13……开始的,少了最前面的一个1。最代码很简单

1public static int f(int n) {
2    if (n < 3)
3        return n;
4    return f(n - 1) + f(n - 2);
5}

我们以计算f(6)为例画个图看一下计算的过程

我们看到递归会重复计算已经计算过的值,效率明显不是很高,我们还可以把计算过的值储存起来,防止重复计算,我们来看下代码

1private static int f2(int n, HashMap<Integer, Integer> map) {
2    if (n < 3return n;
3    if (map.containsKey(n))
4        return map.get(n);
5    int first = f2(n - 1map);
6    int second = f2(n - 2map);
7    int sum = first + second;
8    map.put(n, sum);
9    return sum;
10}

我们还可以把递归改为非递归的形式,看下代码

1private static int f3(int n) {
2    if (n < 3)
3        return n;
4    int first = 1, second = 2, sum = 0;
5    while (n-- > 2) {
6        sum = first + second;
7        first = second;
8        second = sum;
9    }
10    return sum;
11}

上面3种方式都可以实现青蛙跳台阶问题,那么哪种效率更高呢,我们来找个比较大的数据测试一下

1public static void main(String[] args) {
2    int step = 45;
3    long time = System.nanoTime();
4    System.out.println(f(step));
5    System.out.println("代码优化前时间:" + (System.nanoTime() - time));
6    time = System.nanoTime();
7    System.out.println(f2(stepnew HashMap<Integer, Integer>()));
8    System.out.println("代码优化后时间:" + (System.nanoTime() - time));
9    time = System.nanoTime();
10    System.out.println(f3(step));
11    System.out.println("代码非递归时间:" + (System.nanoTime() - time));
12}

来看一下运行的时间

11836311903
2代码优化前时间:2221741900
31836311903
4代码优化后时间:108000
51836311903
6代码非递归时间:17600

我们看到递归优化之前运行时间是非常长的,优化之后时间大幅下降,但对于非递归来说又稍逊色了一些。


问题二:

一只青蛙一次可以跳上一级台阶,也可以跳上二级台阶……,也可以跳n级,求该青蛙跳上一个n级的台阶总共需要多少种跳法。


我们来分析一下

一只青蛙要想跳到n级台阶,可以从一级,二级……,也就是说可以从任何一级跳到n级,

所以递推公式我们很容易就能想到

f(n)=f(n-1)+f(n-2)+……+f(2)+f(1)+f(0);最后这个f(0)是可以去掉的,因为0级就相当于没跳,所以f(0)=0;

然后我们把f(0)去掉在转换一下:

f(n-1)=f(n-2)+f(n-3)+……+f(2)+f(1);

所以f(n)=f(n-1)+f(n-1)=2*f(n-1);他是一个等比数列,且f(1)=1;

我们我们可以得出f(n)=2^(n-1);代码如下

1private static int f4(int n) {
2    if (n == 1)
3        return 1;
4    return f4(n - 1) * 2;
5}

或者还可以改为非递归的

1private static int f5(int n) {
2    if (n == 1)
3        return 1;
4    return 1 << (n - 1);
5}


问题三:

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


这道题我们要分开讨论:

1,如果n<=m;因为只能往上跳不能往下跳,所以大于n的都不可以跳,如果跳了就直接超过了,只能跳小于等于n的数字,那么这个问题就直接退到问题2了。

2,如果n>m;我们要想跳到n级台阶,我们可以从n-1级跳一步上来,或者从n-2级跳两步上来……,或者从n-m级跳m步上来,所以我们可以找出递归公式

 f(n) =  f(n-1) + f(n-2) + f(n-3) + ... + f(n-m);

进一步可以推出:

f(n-1) =   f(n-2) + f(n-3) + ... + f(n-m) + f(n-m-1);

化简结果为:

f(n) = 2f(n-1) - f(n-m-1);(n>m)

所以代码我们要分为两部分,一部分是n>m,另一部分是n<=m,我们来看下代码

1public static int f6(int n, int m) {
2    if (n <= 1)
3        return 1;
4    //总台阶大于跳的最高级台阶
5    if (n > m)
6        return 2 * f6(n - 1, m) - f6(n - 1 - m, m);
7    //回退到上面的问题二了
8    return 2 * f6(n - 1, n);
9}


斐波那契数列又称黄金分割数列,他有很多的特性,比如兔子的繁殖,他的通项公式如下

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存