0509. 斐波那契数 #
- 标签:数组
- 难度:简单
题目大意 #
描述:给定一个整数 n
。
要求:计算第 n
个斐波那契数。
说明:
- 斐波那契数列的定义如下:
f(0) = 0, f(1) = 1
。f(n) = f(n - 1) + f(n - 2)
,其中n > 1
。
示例:
|
|
解题思路 #
思路 1:递归算法 #
根据我们的递推三步走策略,写出对应的递归代码。
- 写出递推公式:
f(n) = f(n - 1) + f(n - 2)
。 - 明确终止条件:
f(0) = 0, f(1) = 1
。 - 翻译为递归代码:
- 定义递归函数:
fib(self, n)
表示输入参数为问题的规模n
,返回结果为第n
个斐波那契数。 - 书写递归主体:
return self.fib(n - 1) + self.fib(n - 2)
。 - 明确递归终止条件:
if n == 0: return 0
if n == 1: return 1
- 定义递归函数:
思路 1:代码 #
|
|
思路 2:递推算法 #
根据斐波那契的递推公式 f(n) = f(n - 1) + f(n - 2)
,我们可以直接写出对应的递推算法。
思路 2:代码 #
|
|