文章目錄
- 算法實現
- #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 開始
#2.1 斐波那契數列
- GitHub
GitHub代碼
-
問題描述
-
規律
-
代碼實現
- 常規實現
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 跳臺階
- GitHub
GitHub代碼
- 問題描述
一只青蛙一次可以跳上1級臺階,也可以跳上2級(最多跳2級),求該青蛙跳上一個n級的臺階總共有多少種方法?
- 規律
如果臺階只有一級,只有一種走法;如果臺階有兩級,走法有兩種;如果臺階有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 |
… | … |
邏輯規律和斐波那契數列一致
- 代碼實現
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 跳臺階(變態跳)
- GitHub
GitHub代碼
- 問題描述
一只青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
- 規律
當跳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
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 兔子繁殖
-
GitHub
-
問題描述
有一對兔子,從出生后第3個月起每個月都生一對兔子,小兔子長到第三個月后每個月又生一對兔子,假如兔子都不死,問每個月的兔子總數為多少?
- 思路
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)
- 代碼實現
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 列表去重
- 沒有時間空間復雜度限制
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)
- 有序列表 + 時間復雜度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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
