【剑指Offer】斐波那契数列之青蛙跳台阶

题目问题一一只青蛙一次可以跳上1级台阶也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。问题二一只青蛙一次可以跳上1级台阶也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。分析分析问题一将跳法总数记为f(n)可以知道f(1)1f(2)2。当n2时第一次跳1级的话还有f(n-1)种跳法第一次跳2级的话还有f(n-2)种跳法所以可以推得f(n)f(n-1)f(n-2)即为斐波那契数列。所以用斐波那契的解法来解即可。分析问题二解法一当n1时f(1)1。当n大于1时归纳总结可知跳上n级台阶第一次跳1级的话有f(n-1)种方法第一次跳2级的话有f(n-2)种方法……第一次跳n-1级的话有f(1)种方法直接跳n级的话有1种方法所以可以得到如下公式f(n) f(n-1)f(n-2)......f(1)1 n≥2f(n-1) f(n-2)f(n-3).....f(1)1 n2由上面两式相减可得f(n)-f(n-1)f(n-1)即f(n) 2*f(n-1) (n2)最终结合f(1)和f(2)可以推得f(n)2^(n-1)解法二除了最后一个台阶外其余的木板都有存在和不存在两种可能性所以n-1块木板有2^(n-1)种跳法。代码package com.Fibonacci; //青蛙跳台阶的2种方式 public class FrogJump { public static int FrogJump1(int n){ if(n 0){ return 0; } if(n 1){ return 1; } return FrogJump1(n-1) FrogJump1(n-2); } public static int FrogJump2(int n){ if(n 0){ return 0; } if(n 0){ return 1; } if(n 1){ return 1; } int prePre 0; int pre 1; int result 1; for(int i 2; i n; i){ result prePre pre; prePre pre; pre result; } return result; } public static void main(String[] args){ System.out.println(FrogJump2(3)); System.out.println(FrogJump2(4)); } }package com.Fibonacci; public class HardFrogJump { //递归 public static int HardFrogJump1(int n){ if(n 0){ return 0; } if(n 1) { return 1; } return 2 * HardFrogJump1(n-1); } //迭代 public static int HardFrogJump2(int n){ if(n 0){ return 0; } if(n 1){ return 1; } int pre 1; int result 2; for(int i 2; i n; i){ result 2 * pre; pre result; } return result; } public static void main(String[] args){ System.out.println(); } }