【剑指offer】8.斐波那契数列

sf_wangchong 发布于2019-08-23 14:50 / 2067人阅读

摘要：题目题目描述大家都知道斐波那契数列，现在要求输入一个整数，请你输出斐波那契数列的第项从开始，第项为。基本思路这道题在剑指中实际是当作递归的反例来说的。明显也符合斐波那契数列的规律矩形覆盖我们可以用的小矩形横着或者竖着去覆盖更大的矩形。

题目

题目描述
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。

基本思路

这道题在剑指offer中实际是当作递归的反例来说的。

递归的本质是吧一个问题分解成两个或者多个小问题，如果多个小问题存在互相重叠的情况，那么就存在重复计算。

f(n) = f(n-1) + f(n-2) 这种拆分使用递归是典型的存在重叠的情况，所以会造成非常多的重复计算。

另外，每一次函数调用爱内存中都需要分配空间，每个进程的栈的容量是有限的，递归层次过多，就会造成栈溢出。

递归是从最大数开始，不断拆解成小的数计算，如果不去考虑递归，我们只需要从小数开始算起，从底层不断往上累加就可以了，其实思路也很简单。

代码

function Fibonacci(n)
{
    if(n<=1){
        return n;
    }
    let i = 1;
    let pre = 0;
    let current = 1;
    let result = 0;
    while(i++ < n){
        result = pre + current;
        pre = current;
        current = result;
    }
    return result;
}

扩展 1.跳台阶：

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

找规律：

跳三级台阶等于跳两级台阶的跳法+跳一级台阶的跳法。

跳四级台阶等于跳三级台阶的跳法+跳二级台阶的跳法。

明显也符合斐波那契数列的规律

function jumpFloor(n)
{
    if(n<=2){
        return n;
    }
    let i = 2;
    let pre = 1;
    let current = 2;
    let result = 0;
    while(i++ < n){
        result = pre + current;
        pre = current;
        current = result;
    }
    return result;
}

3.矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

跟上面跳台阶那个题很像。

假设有8个块

第1块竖着放，后面还剩7块，共f(7)种方法。

第1块横着放，后面还剩6块，共f(6)种方法。

即f(8)=f(6)+f(7)

f(n)=f(n-1)+f(n-2)

function rectCover(n)
{
    if(n<=2){
        return n;
    }
    let i = 2;
    let pre = 1;
    let current = 2;
    let result = 0;
    while(i++ < n){
        result = pre + current;
        pre = current;
        current = result;
    }
    return result;
}

3.{{BANNED}}跳台阶

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

每个台阶都可以选择跳或者不跳，最后一个台阶必跳。

每个台阶有两种选择，n个台阶有2的n次方种选择。

所以一共有2的n-1次跳法。

使用位运算

function jumpFloorII(number)
{
    return 1<<(--number);
}

GPU云服务器云服务器波那契数列解斐波剑指 offer

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/101222.html

剑指offer(javascript版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。例如输入前序遍历序列和中序遍历序列，则重建二叉树并返回。 1.二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数...

imtianx 2019-08-20 15:20 评论0 收藏0
剑指offer中的算法题(PHP版)

摘要：二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。解法有两种，一种是递归法，一种是迭代法但是递归法计算的时间复杂度是以的指数的方式递增的，如果面试中千万不要用递归法，一定要用迭代法。二维数组中的查找在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和...

big_cat 2019-06-27 15:43 评论0 收藏0
数据结构和算法类面试题javascript代码实现

摘要：正文面试题重建二叉树题目输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。前序遍历序列为，中序遍历序列，。确定了左右子树后递归处理。方法方法面试题在时间删除链表结点。写在前面本文的题目均来自于剑指offer中的题目，题目序号保持了书中的题目序号，由于某些题目并不适合于javascript这种语言，所以这些题目就没有写在本篇博客中，因此会出现题目序号的中断。正文面试题6：...

Dean 2019-08-22 10:39 评论0 收藏0
算法记录 >> 斐波那契数列

摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？每个人都知道那就是学习、特别是算法没有任何捷径可走。在这记录平时自己工作和生...

robin 2019-08-16 17:52 评论0 收藏0