###### 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 for i in range(10)] for j 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://i.imgur.com/sbgxlao.png =100x) - [二元樹](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:下圖的中序、前序、後序走訪分別為? ![](https://i.imgur.com/J1qqaQ1.png =350x) ::: ``` 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走訪順序為(子節點以字母序走訪)? ![](https://i.imgur.com/JGKRYVy.png =450x) ::: :::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 for j in range(c)] for i 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 for j in range(10)] for i 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://nthucad.cs.nthu.edu.tw/~yyliu/personal/nou/04ds/dijkstra.html) :::info EX_07:畫出下圖的相鄰陣列,以Dijkstra演算法,求A到各點的最短路徑(以Excel表格表示)?++**0 8 6 4 3 1 5**++ ![](https://i.imgur.com/f0wz9DD.jpg =270x) ::: * [最小生成樹(minimum spanning tree)](https://www.itread01.com/content/1545066724.html) (1). Kruskal演算法為一個使用貪婪法 (greedy method) 的演算法,一開始為一空樹,每次在不讓圖中含有任何迴路(cycle)下尋找圖中最小權重的邊加入樹中,直到所有點皆在樹中即完成。 (2). Prim演算法與Dijkstra演算法類似,屢次找出不在樹上,離樹最近的點。 :::info EX_08:畫出下圖的最小生成樹,其權重總和為?++**28**++ ![](https://i.imgur.com/tjw9GuN.png =350x) ::: <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)) ```