###### tags: `資訊科技`
# 資料結構與演算法(使用Python)
## 一、學習資料結構與演算法的目的
1. ### 資料結構討論「資料儲存的方式」
- 如陣列、鏈結串列
2. ### 演算法討論「解決問題的想法」
- 如排序方法、找質數的方法
:mega: 所選用的資料結構和演算法將影響程式的複雜度與效率
3. ### 參考網站
- [30天學演算法和資料結構](https://ithelp.ithome.com.tw/users/20111557/ironman/2110)
- [演算法與資料結構](http://alrightchiu.github.io/SecondRound/mu-lu-yan-suan-fa-yu-zi-liao-jie-gou.html)
- [Algorithms and Data Structures](http://gousios.org/courses/algo-ds/book/preface.html)
- [以Python實作資料結構](https://super9.space/archives/1105)
- [以Python實作演算法](https://super9.space/archives/1562)
- [The Algorithms - Python](https://github.com/TheAlgorithms/Python?fbclid=IwAR3bq27Qs_j6Qd21aKppbhcHALiQLsJ6v9pLORhru2xeEereV2F0R2ugToA)
<br />
## 二、資料結構
1. ### 堆疊
- LIFO(last in first out)
:::info
EX_01：10進位轉2進位(以list模擬)
:::
``` javascript=
stk = []
n = int(input('輸入n：'))
while ........ : # n不為0時繼續做
........ # 將n除以2的餘數push進堆疊(使用list的append)
........ # 將n/2
while len(stk) > 0: # 堆疊內還有元素
print(........ , end='') # 印出堆疊最上面的元素。pop沒有指定index，則傳回最後一個元素並刪除
```
2. ### 佇列
- FIFO(first in first out)
- 套件中的常用方法 (q = queue.Queue( ))
| 方法名稱 | 意義 |
|:----------|:---------------|
| q.qsize() | 回傳佇列大小 |
| q.empty() | 佇列是否為空 |
| q.put(x) | 將元素加入佇列後端|
| x=q.get() | 取出佇列前端的元素|
<br />
:::info
EX_02：[ZeroJudge e183: 10940 - Throwing cards away II](https://zerojudge.tw/ShowProblem?problemid=e183)
給你一疊有1~n編號的牌(1在最上面，n在最下面)，在牌數大於1的時候執行以下操作：「丟掉最上面的牌，並把現在最上面的的牌放到最下面。」
求最後剩下的那張牌編號為?(7->6、10->4)
:::
``` javascript=
from queue import Queue
q=Queue()
n = int(input('請輸入牌數：'))
for i in range(1,n+1):
........ # 將牌的編號(1 2 3 …)依序push(put)入佇列
while ........ : # 當佇列size>1時繼續執行
f=q.get() # 取出最上面的那張牌
........ # 取出次張牌，並將其重新放入佇列尾端
print(q.get()) # 印出剩下的那張牌
```
:::info
EX_02 (進階)：計算迷宮的最短路徑。
[2維陣列-列表生成式、串列綜合表達式(list comprehensions)](https://www.liaoxuefeng.com/wiki/0014316089557264a6b348958f449949df42a6d3a2e542c000/001431779637539089fd627094a43a8a7c77e6102e3a811000)
:::
``` javascript=
from queue import Queue
len = [[0]*10 for _ in range(10)]
# len為2維陣列，記錄起點到每一點的長度，列表生成式。
maze = [[1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,1],
[1,1,0,1,0,1,1,1,1,1],
[1,0,0,1,0,1,0,0,0,1],
[1,0,1,1,0,1,1,0,0,1],
[1,0,1,0,0,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]]
# 陣列最外層包一圈牆。(1,1) 為起點，(8,8)為終點。
q = Queue()
q.put((1, 1)) # 先把起點放入佇列
len[1][1] = 1
maze[1][1] = 1 # 走過設為牆
while not q.empty():
now=q.get() # 從佇列開頭取一個點
x,y=now[0],now[1] # 此點座標置於x,y
if maze[x + 1][y + 0] == 0: # 此點的右方有路
nx = x + 1 # 下一點座標
ny = y + 0
q.put((nx,ny)) # 下一個點放入佇列
len[nx][ny] = len[x][y] + 1 # 長度+1
maze[nx][ny] = 1 # 走過設為牆
if maze[x + 0][y + 1] == 0: # 此點的下方有路
nx = x + 0
ny = y + 1
q.put((nx,ny))
len[nx][ny] = len[x][y] + 1;
maze[nx][ny] = 1
if maze[x - 1][y + 0] == 0: # 此點的左方有路
........
........
........
........
........
if ........ : # 此點的上方有路
........
........
........
........
........
'''
x,y=q.get()
for nx,ny in [(x+1, y), (x, y+1), (x-1, y), (x, y-1)]:
if maze[nx][ny] == 0:
q.put((nx,ny)) # 下一個點放入佇列
len[nx][ny] = len[x][y] + 1 # 長度+1
maze[nx][ny] = 1;
'''
if len[8][8] == 0:
print('沒有路!')
else:
print('最短路徑為 ', len[8][8])
```
3. ### 樹
- [模擬具有樹枝狀性質的資料](http://www2.csie.ntnu.edu.tw/~u91029/Tree.html)，由節點與邊組成，例如家族族譜、電腦資料夾結構。
- [二元樹](https://mark-lin.com/posts/20170309/#--binary-tree-)
- [二元樹的走訪(Tree Traversal)](http://alrightchiu.github.io/SecondRound/binary-tree-traversalxun-fang.html#pre)
* 前序走訪(preOrder):先走訪樹根，然後左子樹，最後右子樹。
* 中序走訪(inOrder):先走訪左子樹，然後樹根，最後右子樹。
* 後序走訪(postOrder):先走訪左子樹，然後右子樹，最後樹根。
<br/>
:::info
EX_03：下圖的中序、前序、後序走訪分別為？
:::
``` javascript=
data=[0,1,2,3,4,5,6]
def preorder(i): # 前序
if(i>=7):
return;
else:
print(data[i], end=' ')
preorder(i*2+1)
preorder(i*2+2)
'''
if(i<7):
print(data[i], end=' ')
preorder(i*2+1)
preorder(i*2+2)
'''
........ # 中序
........ # 後序
preorder(0)
print('\n')
inorder(0)
print('\n')
postorder(0)
print('\n')
```
- [二元搜尋樹](http://marklin-blog.logdown.com/posts/1526463)
:::info
EX_04：建立二元搜尋樹
依讀入順序 30, 15, 50, 35, 10, 25, 40, 20, 45 建立一個二元搜尋樹(binary search tree)。
:::
- 樹的應用
* [遊戲樹(game tree)](https://commons.wikimedia.org/wiki/File:Tic-tac-toe-full-game-tree-x-rational.jpg)
* [霍夫曼編碼(Huffman Coding)](http://puremonkey2010.blogspot.com/2011/02/huffman-code.html)
:::info
EX_05：若一篇文章每個字母出現的次數為，a:8，b:7，c:3，d:4，e:5，建立Huffman Tree(次數小的字母結點放左邊)，並求每個字母的Huffman Code。
a->11
b->
c->
d->
e->00
:::
4. ### 圖
- [圖形是「頂點」(vertex)和邊(edge)所組成](https://mark-lin.com/posts/20170311/)
- 圖常用的表示法
* [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3)
* 相鄰串列表示法(Adjacency Lists)
- 圖的搜尋
* [深度優先搜尋(Depth First Search,DFS)](https://jason-chen-1992.weebly.com/home/-graph-searching-methods)：以堆疊(Stack)、遞迴來實作。(類似樹的前序走訪)
* [廣度優先搜尋(Breadth First Search,BFS)](http://simonsays-tw.com/web/DFS-BFS/BreadthFirstSearch.html)：以佇列(Queue)來實作。
:::info
EX_06_1：下圖的DFS與BFS走訪順序為(子節點以字母序走訪)？
:::
:::info
EX_06_2：[ZeroJudge c129: 00572 - Oil Deposits](https://zerojudge.tw/ShowProblem?problemid=c129)。
以DFS找出@相鄰土地有@有幾塊。
:::
``` javascript=
r,c = map(int, input().split())
visited = [[0]*c for _ in range(r)]
map=[]
for i in range(r):
line=list(input())
map.append(line)
def dfs(i, j):
if i<0 or i>=r or .... or .... or .... or .... : # i(列)、j(欄)超出邊界、此點已被拜訪過、此點沒油
return
visited[i][j]=1
dfs(i-1,j-1) # 左上。螢幕左上角為原點，往下、往右為正。 先看列(數學上的y)，後看欄(數學上的x)
dfs(i-1,j) # 上
dfs(...., ....) # 右上
........ # 左
........ # 右
........ # 左下
........ # 下
........ # 右下
cnt=0
for ........ # 第 i 列
for ........ # 第 j 欄
if ........ # 目前座標沒被拜訪過 而且 有油
dfs(.... , ....) # 從此點開始DFS
cnt+=1
print(cnt)
# 地圖、visited陣列輸出
# Bonus：visited陣列以編號標出不同的油田
測資(ans=4)
9 10
@@*@*@@*@@
@@*@**@*@*
*@@@****@@
*@@@**@**@
***@*@****
@@@@@*@*@@
@*@@**@@@*
@*@*******
@***@@@@**
```
:::info
EX_06 (Bonus)：[ZeroJudge d626: 小畫家真好用](https://zerojudge.tw/ShowProblem?problemid=d626)。
以DFS找出油漆桶能上色的範圍。
:::
:::info
EX_06 (進階)：以DFS，計算EX_02_2(進階)迷宮的最短路徑。
:::
``` javascript=
def dfs(sx, sy, step):
if (sx == gx and sy == gy):
global MIN
if(step < MIN):
MIN = step
return
for nx,ny in [(sx+1, sy), (sx, sy+1), (....), (....)]: # 下一個點的順序：右、下、左、上
if maze[nx][ny] == 0 and visited[nx][ny] == 0:
visited[nx][ny] = 1 # 下一個要走的點先設為走過
........ # 遞迴呼叫實作DFS，從nx,ny繼續往後走，走的步數+1
........ # 下一個要走的點恢復為沒走過
return
MIN = 999
visited = [[0]*10 for _ in range(10)]
maze = [[1,1,1,1,1,1,1,1,1,1],
[1,0,0,0,0,0,0,0,0,1],
[1,0,1,1,1,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,1],
[1,1,0,1,0,1,1,1,1,1],
[1,0,0,1,0,1,0,0,0,1],
[1,0,1,1,0,1,1,0,0,1],
[1,0,1,0,0,1,1,1,0,1],
[1,0,0,0,0,0,0,0,0,1],
[1,1,1,1,1,1,1,1,1,1]]
# 陣列最外層包一圈牆。(1,1) 為起點，(8,8)為終點。
sx,sy = 1,1 # 起點
gx,gy = 8,8 # 終點
visited[1][1] = 1 # 將起點標記為1，表示走過，避免重復走。
dfs(sx, sy, 1)
print(f'最短路徑:{MIN}')
```
- 圖的應用
* [最短路徑演算法(一個頂點到多頂點-代克思托Dijkstra)](http://puremonkey2010.blogspot.com/2013/05/alg-info-dijkstras-algorithm-shortest.html)
:::info
EX_07：畫出下圖的相鄰陣列，以Dijkstra演算法，求A到各點的最短路徑(以Excel表格表示)？++**0 8 6 4 3 1 5**++
:::
* [最小生成樹(minimum spanning tree)](https://www.itread01.com/content/1545066724.html)
(1). Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法，一開始為一空樹，每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中，直到所有點皆在樹中即完成。
(2). Prim演算法與Dijkstra演算法類似，屢次找出不在樹上，離樹最近的點。
:::info
EX_08：畫出下圖的最小生成樹，其權重總和為？++**28**++
:::
<br />
## 三、演算法
1. ### 演算法效能
- [運算能力](https://buzzorange.com/techorange/2019/09/11/solve-sums-of-three-cubes/)
* 循序搜尋 v.s. 二分搜尋
- [時間複雜度](https://jason-chen-1992.weebly.com/home/time-space-complexity)
* [常見的六種時間複雜度與演算法](https://medium.com/appworks-school/%E5%88%9D%E5%AD%B8%E8%80%85%E5%AD%B8%E6%BC%94%E7%AE%97%E6%B3%95-%E5%BE%9E%E6%99%82%E9%96%93%E8%A4%87%E9%9B%9C%E5%BA%A6%E8%AA%8D%E8%AD%98%E5%B8%B8%E8%A6%8B%E6%BC%94%E7%AE%97%E6%B3%95-%E4%B8%80-b46fece65ba5)
- 求質數演算法效能比較
:::info
EX_09_1：求3萬內的質數。
:::
``` javascript=
import datetime
start = datetime.datetime.now()
n=30000
lst=[]
for i in range(2, n+1):
prime = True
for j in range(2, i): # 測試2~i-1是否有因數
if i%j == 0:
prime = False
break
if prime:
lst.append(i)
print(lst)
end=datetime.datetime.now()
print(end-start) # 11.23sec
```
``` javascript=
import datetime
start = datetime.datetime.now()
n=30000
lst=[]
for i in range(2, n+1):
for j in range(2, i): # 測試2~i-1是否有因數
if i%j == 0:
break
else: # for-else，for循環完整完成才執行else
lst.append(i)
print(lst)
end=datetime.datetime.now()
print(end-start) # 9.72sec
```
:::info
EX_09_2：求20萬內的質數。
:mega:
1. 如果一個數是合數，它的最小質因數會小於等於它的平方根。
2. 因為成對出現的因數中，一個會≦√n，而另一個會≧√n。因此只要檢查≦√n中是否有n的因數即可。
:::
``` javascript=
import datetime
start = datetime.datetime.now()
n=200000
lst=[]
for i in range(2, n+1):
for j in range(2, int(i**0.5)+1): # 測試2~√i是否為因數
if i%j == 0:
break
else: # for-else，for循環完整完成才執行else
lst.append(i)
print(lst)
end=datetime.datetime.now()
print(end-start) # 1.93sec
```
:::info
EX_10：[埃拉托斯特尼篩法](https://zh.wikipedia.org/wiki/%E5%9F%83%E6%8B%89%E6%89%98%E6%96%AF%E7%89%B9%E5%B0%BC%E7%AD%9B%E6%B3%95)，求100萬內的質數。
:::
``` javascript=
import datetime
start = datetime.datetime.now()
n=1000000
prime = [True]*(n+1) # 產生n+1個True的list
for i in range(2, int(n**0.5)+1): # 檢查到<=√n即可
if prime[i]:
for j in range(...., n+1, ....): # 如果i是質數，則篩掉它的倍數。(從i^2開始，每次+i)
prime[....] = .... # i的倍數不為質數
lst = [x for x in range(2, n+1) if prime[x]]
print(lst)
end=datetime.datetime.now()
print(end-start) # 0.37sec
```
<br />
2. ### 分而治之(Divid and Conquer)
- [合併排序(Merge Sort)](http://alrightchiu.github.io/SecondRound/comparison-sort-merge-sorthe-bing-pai-xu-fa.html)
:::info
EX_11：[ZeroJudge d219: 00374 - Big Mod](https://zerojudge.tw/ShowProblem?problemid=d219)
對相當大的b、p、m，請寫一個有效率的演算法來計算 r = b^p mod m ( 1 <= b、p、m <= 32767 )
b=2、p=8、m=10 → r=6
b=2、p=10、m=10 → r=4
b=17、p=1765、m=3 → r=2
:::
:mega: [分配律](https://zh.wikipedia.org/wiki/%E6%A8%A1%E9%99%A4)：(A\*B)%M=[ (A%M)\*(B%M) ]%M→B^P^%M=[ (B^P/2^%M)\*(B^P/2^%M) ]%M
EX：4\*5%3=(4%3)\*(5%3)、5\*8%3=(5%3)\*(8%3)%3
``` javascript=
def dc(b,p,m):
if ........ # p分割到1時停止
return ........
else:
if ........
return ........ # p為偶數，( b^(p/2)%m * b^(p/2)%m ) % m
else:
........ # p為奇數要比偶數時多乘一次b
b,p,m = map(int,input("請輸入b、p、m(空白隔開)： ").split())
print(dc(b,p,m))
```
:::info
EX_12 (進階)：合併排序實作。
:::
``` javascript=
def mergesort(lst):
if len(lst) <= 1:
return lst
mid = len(lst)//2
left = mergesort(lst[:mid])
right = mergesort(lst[mid:])
mrg_lst = []
while left and right: # 即while len(left)>0 and len(right)>0: 因為空的串列即為False，可直接邏輯判斷
if left[0] < right[0]:
mrg_lst.append(left.pop(0)) # 傳回left索引值0的元素，並將其刪除
else:
mrg_lst.append(right.pop(0))
mrg_lst += left + right # left 或 right剩下的元素全部加到mrg_lst
return mrg_lst
lst=[6,3,5,1,8,2,7,4]
print(mergesort(lst))
```
Sign in with Wallet
Connect another wallet