劍指offer——面試題10 斐波那契數列

文章目錄

• 斐波那契數列
• • 解法1：遞歸（時間複雜度高，無法編譯通過）
  • 解法2：非遞歸
• 青蛙跳台
• • 解法
• 變态跳台階
• • 解法

斐波那契數列

題目：寫一個函數，輸入n，求斐波那契（Fibonacci）數列的第n項。

斐波那契數列的定義如下：

f ( n ) = { 0 n=0 1 n=1 f ( n − 1 ) + f ( n − 2 ) n>1 f(n)= \begin{cases} 0& \text{n=0}\\ 1& \text{n=1}\\ f(n-1)+f(n-2)& \text{n>1} \end{cases} f(n)=⎩⎪⎨⎪⎧​01f(n−1)+f(n−2)​n=0n=1n>1​

解法1：遞歸（時間複雜度高，無法編譯通過）

• 時間複雜度 O ( n 2 ) O(n^2) O(n2)

class solution:
    def fab(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        else:
            return self.fab(n-1) + self.fab(n-2)
           

解法2：非遞歸

• 思路： 從小往上計算，根據f(0)和f(1)算出f(2), f(1)和f(2)算出f(3), 以此類推算出第n項，時間複雜度O(n)

# -*- coding:utf-8 -*-
class Solution:
    def Fibonacci(self, n):
        if n == 0:
            return 0
        if n == 1:
            return 1
        else:
            sum = 0
            a = 0
            b = 1
            while n >1:
                sum = a+b
                # 保留大的數，把小的舍掉
                a = b
                b = sum
                n -= 1
            return sum

        # write code here
           

青蛙跳台

題目描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級。求該青蛙跳上一個n級的台階總共有多少種跳法（先後次序不同算不同的結果）。

解法

• 思路：第一次跳的情況: 若跳1級, 剩下n-1級， 跳法有f(n-1)種；若跳2級， 剩下n-2級， 跳法有f(n-2)種。于是，f(n) = f(n-1) + f(n-2), 這樣就是一個斐波那契數列了

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloor(self, number):
        # write code here
        if number == 1:
            return 1
        
        if number == 2:
            return 2
        
        else:
            j_one = 1
            j_two = 2
            sum = 0
            for i in range(2, number):
                sum = j_one + j_two
                j_one = j_two
                j_two = sum
            return sum
           

變态跳台階

題目描述

一隻青蛙一次可以跳上1級台階，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的台階總共有多少種跳法。

解法

• 思路: 考慮第一次跳的情況：若跳了1級，剩下n-1級， 有f(n-1)種跳法; 跳了2級， 就有f(n-2)種跳法；…; 若跳了n-2級， 有f(2) = 2種， 若跳了n-1級， 有f(1)=1種， 若跳了n級， 有f(0)=1種；

  于是f(n) = f(0) + f(1) + … + f(n-1)

  f(1) = f(0) = 1 = 2^0

  f(2) = f(1) + f(0) = 2 = 2^1

  f(3) = f(2) + f(1) + f(0) = f(2) + f(2) = 2f( 2) = 2^2

  …

  于是可以發現

  f(n) = 2 f(n-1) = 2^(n-1)

# -*- coding:utf-8 -*-
class Solution:
    def jumpFloorII(self, number):
        # write code here
        if number == 1:
            return 1
        
        a = 1
        sum = 0
        for i in range(1, number):
            sum = 2* a
            a = sum
        return sum
           

或者

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