Description
大家都知道斐波那契数列,现在要求输入一个整数n,请你输出斐波那契数列的第n项(从0开始,第0项为0)。 n<=39
Solutions
当然,教科书上最标准的做法其实是比较低效的:
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
if n == 1:
return 1
return self.Fibonacci(n-1) + self.Fibonacci(n-2)
直接用累加的方式:
# -*- coding:utf-8 -*-
class Solution:
def Fibonacci(self, n):
# write code here
if n <= 0:
return 0
if n == 1:
return 1
f1 = 0
f2 = 1
fn = 0
for i in range(2, n + 1):
fn = f1 + f2
f1 = f2
f2 = fn
return fn
问题延伸
青蛙跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法(先后次序不同算不同的结果)。
这个就是初始值不一样而已,具体分析时利用递归思路来考虑就可以了。跳到下一层台阶的方式有两种,一是从当前台阶跳一步上去,二是从当前台阶的下一个台阶一步跳两层上去,这就是有点儿像斐波那契数的例子了,只是当我们在平底时初始值为1.
# -*- coding:utf-8 -*-
class Solution:
def jumpFloor(self, number):
# write code here
if number <= 1:
return 1
f1 = 1
f2 = 1
fn = 0
for i in range(2, number + 1):
fn = f1 + f2
f2 = f1
f1 = fn
return fn
变态版青蛙跳台阶
一只青蛙一次可以跳上1级台阶,也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
这个看起来复杂实则是最简单的了,通过 f(n) 和 f(n-1) 的等式相减,就可以得到递归式,一下就写出来代码了:
# -*- coding:utf-8 -*-
class Solution:
def jumpFloorII(self, number):
# write code here
if number <= 1:
return 1
return 2 * self.jumpFloorII(number-1)
矩阵覆盖
我们可以用 2*1 的小矩形横着或者竖着去覆盖更大的矩形。请问用 n 个 2*1 的小矩形无重叠地覆盖一个 2*n 的大矩形,总共有多少种方法?
# -*- coding:utf-8 -*-
class Solution:
def rectCover(self, number):
# write code here
if number == 0:
return 0
if number == 1:
return 1
if number == 2:
return 2
f1 = 2
f2 = 1
fn = 0
for i in range(3, number+1):
fn = f1 + f2
f2 = f1
f1 = fn
return fn