【剑指offer系列】-10青蛙跳台阶问题（关键字：数学公式推导）

本文主要是介绍【剑指offer系列】-10青蛙跳台阶问题（关键字：数学公式推导），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

青蛙跳台阶问题1：一次只能跳1个或2个台阶。青蛙跳到台阶为n的地方有多少种方式。

一次跳1或2,f(n)表示n个台阶一次跳1或2的可能情况
那么f(n)= 最后一次跳1层到n了 + 最后一次跳2层到n了的情况和
所以 f(n) = f(n-1) + f(n-2)

青蛙跳台阶问题2：一次只能跳1个或2个或3个或···n个台阶。青蛙跳到台阶为n的地方有多少种方式。

f(n) = f(n-1) + f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1
f(n - 1) = f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1
两式相减得到 f(n) = 2 * f(n-1)
带入计算 f(n) = f(n-1) + f(n-2) + … + f(n-m) + … + f(2) + f(1) + 1
= 1 + f(1) + f(2) + … + f(n-m) + … + f(n-2) + f(n-1)
= 1 + f(1) + 2*f(1) + … + 2^{n-m-1} * f(1) + … 2^{n-3} * f(1) + 2^{n-2} * f(1)
= 1 + 1 + 21 + … + 2^{n-m-1} + … 2^{n-3} + 2^{n-2}
= 2^{n-1}

public class Main10
{public static void main(String[] args){Scanner sc = new Scanner(System.in);int n = sc.nextInt();System.out.println(jump1or2(n));System.out.println(jumpany(n));}/***一次只能跳1个或2个或3个或···n个台阶。* @param n* @return*/private static int jumpany(int n){if (n <= 0)return -1;if (n == 1)return 1;if ( n== 2)return 2;return (int)Math.pow(2 , n-1);}/*** 一次跳1或2,f(n)表示n个台阶一次跳1或2的可能情况* @param n* @return*/private static int jump1or2(int n){if (n <= 0)return -1;if ( n == 1)return 1;if (n == 2)return 2;return jump1or2(n-1)+jump1or2(n-2);}
}