美文网首页
《剑指offer第二版》面试题10:斐波那契数列/青蛙跳台阶问题

《剑指offer第二版》面试题10:斐波那契数列/青蛙跳台阶问题

作者: castlet | 来源:发表于2020-03-08 12:51 被阅读0次

    题目一:斐波那契数列

    题目描述

    写一个函数,输入n,求斐波那契(Fibonacci)数列的第n项。斐波那契数列定义为:

            | 0, n = 0
     f(n) = | 1, n = 1
            | f(n-1) + f(n-2), n>1
    

    解题思路:

    1. 递归会产生很多重复的计算,这里使用循环的方式。
    2. 根据f(0)和f(1)计算出f(2),再根据f(1)和f(2)计算出f3,以此类推就可以计算出f(n)了。

    代码

    int fibonacci(int n){
        if (n == 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
    
        int f1 = 0;
        int f2 = 1;
        int fn = 0;
        for (int i = 2; i <= n; i++) {
            fn = f1 + f2;
            f1 = f2;
            f2= fn;
        }
        return fn;
    }
    

    题目二:青蛙跳台阶问题

    题目描述

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

    解题思路:

    1. 假设跳到n级台阶的跳法为f(n), 则调到n-1级台阶的跳法为f(n-1),跳到n-2级台阶的跳法为f(n-2)
    2. 要跳到n级台阶,必须是从n-1级再跳一个台阶,或者从n-2级再跳2个台阶,因此f(n) = f(n-1)+ f(n - 2)
    3. 即为斐波那契数列。

    相关文章

      网友评论

          本文标题:《剑指offer第二版》面试题10:斐波那契数列/青蛙跳台阶问题

          本文链接:https://www.haomeiwen.com/subject/musddhtx.html