Fibonacci

题目 我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？ 比如n=3时，2 * 3的矩形块有3种覆盖方法： ()[../images/offer10.png] 详解 每次使用两个变量a，b来计算下一个数的值sum，然后a，b，sum分别是斐波那契数列中的三个数，那么就令a=b，b=sum，这样a和b就往下移动了一个位置，再计算sum就是第4个数了，重复这个过程即可。 target = 1时，1种 target = 2时，2种 target = 3时，3种 target = 4时，5种 target = n …

题目 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 详解 关于本题，前提是n个台阶会有一次n阶的跳法。分析如下： f(1) = 1 f(2) = f(2-1) + f(2-2) //f(2-2)表示2阶一次跳2阶的次数。 f(3) = f(3-1) + f(3-2) + f(3-3) … f(n) = f(n-1) + f(n-2) + f(n-3) + … + f(n-(n-1)) + f(n-n) 说明： 这里的f(n)代表的是n个台阶有一次1,2,…,n阶的跳法数。 n=1时，只 …

题目 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 详解 一次1阶或者2阶的跳法： a. 如果两种跳法，1阶或者2阶，那么假定第一次跳的是一阶，那么剩下的是n-1个台阶，跳法是f(n-1); b. 假定第一次跳的是2阶，那么剩下的是n-2个台阶，跳法是f(n-2) c. 由a\b假设可以得出总跳法为: f(n) = f(n-1) + f(n-2) d. 然后通过实际的情况可以得出：只有一阶的时候 f(1) = 1 ,只有两阶的时候可以有 f(2) = 2 e. 可以发现最终得出的是一个斐波那契数列： | 1, (n=1) …

题目 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 斐波那契数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… , 这个数列从第3项开始，每一项都等于前两项之和。 JS实现 //递归实现 const Fibonacci = (n) => { if (n <= 0) { return 0; } if (n === 1) { return 1; } return Fibonacci(n - 1) + Fibonacci(n - 2); }; // …