青蛙跳台阶算法分析


青蛙跳台阶问题在面试中经常会被问到,如果你之前没听过这个算法问题,那么在面试短时间内能给出完整的答案还是有一定的难度的,但是其实也并不算很难,看完这篇文章,相信你会恍然大悟的。



一只青蛙一次可以跳一级台阶,也可以一次跳两级台阶,现在有 n 级台阶,问青蛙一共有多少种跳法?



咋一看到这种问题,好像没有什么思路,不知道从哪里着手分析,那么我们就从最简单的情况开始分析,假如 n = 1,即一共只有一级台阶,显然一共就只有一种跳法,假如 n = 2,一共有两级台阶,那么可以每次跳一级跳两次,或者也可以一次跳两级,也就是说一共有两种跳法。n 越大跳法就越多,但是我们可以发现一个规律,就是把 n 拆分成各个比他小的数来分析,这里有点像分而治之的思想,即把大问题划分为若干个小问题来处理,最后再把小问题汇总去解决大问题。



我们先令 f(n) 为 n 级台阶的总跳法数,那么第一次如果选择跳一级的话,那么剩下的 n-1 级台阶的跳法数就为 f(n-1),如果第一次跳两级的话,那么剩下的 n-2 级台阶的跳法就是 f(n-2),然后再回到题目中要求来看,青蛙一次只能挑一级或两级,也就是说刚刚列举的这两种情况的和就是青蛙一共有多少种跳法,所以 f(n) = f(n-1) + f(n-2)。到了这一步,我们不难看出,这其实就是数学中的斐波拉契数列,看到这里应该会有恍然大悟的感觉了,如果还没明白的话,请回到文章开头再次认真看。



问题的思路已经找到了,接下来我们就用 python 来实现这个斐波拉契数列吧。关于斐波拉契数列的实现,我这里用了两种方式,一种是递归,一种是循环,其中一旦 n 数据较大时递归的效率是非常非常差的,大家可以用 n = 100 简单试一下就知道有多慢了,估计没个 10 分钟计算机是算不出来的,其时间复杂度为 O(2^n),随 n 的增加时间复杂度成指数级增长,因为在这递归过程中,我们在不断重复计算 f(n-1) 和 f(n-2) 的值,即每计算数列中的某个数,都会从 1 重新开始计算,这样的效率能不慢么,所以递归这种方式不可取。用一个简单的循环效率一下子就上来了,时间复杂度为 O(n)。 


# 斐波拉契数列实现方法一:递归 def fibonacci(n):     if n > 2:
        return fibonacci(n-1) + fibonacci(n-2)
    else:
        return n    

print(fibonacci(10)) 


# 斐波拉契数列实现方法二:for循环 def fibonacciFor(n):     for i in range(3,n+1):
        n = (i-1) + (i-2)
    return n

print(fibonacciFor(4)) 

最后大家还可以继续思考下,如果题目条件改为一次可以跳一级,也可以一次跳 n 级,那么总共的跳法又是多少呢?这里直接给出答案吧,f(n) = 2^(n-1),这个结果是数学公式换算推导出来的,大家可以尝试去验证下。


关键词: 台阶算法

网友留言(0条)

发表评论