本文主要是介绍笔试面试题目：青蛙跳台与斐波那契数列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天周末，刚好也是程序员节，来聊一下青蛙跳台与斐波那契数列。很多年前，我在面试T公司的W部门时，遇到了青蛙跳台问题。
问题如下：
有n阶台阶，青蛙每次只能跳跃1阶或2阶，求跳上n阶台阶的方法数。
(1) 当n > 1000时，写程序求解。
(2) 求通项公式。
不得不说，要在面试现场解决这个问题，还是有一定难度的。记f(n)为青蛙跳上n阶台阶的方法数，则有：
f(1) = 1
f(2) = 2
f(n + 2) = f(n + 1) + f(n)
这是一个经典的斐波那契数列，直接递归就可以求解：
func fib(n int) int {if n <= 0 {// 异常处理}if n == 1 || n == 2 {return n}return fib(n - 1) + fib(n - 2)
}但是，当n>1000时，f(n)是一个非常大的值，显然不能用上述方法。处理大数问题，可以参考之前的文章：笔试面试题目：1000的阶乘问题。
那么，如何求通项公式呢？方法很多，比如特征根法、矩阵法、生成函数法、Z变换法。
下面给出一种高中生就能看懂的方法，即构造数列法：
斐波那契数列的应用非常广泛，青蛙跳台、兔子繁殖、地面铺砖等问题，都是典型的斐波那契数列问题。
周末愉快，程序员节愉快。祝大家拿到心仪的offer.
这篇关于笔试面试题目：青蛙跳台与斐波那契数列的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
