面试题10 斐波那契数列

题目一：求斐波那契数列的第n项

思路1：递归思想-效率低，无法通过

# -*- 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)

递归运行结果.png

思路2：利用循环的思想，首先求出f(1),f(2)，保存后依次求解

class Solution:
    def Fibonacci(self, n):
        # write code here
        #循环方法-推荐
        if n == 0:
            return 0
        if n == 1:
            return 1
        small = 0
        big = 1
        for i in range(2,n+1):
            sum_i = small + big
            small = big
            big = sum_i
        return big

题目二：青蛙跳台阶

思路：这道题需要归纳出规律，第一种办法是依次计算前几个结果，发现规律是斐波那契数列。
第二种（暂时没看懂）:在跳第一次时有两种选择，跳一阶的跳法是剩下的n-1台阶数f(n-1);第二种是跳两阶，则跳法是f(n-2),所以f(n)=f(n-1)+f(n-2),因此可以看出是斐波那契数列

代码：

#青蛙跳台阶
class Solution:
   def Jump(self,number):
       if number == 1:
           return 1
       if number ==2:
           return 2
       small = 1
       big = 2
       for i in range(3,number+1):
           sum_i = small+big
           small = big
           big = sum_i
       return big

print(Solution().Jump(10))

题目拓展2：变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

解题思路：由数学归纳法得规律。

解题代码：

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number<=0:
            return 0
        return 2**(number-1)

题目四：矩形覆盖问题如P79所示，我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？ 也是斐波那契数列