亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

Python經典算法

系統 1625 0

文章目錄

  • 算法實現
    • #0 GitHub
    • #1 環境
    • #2 開始
      • #2.1 斐波那契數列
      • #2.2 跳臺階
      • #2.3 跳臺階(變態跳)
      • #2.4 兔子繁殖
      • #2.5 列表去重
    • 未完待續

算法實現

#0 GitHub

https://github.com/Coxhuang/Python-DataStructure

#1 環境

            
              Python3.7.3

            
          

#2 開始

Python經典算法_第1張圖片

#2.1 斐波那契數列

  1. GitHub

GitHub代碼

  1. 問題描述

  2. 規律

  3. 代碼實現

  • 常規實現
            
              def fib(max_val):

    a, b, n = 0, 1, max_val
    while n:
        print(a)
        a, b = b, a+b
        n -= 1
    return None
fib(10)


            
          

輸出

            
              0
1
1
2
3
5
8
13
21
34

            
          
  • 生成器
            
              

def fib(max_val):
    a, b, n = 0, 1, max_val
    while n:
        yield a
        a, b = b, a+b
        n -= 1
    return None
for foo in fib(10):
    print(foo)


            
          

輸出

            
              0
1
1
2
3
5
8
13
21
34

            
          
  • 遞歸
            
              def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
for foo in  range(10):
    print(fib(foo))

            
          

輸出

            
              0
1
1
2
3
5
8
13
21
34

            
          

#2.2 跳臺階

  1. GitHub

GitHub代碼

  1. 問題描述

一只青蛙一次可以跳上1級臺階,也可以跳上2級(最多跳2級),求該青蛙跳上一個n級的臺階總共有多少種方法?

  1. 規律

如果臺階只有一級,只有一種走法;如果臺階有兩級,走法有兩種;如果臺階有N級,最后跳上第N級的情況,要么是從N-2級直接跳兩級臺階,或者從第N-1級跳一級臺階,所以臺階有N級的方法數等于跨到N-2級臺階的方法數加上跨到N-1級臺階的方法數,即S(N)=S(N-1)+S(N-2),初始項為S(1)=1,S(2)=2,類似于斐波那契數列,只不過是初始項不同。

臺階數 方法
f(0) 0
f(1) 1
f(2) 2
f(3) 3
f(4) 5
f(5) 8

邏輯規律和斐波那契數列一致

  1. 代碼實現
            
              def fib(max_val):
    a, b, n = 0, 1, max_val
    while n:
        a, b = b, a+b
        n -= 1
    return b
n = 3 # 臺階數
ret = n if n <= 2 else fib(n)
print(ret)

            
          

#2.3 跳臺階(變態跳)

  1. GitHub

GitHub代碼

  1. 問題描述

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

  1. 規律

Python經典算法_第2張圖片

            
              當跳1級臺階時,f(1) = 1;

當跳2級臺階時,f(2) = f(1) + 1 = 2;

當跳3級臺階時,f(3) = f(2) + f(1) + 1 = 4;

當跳4級臺階時,f(4) = f(3) + f(2) + f(1) + 1 = 8;

f(n-1) = f(n-2) +...+ f(2) + f(1) + 1

f(n) = f(n-1) + f(n-2) +...+ f(2) + f(1) + 1


            
          

說明:

3.1. 這里的f(n) 代表的是n個臺階有一次1,2,…n階的 跳法數。
3.2. n = 1時,只有1種跳法,f(1) = 1
3.3. n = 2時,會有兩個跳得方式,一次1階或者2階,這回歸到了問題(1) ,f(2) = f(2-1) + f(2-2)
3.4. n = 3時,會有三種跳得方式,1階、2階、3階,那么就是第一次跳出1階后面剩下:f(3-1);第一次跳出2階,剩下f(3-2);第一次3階,那么剩下f(3-3)因此結論是:

            
              f(3) = f(3-1)+f(3-2)+f(3-3)

            
          

3.5. n = n時,會有n中跳的方式,1階、2階…n階,得出結論:

            
              f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1)

            
          

3.6. 由以上已經是一種結論,但是為了簡單,我們可以繼續簡化:

            
              f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2)
f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1)

            
          

3.7. 得出最終結論,在n階臺階,一次有1、2、…n階的跳的方式時,總得跳法為:

            
                          | 1       ,(n=0 ) 
            |
f(n) =      | 1       ,(n=1 )
            |
            | 2*f(n-1),(n>=2)

            
          
  1. 代碼實現
            
              
# 遞歸 - 法1
def jump(n):

    while n<=2:
        return n

    return jump(n-1)*2

print(jump(5))

            
          
            
              
# 遞歸 - 法2
def jump(n):

    while n<=2:
        return n

    return 2**(n-1)

print(jump(5))

            
          

#2.4 兔子繁殖

  1. GitHub

  2. 問題描述

有一對兔子,從出生后第3個月起每個月都生一對兔子,小兔子長到第三個月后每個月又生一對兔子,假如兔子都不死,問每個月的兔子總數為多少?

  1. 思路

f(N) : 第N個月兔子的總數

f(Nbefore) : 第N個月之前出生的兔子

f(Nnew) : 第N個月出生的兔子

f(N) = f(Nbefore) + f(Nnew) = f(N-1) + f(Nnew)

  • 到了第(N+1)個月時:第N個月出生的兔子還不能繁殖,第N個月之前出生的兔子全部都可以繁殖

f(N+1) = f(Nnew) + f(Nbefore) 2 = f(Nnew) + 2 f(N-1)

            
              由:
f(N) =  f(N-1) + f(Nnew)
f(N+1) = f(Nnew) + 2*f(N-1)

得:
f(N+1) = f(N) + f(N-1)

            
          
  1. 代碼實現
            
              def fib(max_val):
    a, b, n = 1, 2, max_val
    while n:
        a, b = b, a+b
        n -= 1
    return b
n = 5 # 第N月
ret = n if n <= 2 else fib(n)
print(ret)

            
          

#2.5 列表去重

  1. 沒有時間空間復雜度限制
            
              def func(tar):
    tar_copy = []
    for foo in tar:
        if foo not in tar_copy:
            tar_copy.append(foo)
    return tar_copy
ret = func([1,2,2,2,2,3,4,5,6,7,8,9,8,1,2,3,4])
print(ret)

            
          
  • 時間復雜度
            
              O(n)

            
          
  • 空間復雜度
            
              O(n)

            
          
  1. 有序列表 + 時間復雜度O(n) + 空間復雜度O(1)

意味著只能有一個for循環+只能在原表操作

            
              def func(tar):
    for i,num in enumerate(tar):
        try: # tar[i+1] 到最后一個會拋異常
            while num == tar[i+1]:
                tar.pop(i+1)
        except:
            break
    return tar
ret = func([1, 1, 1, 2, 2, 2, 2, 3, 3, 4, 4, 5, 6, 7, 8, 8, 9, 9, 9])
print(ret)

            
          

未完待續


更多文章、技術交流、商務合作、聯系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號聯系: 360901061

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對您有幫助就好】

您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長會非常 感謝您的哦!!!

發表我的評論
最新評論 總共0條評論
主站蜘蛛池模板: 久久精品国产福利国产秒 | 亚洲国产成人资源在线软件 | 久久久久这里只有精品 | 高清不卡毛片免费观看 | 久草在线视频免费播放 | 亚洲精品动漫一区二区三区在线 | 人成午夜欧美大片免费视频 | 97国产精品国产品国语字幕 | 国产成人乱码一区二区三区在线 | 亚洲欧美日韩在线精品2021 | 一亚洲精品一区 | 美日韩毛片 | 国产丶欧美丶日韩丶不卡影视 | 在线成人精品国产区免费 | 成人影院在线观看kkk4444 | a毛片免费在线观看 | 国产主播在线播放 | 久久精品国产久精国产果冻传媒 | 女人l8毛片a一级毛片 | 久久九九有精品国产23百花影院 | 久久久久久91 | 亚洲黄色免费在线观看 | 91精品国产乱码在线观看 | 久久福利影院 | 一区二区三区四区 | 午夜在线观看cao | 香蕉依人 | 中文字幕欧美日韩久久 | 97久久精品国产精品青草 | 亚洲高清在线观看 | 国产一区二区三区日韩 | 亚洲精品宾馆在线精品酒店 | 午夜看毛片 | aaa一级毛片| 久久免费视频在线 | 国产福利视频一区二区三区四区 | 久久精品国产99国产 | 人人爽天天碰天天躁夜夜躁 | 欧美性久久久久 | 91国内精品久久久久免费影院 | 亚洲视频三级 |