Python实现斐波那契数列与跳台阶变体

本篇记录了斐波那契数列的Python实现：递归与循环两种解法，以及一些化用的题目。

Python实现

递归

按传统的递归方式，简洁、优雅。写出来却是$O(n^2)$的算法

def fibo(n):
	"""肥波那契函数"""
    if n < 3:
    	return 1
    else:
        return fibo(n-1) + fibo(n-2)

$O(n)$的算法

上面“简洁”的算法其实重复算了好多项。比如算fibo(6)，它就算了三个fibo(3)、五个fibo(2)。从理论上分析，只要不多算，那就是$O(n)$的算法——大约是算了n次fibo(n-1) + fibo(n-2)。

思路也很简洁：构建一个循环，在每次循环中，都有两个变量储存下一次循环的fibo(n-1)与fibo(n-2)。当然，循环开始和终止的边界条件是需要注意的。（拿几个数去试一试就行了）

def fibo(n):
	if n < 3:
		return 1
	frist = 1
	second = 1
	third = 1  # 没有这个会怎样？
	count = 3
	while count <= n:
	    third = second + frist
	    frist = second
	    second = third
	    count += 1
	return third

if __name__ == '__main__':  # 测试
	print(fibo(2))  # 1
    print(fibo(6))  # 8

当然，这个算法也有一个简洁的版本，只是不便于拓展和理解：

def fibo(n):
	"""假设输入值为整数，第1项为零。"""
	first, second = 0, 1
	for i in range(2, n + 1)

最后

以上就是义气金毛为你收集整理的Python实现斐波那契数列与跳台阶变体的全部内容，希望文章能够帮你解决Python实现斐波那契数列与跳台阶变体所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。