一道爬楼梯问题引发的思考

2020-05-03

A1 用递归解决爬楼梯问题

1
2
3
4
5
6
7
public static int cs(int n){
      if(n <= 3){
          return n;
      }
      return cs(n-1) + cs(n-2);

  }

A2 两个变量实现斐波那契数列

1
2
3
4
5
6
7
8
9
10
11
public static int cs(int n){
       int prev = 0;
       int curr = 0;

       for(int i = 1 ; i<= n; i++){
           int tmp = curr;
           curr = curr+prev;
           prev = tmp;
       }
       return curr;
   }

A3 两个变量解决爬楼梯的问题

1
2
3
4
5
6
7
8
9
10
11
public static int cs(int n){
       int prev = 0;
       int curr = 1;

       for(int i = 1 ; i<= n; i++){
           int tmp = curr;
           curr = curr+prev;
           prev = tmp;
       }
       return curr;
   }

A4 尾递归 实现斐波那契数列

1
System.out.print(cs(3, 0, 1));
1
2
3
4
5
6
7
public static int cs(int n, int ret1, int ret2){
       // 递到底了
       if(n == 0){
           return ret1;
       }
       return cs(n-1, ret2, ret1+ret2);
   }

A5 尾递归解决爬楼梯
这里函数代码和上面并无不同，不同的是调用的时候初始传参的问题，也是这篇文章所思考的问题

1
System.out.print(cs(3, 1, 1));
1
2
3
4
5
6
7
public static int cs(int n, int ret1, int ret2){
        // 递到底了
        if(n == 0){
            return ret1;
        }
        return cs(n-1, ret2, ret1+ret2);
    }

一个典型的斐波那契数列是这样的：

1 1 2 3 5 8

为什么 前两个数字都是1呢？

在A2中为什么curr的初始值是1呢，为什么不是prev是1呢？为什么curr不是2呢？只是因为我们测试后发现这个值是1才能得出正确的结果吗？显然不是这样子的

那么，我们可不可以这么看斐波那契数列

0 1 1 2 3 5 8 （0+1，1+1，1+2）

那爬楼题问题里，我们首先要总结下规律：

image

它是这样的：

1 2 3 5 8

和上面的相比它少了一个1，想套用斐波那契数列的公式的话，我们也给它补全一下

0 1 1 2 3 5 8

少了一个1的初始值，所以，我们给它补上1，相同的道理，如果碰到其他问题，我们可以差多少给它补多少

如有不对，欢迎指正

Tags: 算法 数据结构
java & 0xff →
赏
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助，欢迎点击上方按钮对我打赏

扫描二维码，分享此文章