【剑指offer】青蛙跳系列&&斐波拉契

题目1：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项。 n<=39

公式：f(n) = f(n-1)+f(n-2)

显然直接递归容易超时，由此用迭代法，取一个变量存中间值。

public class Solution { public int Fibonacci(int n) { int f1 = 1; int f2 = 1; int curr = 0; if(n <= 0){ return 0; } if(n == 1 || n == 2){ return 1; } for(int i = 3;i <= n;i ++){ curr = f1 + f2; //保存当前值&&f2先不被修改 f1 = f2; f2 = curr; } return curr; } public static void main(String[] args){ System.out.println(new Solution().Fibonacci(3)); } }

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

假设从第n级考虑，那么就是踩一级到n的方法加上，踩两级到n的方法，也就是f(n)=f(n-1)+f(n-2)，斐波拉契公式。 上面题目的变形，唯一的区别就是，跳二台阶的时候有两种方法。

public class Solution { public int JumpFloor(int n) { int f1 = 1; int f2 = 2; int curr = 0; if(n <= 0){ return 0; } if(n == 1 || n == 2){ return n; } for(int i = 3;i <= n;i ++){ curr = f1 + f2; f1 = f2; f2 = curr; } return curr; } public static void main(String[] args){ System.out.println(new Solution().JumpFloor(4)); } }

题目3：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 有规律： 第n级： f(n) = f(n-1)+f(n-2)+f(n-3)+……+f(1) ………. ① 第n-1级：f(n-1) = f(n-2)+f(n-3)+……+f(1) ………. ② ①②两个式子相减得，f(n) = 2*f(n-1) f(n-1) = 2*f(n-2) …… f(2) = 2*f(1) f(1) = 1 带入后的f(n) = 2^(n-1)

public class Solution { public int JumpFloor2(int n) { return 1<<(n-1); //2的幂运算用位移 } public static void main(String[] args){ System.out.println(new Solution().JumpFloor2(4)); } }