文章目錄
- 算法實現
- #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元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
