青蛙跳台阶问题（史上最详细）-阿里云开发者社区

青蛙跳台阶问题（史上最详细）

2022-11-22 148

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 一只青蛙一次最少可以跳 1层台阶，一次最多可以跳 2层台阶，求：该青蛙跳上n 层的台阶总共有多少种跳法？

一、提出背景

一只青蛙一次最少可以跳 1层台阶，一次最多可以跳 2层台阶，求：该青蛙跳上n 层的台阶总共有多少种跳法？

二、分析问题

如上图分析：

一层台阶：1种跳法

两层台阶：2种跳法

三层台阶：3种跳法

四层台阶：5种跳法

…

那么我们可以列一个数列：

1 2 3 5 8 13 21 34…

对这些数字是不是很熟悉？没错，问题其实就是隐含了斐波那契数列的思想

三、搜寻规律

F(1) = 1，F(2) = 2
当 n >= 3 时， F(n) = F(n - 1) + F(n - 2)

程序清单1（递归法）：

public class Test1 {
    public static void main(String[] args) {
        int n = 10;
        for (int i = 1; i <= n; i++) {
            System.out.println(fib(i));
        }
    }
    public static int fib(int n){
        if(n==1 || n==2){
            return n;
        }
        else{
            return fib(n-1)+ fib(n-2);
        }
    }
}
//输出 1 2 3 5 8 13 21 34 55 89

程序清单2（迭代法）：

public class Test2 {
    public static void main(String[] args) {
        int n = 10;
            fib(n);
    }
    public static void fib(int n){
        int a = 1;
        int b = 2;
        for (int i = 1; i <= n; i++) {
            if (i == 1 || i == 2) {
                System.out.println(i);
            } else {
                int c = a + b;
                a = b;
                b = c;
                System.out.println(c);
            }
        }
    }
}
//输出 1 2 3 5 8 13 21 34 55 89