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

题目题目描述大家都知道斐波那契数列，现在要求输入一个整数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.变态跳台阶一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。每个台阶都可以选择跳或者不跳，最后一个台阶必跳。每个台阶有两种选择，n个台阶有2的n次方种选择。所以一共有2的n-1次跳法。使用位运算function jumpFloorII(number){ return 1<<(–number);}