记一道很有意思的算法题 --- 青蛙跳台阶问题

题目背景简介

这是博主最近准备秋招时看的剑指 offer 上的一道题目,题目不是很难,但是我觉得比较有意思,所以发在了博客上面.

题目描述

一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级.....它也可以跳上 n 级,求该青蛙跳上一个 n 级台阶总共有多少种方法

如果哪位路过的朋友觉得这道题比较有意思的话可以暂时先不看下面的分析,自己先尝试一下写这道题.

题目分析

在看到这个题目后,首先想到的应该是斐波那契数列的变形,那么思考这个问题应该从斐波那契数列的方向上着手.
当 n=1 时,f(n)=1,当 n>2 时,可以从以下角度进行考虑,青蛙最后一次上台阶可能是跳了 1-n 中任意一个数的台阶.
如果青蛙最后一步是跳了 1 个台阶的话,那么前面的 n-1 个台阶的跳法就有 f(n-1) 种,如下图:

如果青蛙最后一步跳了 2 个台阶的话,那么前面的 n-2 个台阶的跳法就有 f(n-2) 种,如下图:

依次类推青蛙最后一步跳了 n-1 个台阶的话,那么前面的 1 个台阶跳法等于 f(1),
除此之外还有一种情况就是青蛙一步从最低端跳到了最高点,也就是一步跳了 n 个台阶,在之前方法数目的基础上再次加 1

所以跳到 n 级台阶的方法就有

f(n)=f(n-1)+f(n-2)....+f(1)+1

跳到 n-1 级台阶的方法就有

f(n-1)=f(n-2)....+f(1)+1

用 f(n)-f(n-1),有

f(n)-f(n-1)=f(n-1)

即 f(n)=2f(n-1),又因为 f(1)=1,当 n>=2 时有

f(1)=1,为 2 的 0 次方,也满足上式,所以 上式为通式,

###代码(Java)
由此写出的代码如下:

  
public Integer jumpFloor(int n) {
  if (n <= 0) {
  //错误的无法计算的台阶数目
  // throw new Exception("Error input,The number of steps must be greater than zero");
  return -1;
  } else if (n == 1) {
  return 1;
  } else {
  return 2*jumpFloor(n - 1);
  }
}

要注意两个事情

1. 在这个代码中,由于方法的数目是指数型增长的,所以当 n>=32 时,程序所得的数据就不正常了,因为此时的数据大于 int 的范围,int 的范围[-2^31 , 2^31 -1] 即 [-2147483648,2147483647].
2. 程序的栈大小有限,当递归层数超过一定程度的时候,就会导致栈溢出现象,报错:

Exception in thread "main" java.lang.StackOverflowError

当然在这一题里面,我指定 -Xss1m,栈溢出的时候所求的 n 已经大于 9000 了,数据早就已经超过 int 的范围了.感兴趣的读者可以使用 BigInteger 重写一下代码.