###### tags: `選修` # 進階程式設計(Python) :::success **評量、學習歷程** ::: ### 1. 評量方式 + 上課基本練習(遲交期限：1週) **40%** + 作業題數 **20%** (期中10%+期末10%) - 作業登記表：[高三五選A(309\~311、315)](https://docs.google.com/spreadsheets/d/1VTlC3J2BrGutxuUBDIJeU11IZvBXLRpm3ERU8MgjvlU/edit?usp=sharing)、[高三五選B(312\~314、317)](https://docs.google.com/spreadsheets/d/1u59MsjcIn1zUwQQcS9cg75bcW6eqlhvIDkhJXXcjylk/edit?usp=sharing) - [歷年作業登記表](https://hackmd.io/@cube/r1Cw2JgDT) - 每寫完一題作業，請將程式碼連結登錄於作業登記表，以統計作業題數。請小心不要改到別人的資料。惡意編刪別人的資料，視情節扣分或校規處理。 - 作業原始分數：解題數 $*$ 10 (最高120分) ``` if 上機考分數>=60 作業實得分數=作業原始分數 else 作業實得分數=作業原始分數*(上機考成績/60) ``` - 不要為了衝題數，做複製貼上、不求甚解這種沒意義的事。上機考0分，全部都寫也是0分。 - 不寫作業，除了無作業成績，上機考時網路會斷線，沒有任何參考資料，也必定寫不出來，請每個單元至少完成 2 題作業，熟練基本語法。**(不寫作業被當的機會很高，除非你有本事上機考2次都及格)** - 不要考前才寫作業，初學程式會有很多錯誤，要花時間除錯。請自我要求每週至少要寫 1 題作業，上機考才會比較保險。 - 不會的可以去參考網路上的程式碼、解法，同學也可以互相討論，而且是鼓勵的。不論如何，都要在了解解法後，不看別人的程式碼，自己親自寫一遍。 - 有做作業，考差了才有補救的機會，作業題為期末解題報告的題目。 + 期中上機考(二、搜尋教完後 1 週) **20%** + 期末上機考(倒數第 2 週) **20%** + 期末解題報告 **10%** (高二) - 非必要，想高分或不及格的同學請保握最後機會。 - 繳交期限：最後一週上課前 1 天。 - 分數：每一題 10 分。每個單元至多可放 2 題 (不可以都寫同一單元的題目) - 報告格式： * 第1頁為解題目錄(單元、題號、題目、頁碼)。 * 每題的子標題為 (1) 單元、題號、題目、題目簡述 (2) 解題動態、評分結果截圖 (3) 解題思路 (4) 程式碼 (5) 反思(遇到的錯誤、修正的地方、更好的方法…) (6) 錯誤程式碼 - 檢核方式： * 有交解題報告者，最後一週會請你在沒有網路的狀態下重寫一題當做檢核(題目由老師挑選)，寫不出來作業直接作廢不算分，請務必自行思考完成。 * 不要為了分數直接複製貼上別人的程式碼，那是無意義的行為，檢核時你就會現出原形，就不用做這種白工了。 - 可整合上課內容後完成課程學習成果，上傳至學習歷程檔案平台。請儘量挑選一開始有錯，然後修正的題目，將修正的想法寫出來更能顯示出反思的能力。 ### 2. [APCS](https://apcs.csie.ntnu.edu.tw/) + 實作級分*2，直接加在總成績。 + 4級分免上機考，上機考成績為100。 + 5級分以上者，一切皆免，學期成績直接算100。 ### 3. APCS 實作題檢測從三級到五級(中正大學 吳邦一教授) + [AP325(Python)](https://hackmd.io/@bangyewu/Hy2kbYLI6/%2Fg2kqHh5_Q4eQnz-mfNu3Kw)、[範例程式](https://drive.google.com/drive/folders/1JziPJ39tANRokjx6nFzZSRXtym0p5_kg?fbclid=IwAR2Xo7LP8V3lWyhJEbFx3F8JLF9AIEI9t9snla9vwwtI4qlGc0mDwJVuf1o) + [AP325(C++)](https://drive.google.com/drive/mobile/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m?usp=sharing) + [APCS實作題檢測(Facebook)](https://www.facebook.com/groups/359446638362710) + [HWSH Judge (例題與習題)](https://judge.hwsh.tc.edu.tw/)、[TCFSH CIRC Judge(例題與習題)](https://judge.tcirc.tw/) + [PythAPCS123講義](https://drive.google.com/drive/folders/1mnVdO2LHq7e4vesn6pt_R0-S6YWtz4Q4?fbclid=IwAR2Xo7LP8V3lWyhJEbFx3F8JLF9AIEI9t9snla9vwwtI4qlGc0mDwJVuf1o)、[PythAPCS123 YouTube撥放清單](https://youtube.com/playlist?list=PLpmg1QLbgMuSIDOgOcwf0Fbbn2ZDR7s-X ) + [PyAP45_v202201題解講義](https://drive.google.com/drive/u/0/folders/10hZCMHH0YgsfguVZCHU7EYiG8qJE5f-m)、[PyApcs45 YouTube撥放清單](https://www.youtube.com/playlist?list=PLpmg1QLbgMuRQXHRkX9iDHyAVIW1D6OJF ) ### 4. 學習歷程檔案(修課記錄、課程學習成果) + 最後一週上課結束前如果認證完成，學期總成績加分。 + [撰寫「課程學習成果」參考資源](https://hackmd.io/@cube/HkCv90e19)。 ### 5. 修課建議目標 + 低：成績及格(修課記錄)。 + 中：能產出課程學習成果。 + 高：參加 APCS 檢定，實作達到 3 級分以上。 ### 6. 演算法進階參考 + [中央資工演算法](https://staff.csie.ncu.edu.tw/jrjiang/alg2019/) + [中山資工演算法](http://par.cse.nsysu.edu.tw/~cbyang/course/algo/algo_index.htm) + [台大資訊系統訓練班演算法](https://www.csie.ntu.edu.tw/~d92005/course_Algorithm(2008).htm) ### 7. [高中資訊學科中心 科技領域加深加廣選修課程－進階程式設計](https://ghresource.mt.ntnu.edu.tw/nss/s/main/InformationTechnologyTPD05) ### 8. 軟體 + [Google Colaboratory](https://colab.research.google.com/) - [Google Colab相關設定](https://hackmd.io/@wiimax/HJuUPnPQr) + [The collaborative browser based IDE - Replit](https://replit.com/) - 「+ Create Repl」 可新增一個 Repl (專案) - Template 欄選擇 「C++」 或 「Python (with Prybar)」，Title 欄填入專案標題如 a001， 再按「+ Create Repl」鈕，就會進入專案編輯的頁面。 - 如果 Template 沒有看到 Python (with Prybar) ，請自行輸入 prybar 後按「Search community templates」後點找到的「Python (with Prybar)」，按「+ Use Template」/「Use Template」，回首頁重新整理後，「Python (with Prybar)」即會出現在 「Favorites」項目下。 - Repls：專案管理 New folder：建立分類資料夾，如 ch1、ch2 …。 專案.../Move：將專案移至分類資料夾。 - 側邊欄/Tools/User Settings/Indentation Size：4 - 側邊欄/Tools/User Settings/ser Settings/AI Code Completion：關閉 - 側邊欄/Tools/User Settings/Themes：Explore Themes/VS Code Dark/Use Theme + [GDB online Debugger | Compiler - Code, Compile, Run, Debug online C, C++](https://www.onlinegdb.com/) + [Online Python](https://www.online-python.com/) + [Thonny](https://thonny.org/) (安裝套件： Tools/Manage plug-ins) <br/> :::success **程式語言(基本語法複習)** ::: + 巢狀 if :::info EX_0_1：[a003. 兩光法師占卜術](https://zerojudge.tw/ShowProblem?problemid=a003) ``` python= print('hello') a=input() # 輸入 1 ''' execute Python code interactively > a # a='1' > a+10 > a+'10' 再分別輸入 1.5、'abc'、'1 2' ''' a=input() b=int(a) a=input() a=int(a) a=int(input()) # a=1 a=input().split() # a=['1','2']。a[0]、a[1] m=a[0] d=a[1] m,d=input().split() # m='1', d='2' m=int(m) # m=1 d=int(d) # m=2 m,d=map(int, input().split()) # m=1, d=2 ``` ``` python= if 條件1: 條件1「成立」時程式碼區塊 elif 條件2: 條件1「不成立」，且條件2「成立」時的程式碼 ... else: 上述條件都「不成立」時的程式碼 ``` ::: + for 迴圈 :::info EX_0_2：[d490: 我也愛偶數](https://zerojudge.tw/ShowProblem?problemid=d490) + 先完成1+...+n ``` python= a=['a','b','c'] for x in a: print(x) idx=[0,1,2] # idx=range(3) 產生串列 [0, 1, 2] for i in idx: # for i in range(3): print(a[i]) for i in range(10,20,2): print(i) ``` ::: + 一維串列 :::info EX_0_3：[f818. 物競天擇 (Survival)](https://zerojudge.tw/ShowProblem?problemid=f818) ``` python= h=map(int, input().split()) # <map object at 0x7f2751f4b130> h=list(map(int, input().split())) h=[*map(int, input().split())] # h=[int(n) for n in input().split()] ``` + `Ctrl+Shift+v`：Replit 測資貼上。或右鍵／貼上。 ::: <br/> :::success **資料結構** ::: ## 一、串列 + 常用串列函式 | 串列函式 | 意義 | |:------------ |:-------------- | | lst=list() 或 lst=[] |宣告空的串列| | len(lst) | 回傳串列個數 | | max(lst) | 回傳串列中的最大值 | | min(lst) | 回傳串列中的最小值 | | sum(lst) | 將串列元素加總 | | list('abc') | 將'abc'拆成'a','b','c'加入串列 | | 串列方法(函式) | 意義 | |:---------------|:-------------- | | lst.append(x) | 將x附加到串列後面 | | lst.insert(i,x)| 將x插入到索引值i的位置 | | lst.extend(x) | 將串列x中的所有元素，附加到串列後面。<br />a=[1,2] b=[3,4] <br /> a.append(b) vs. a.extend(b)| | lst.remove(x) | 刪除串列中的第一個x | | x=lst.pop(i) | 回傳索引值i的元素，並將其刪除；<br/>如果沒有i，則傳回最後一個元素並刪除 | | it=lst.index(x) | 回傳第一次出現x的索引值 | | lst.count(x) | 計算出現x的次數 | | lst.sort() | 將串列中的元素小->大排序，大->小則加入參數reverse=True | | lst.reverse() | 將串列中的元素反轉 | | lst2=lst.copy()| copy串列 | | lst.clear() | 清除串列內所有元素 | :::info DS_EX_1_1：[陸行鳥大賽車](https://neoj.sprout.tw/problem/21/) + `ctrl + /`：多行註解 + `Tab、Shift+Tab`：增、減縮排 ``` python # [1, 2, 3] → [1, 3, 2] lst=[1, 2, 3] # it=lst.index(3) # 找到 3 的位子 # lst.remove(3) lst.insert(1,3) # 將 3 插入到索引值 1 的位子，lst=[1, 3, 2, 3] lst.remove(3) # 將 3 移除。移除第 1 個 3，如何才能移除第 2 個 3？ # lst.insert(it-1,3) ``` ::: ``` python= n=int(input()) m=int(input()) lst=[] for ~ # 將 1~n 放入 lst。lst=list(range(1,n+1)) ~ for _ in range(m): t,x=map(int,input().split()) if t==0: # x受攻擊 ~ # 刪除 x elif t==1:# x衡刺 ~ # 找 x 的位子 if ~ # 如果不是開頭 ~ # 刪除 x ~ # 將 x 插入到前 1 個位子 print(*lst) #for x in lst: # print(x, end=' ') ``` :::warning [a870: 10. List Maker](https://zerojudge.tw/ShowProblem?problemid=a870) ::: ``` python= ~ # 宣告一個空的lst while True: try: line=input() # 讀入一行 except: break # 只用 line=input() 會有 EOFError: EOF when reading a line if line=='SHOW': break cmd=list(line.split()) # 將讀入的一行以空白分割。cmd=[*line.split()] if ~ # 如果 cmd[0] 為 ADD ~ # 將 cmd[1] 加入 lst elif ~ # 如果 cmd[0] 為 INSERT ~ # 找出 cmd[2] 的 index ~ # 將 cmd[1] 插入此 index elif ~ # 如果 cmd[0] 為 REMOVE ~ # 移除 cmd[1] ~ # 印出lst ``` <br/> ## 二、堆疊 + [0-19 queue 與 stack | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/03/0-19/) + 串列模擬堆疊(Stack)常用的方法 | 串列方法(函式) | 意義 | |:-----|:----------| | len(sk) | 回傳串列個數 | | sk.append(x) | 將 x 附加到串列後面 | | x=sk.pop() | 回傳最後一個元素並刪除 | + 算數運算子 | 算數運算子 | 意義 | 備註| |:-------- |:------ |:-------| | / | 除 |17/5 為 3.4，15/5 為 3.0 | | // | 取商數 |17//5 為 3 | | % | 取餘數 |17%5 為 2 | | ** | 次方 | 5**2 為 25 | + 運用 [] 取值，可以使用 index(索引值從0開始)、slice 來存取陣列裡的資料。 | slice運算 | 意義 | |:----------- |:-------------- | | lst[i] | 取出索引值i的元素 | | lst[-1] | 取出最後一個元素 | | lst[i:j] | 取出索引值i~j-1的元素 | :::info DS_EX_2_1：[f698. 後序運算式 ](https://zerojudge.tw/ShowProblem?problemid=f698) ::: ``` python= sk=[] # 宣告一個空的串列，模擬堆疊 line=input().split() for c in line: # for c in input().split(): if c=='+': # a b + sk.append(sk.pop()+sk.pop()) # 將最後2個元素pop，相加後重新放入堆疊 elif c=='-': # a b - ~ # 不可直接 sk.append(sk.pop()-sk.pop())，這樣是 b-a。 elif c=='*': # a b * ~ elif c=='/': # a b / 為 a/b ~ # 取出 b ~ # 取出 a ~ # 不可直接 sk.append(sk.pop()/sk.pop())，這樣是 b/a。// 取商 else: # 數字直接放入堆疊 ~ print(sk.pop()) ``` :::info DS_EX_2_2：[e924. pC. 括號配對](https://zerojudge.tw/ShowProblem?problemid=e924) + 遇到左括號，放入 stack。 + 遇到右括號，檢查 stack 是否是空的(有無左括號可配對)。如果空，則括號不正確；如果不空，且括號成對，則 pop 掉。 + 最後再檢查 stack 是否是空的。 + 範例輸入 4 {()<>}[] [(]) ()[ ()] + 範例輸出 Y N N N ::: ``` python= T=int(input()) for _ in range(T): # for _ in range(int(input())): line=input() sk=[] legal=True for c in line: # for c in input(): if c=='(' or ~ : # 如果是([<{，則放入堆疊 sk.append(c) elif len(sk)>0 and ( (c==')' and sk[-1]=='(') or ~ or ~ or ~ ): # 如果堆疊裏有之前放入的括號，而且 c=')' 堆疊最上面為'(' (其餘依此類推)，則 pop 掉左括號 ~ else: # 其它狀況為括號配對不正確 ~ ~ if ~ # 如果合法，最後堆疊內會沒有東西 legal=False if legal: print('Y') else: print('N') ``` :mega: 逐行除錯練習。先不寫15~16行，發現測資 ()[ 的錯誤。 + Thonny (1) 執行目前程式(F5)後發現錯誤。 (2) 點行號設定中斷點(可跳過沒問題的程式)。 (3) 按「![截圖 2024-09-05 下午2.36.26](https://hackmd.io/_uploads/SJNq-0I3A.png =20x20) 為目前腳本除錯」，準備逐行執行。 (4) 檢視/變數，開啟變數面板，可以看到執行每一步的變數變化。 (5) 逐行執行 　　跳過(Step Over)(F6)：黃色區塊一次執行(big step)。 　　跳入(Step into)(F7)：詳細執行每個小步驟(small step)。 (6) 發現錯誤後按『STOP』停止除錯，修正程式。 + Google Colab (1) 執行目前程式(Ctrl+Enter)後發現錯誤。 (2) 於有問題程式碼前加入breakpoint() (執行到中斷點，可跳過沒問題的程式)。 (3) Pdb 指令 | 指令 | 功能 | | ----| ----- | | n(next) | 執行當前行，並移動到下一行，不進入函數內部| | s(step) | 進入函數內部逐步執行| | c(continue) | 繼續執行到下一個中斷點或程式結束| | p <變數名> | 印出變數的值。例如p score 會印出 score 變數的值| | q(quit) | 離開 pdb| | h(help) | 指令說明| ``` python= for _ in range(int(input())): sk=[] for c in input(): if c=='(' or ~ : # 如果是([<{，則放入堆疊 sk.append(c) elif len(sk)>0 and ( (c==')' and sk[-1]=='(') or ~ or ~ or ~ ): # 如果堆疊裏有之前放入的括號，而且 c=')' 堆疊最上面為'(' (其餘依此類推)，則 pop 掉左括號 ~ else: ~ # 不正確直接輸出 break else: # 迴圈正常結束，執行此區塊程式碼。(break不會執行) if ~ # 如果合法，最後堆疊內會沒有東西 print('Y') else: print('N') ``` :::warning [i213: stack 練習](https://zerojudge.tw/ShowProblem?problemid=i213) ::: ``` python= n=int(input()) sk=[] for ~ # 做 n 次 a=[*map(int,input().split())] # 將輸入以空白分割轉成整數後，放入list a if ~ # 如果 list a 第 0 個元素為 1 ~ # 將 list a 第 1 個元素加入堆疊 sk elif ~ # 如果 list a 第 0 個元素為 2 try: ~ # 印出堆疊 sk 頂端的元素 except: ~ # 堆疊 sk 內沒有元素，輸出 −1 elif ~ # 如果 list a第 0 個元素為 3 try: ~ # 刪除堆疊 sk 最頂端的元素 except: pass ``` :::warning [d318: 11185 - Ternary](https://zerojudge.tw/ShowProblem?problemid=d318) + 以 stack 記錄不斷除以 3 的餘數。 ::: :::warning [b838: 104北二2.括號問題](https://zerojudge.tw/ShowProblem?problemid=b838) + 去除字串左右空白：line=input().strip() ::: <br/> ## 三、佇列 + [0-19 queue 與 stack | 從零開始的演算法競賽入門教學](https://emanlaicepsa.github.io/2020/12/03/0-19/) + 串列模擬佇列(Queue)常用的方法 | 串列方法(函式) | 意義 | |:--------|:----------| | len(q) | 回傳串列個數 | | q.append(x) | 將 x 附加到串列後面 | | x=q.pop(i) | 回傳索引值i的元素，並將其刪除；<br/>如果沒有i，則傳回最後一個元素並刪除 | + [實作 queue 時效率問題的考量](https://hackmd.io/@s10109670/r1IP771n_?fbclid=IwAR00pFRQZSGuXx7FoXx8_Lxe0qUYwAVzUaWlj9QIDVKfEH3o6S3TZmMtaM0) :::info DS_EX_3_1：[e155: 10935 - Throwing cards away I](https://zerojudge.tw/ShowProblem?problemid=e155) + [Print lists in Python (4 Different Ways) - GeeksforGeeks](https://www.geeksforgeeks.org/print-lists-in-python-4-different-ways/) + Google : [python print 不換行](https://medium.com/data-science-is-not-hard/python%E5%AD%B8%E7%BF%92%E7%AD%86%E8%A8%98-hello-world-%E5%AD%97%E4%B8%B2%E4%BB%8B%E7%B4%B9-%E8%AE%93%E6%96%87%E5%AD%97%E4%B8%8D%E6%8F%9B%E8%A1%8C-529f3b9b11b2)。或問[ChatGPT](https://chat.openai.com/)。 + 指定字符(str)連接串列(lst)中的元素後，生成新字串(x)：[x = str.join(lst)](https://www.w3schools.com/python/ref_string_join.asp) ``` python lst = ['a','b','c'] x = ', '.join(lst) ``` + [列表生成式(List Comprehensions)](https://www.liaoxuefeng.com/wiki/1016959663602400/1017317609699776)建立list，類似數學集合的表示法 $\{ 2n+1 \mid n \in \{0, 1, 2, 3, 4\} \} \rightarrow \{1,3,5,7,9\}$ ``` python a = [2*n+1 for n in range(5)] # a = [1, 3, 5, 7, 9] lst = [1,2,3,4,6,7,13,21] b = [n for n in lst if n%2==0] # b = [2, 4, 6] c = [ [0 for i in range(3)] for j in range(2) ] # c = [[0, 0, 0], [0, 0, 0]] d = [ [0]*3 for j in range(2)] ``` ::: ``` python= while True: try: n=int(input()) if n==0: break q=[] discard=[] for ~ # 將 1~n 放到佇列。q=list(~) ~ for ~ # 做 n-1 次 ~ # 將佇列前端元素放至discard，並刪除 ~ # 讀取佇列前端元素，並從後端加入 # 1. 先印出 discard 元素檢查答案是否正確，元素間為空白 print('Discarded cards:', *discard) # 2. 分兩段印 print('Discarded cards:', e~) # 結尾不換行 print(*discard, s~) # discard 元素間為', ' # 3. 以列表生成式，將 discard 元素轉成文字，並在元素間加上', ' 組成字串 print('Discarded cards:', ~) # 4. 以map的方式將discard裏的數字轉成文字 print('Discarded cards:', ', '.join(map(str,discard)) ) print('Remaining card:', q[0]) except: break ``` :::info DS_EX_3_2：[a982: 迷宮問題#1](https://zerojudge.tw/ShowProblem?problemid=a982) + [圖的搜尋](https://jason-chen-1992.weebly.com/home/-graph-searching-methods) - [深度優先搜尋(Depth First Search, DFS)](http://simonsays-tw.com/web/DFS-BFS/DepthFirstSearch.html)：以堆疊(Stack)、遞迴來實作。 - [廣度優先搜尋(Breadth First Search, BFS)](http://simonsays-tw.com/web/DFS-BFS/BreadthFirstSearch.html)：以佇列(Queue)來實作。 + tuple(元組)：類似 list，但元素個數及元素值不能改變，執行效能較好。 - 元組變數 = ( 元素1, 元素2, .... ) - list 使用 []，而 tuple 使用 ()。 ``` python lst = ['臺北', '臺中', '臺南'] lst.append('高雄') lst[2] = '高雄' tpl = ('臺北', '臺中', '臺南') tpl.append('高雄') tpl[2] = '高雄' ``` + ![](https://hackmd.io/_uploads/SyQ6o_Gga.png =250x) ::: ``` python= n=int(input()) maze=[] length=~ # 以列表生成式產生n*n的二維串列，初值為-1 q=[] for _ in range(n): ~ # maze.append(input()) q.append((1,1)) # tuple 介紹 length[1][1]=1 maze[1][1]='#' while ~ # 當佇列內還有點 ~ # 從前端取出 r,c=e[0],e[1] if maze[r+0][c+1]=='.': # 右 ~ # 將 (r,c+1) push 至 queue ~ # 右邊點的長度為目前點的長度+1 ~ # 右邊點設為 '#' 表示走過 ~ # 下 ~ # 左 ~ # 上 if length[n-2][n-2]==-1: print('No solution!') else: print(length[n-2][n-2]) ``` ``` python= # Q：如何以迴圈，讓程式碼更精簡 dr=(~,~,~,~) # 以tuple或list表示座標要調整的數值(右、下、左、上) dc=(~,~,~,~) while len(q)>0: e=q.pop(0) # 從前端取出 r,c=e[0],e[1] for i in range(4): # 四個方向 nr, nc = ~, ~ # 多設下一點座標變數 nr,nc 讓程式碼更清楚 if maze[~][~]=='.': # 下一個點的座標 ~ # 將下一個點 push 至 queue ~ # 下一個點的長度為目前點的長度+1 ~ # 下一點設為 '#' 表示走過 ``` :::warning [e447: queue 練習](https://zerojudge.tw/ShowProblem?problemid=e447) ::: ``` python= n=int(input()) q=[] for ~ # 做 n 次 ~ # 將輸入以空白分割轉成整數後，放入 list a if a[0]==1: ~ # 將 a[1] 放入佇列 q elif a[0]==2: ~ # 取得佇列 q 前端元素，如果沒有元素，輸出 -1。(try except) elif a[0]==3: ~ # 刪除佇列 q 前端元素，如果沒有元素，無視該操作。(try except pass) ``` :::warning [n763. 我愛偶數 (之偶數殺手)](https://zerojudge.tw/ShowProblem?problemid=n763) + 以 list 模擬，NA(score:80%)即可。 + 如果要AC，請參考[實作 queue 時效率問題的考量](https://hackmd.io/@s10109670/r1IP771n_?fbclid=IwAR00pFRQZSGuXx7FoXx8_Lxe0qUYwAVzUaWlj9QIDVKfEH3o6S3TZmMtaM0)，以deque實作。 ``` python= from collections import deque dq=deque(map(int, input().split())) ``` + x=dq.popleft() # 從最前面刪除一個元素，並將值回傳 ::: :::warning [d406: 倒水時間](https://zerojudge.tw/ShowProblem?problemid=d406) + BFS，以 queue 實作。 ::: :::warning [m372. 3. 搬家](https://zerojudge.tw/ShowProblem?problemid=m372) + [解題參考](https://hackmd.io/@bangyewu/SkxXo4QGa) ::: <br/> <br/> :::success **演算法** ::: ## 一、排序演算法 + [思考排序的演算法](https://zh.wikipedia.org/wiki/十三張) ### 1. 氣泡排序(Bubble Sort) + [bubble sort](https://ithelp.ithome.com.tw/articles/10276184?sc=pt)：兩兩相比，數字大的往後擺，好像數字大的元素慢慢「浮」到右端。 + [Bubble Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=nmhjrI-aW5o) :::info AL_EX_1_1：[a539: 10327 - Flip Sort](https://zerojudge.tw/ShowProblem?problemid=a539) ::: ```python= # bubble sort while True: try: n=int(input()) a=[*map(int, input().split())] cnt=0 for ~ # 5 個數字排序只需 4 個循環 for ~ # 每次兩兩比較，每次比較索引值「0、1」「1、2」「2、3」「3、4」 的數字 if ~ # 如果左邊比右邊大 ~ # 交換 cnt+=1 print(f'Minimum exchange operations : {cnt}') # print('Minimum exchange operations :',cnt) except: break ``` :::warning [e561: 00299 - Train Swapping](https://zerojudge.tw/ShowProblem?problemid=e561) + 計算 Bubble Sort 交換的次數。 ::: ``` python= t=int(input()) for _ in range(t): n=int(input()) a=[*map(int, input().split())] cnt=0 for ~ for ~ if ~ ~ cnt+=1 print(f'~') ``` ### 2. 交換排序(Exchange Sort) vs. 選擇排序(Selection Sort) + [exchange sort](http://it-easy.tw/sorting-algorithm/)：對每個基準點，如果之後的數比它小就交換。 + [selection sort](https://rust-algo.club/sorting/selection_sort/index.html)：跟交換排序法類似，但交換次數較少。對每個基準點，找到其後最小的數值，並進行對調。[GIF變速器](https://www.veed.io/zh-TW/tools/video-speed-controller/gif-speed-changer) + [Selection Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=xWBP4lzkoyM) :::info AL_EX_1_2：[d452: 二、直線最小距離和](https://zerojudge.tw/ShowProblem?problemid=d452) (以選擇排序實作) + 排序後求中位數，中位數與數組各數的距離和最小 ::: ```python= # exchange sort t=int(input()) for _ in range(t): a=[*map(int, input().split())] n=a.pop(0) for i in range(n-1): # 對每個基準點 i for j in range(i+1,n): # 從 i 的右邊開始找最小值 if a[j]<a[i]: # 如果檢查的這個數 < 第 i 個數 a[i],a[j]=a[j],a[i] # 交換 sum=0 for i in range(n): sum+=abs(a[n//2]-a[i]) print(sum) ``` + [蛇形命名法](https://zh.wikipedia.org/zh-tw/%E8%9B%87%E5%BD%A2%E5%91%BD%E5%90%8D%E6%B3%95) ```python= # selection sort，記錄最小值的索引值 t=int(input()) for _ in range(t): a=[*map(int, input().split())] n=a.pop(0) for ~ # 對每個基準點 i，0 到 ?(最後一個不用看) min_idx=i # 預設目前最小值的 index 為 i for ~ # 從 i 的右邊開始找更小的數值 if a[~]<a[~]: # 如果右邊的值 < 目前最小值 ~ # 更新 min_idx ~ # 把找到的最小值(min_idx的值)和基準點交換 sum=0 for i in range(n): sum+=abs(a[n//2]-a[i]) print(sum) ``` ### 3. 插入排序(Insertion Sort) + [insertion sort](https://kopu.chat/2017/06/22/插入排序insertion-sort/)：將還未排序的元素插入到已排序數列中的正確位子。 + [Insertion Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=OGzPmgsI-pQ) :::info AL_EX_1_3：[a104: 排序](https://zerojudge.tw/ShowProblem?problemid=a104) (以插入排序實作) ::: ```python= # insertion sort while True: try: n=int(input()) a=[*map(int, input().split())] for ~ # 第 0 個元素不用處理，當成已排好序的數列 key=a[i] # key(a[i]) 是正在處理的數值 j=i-1 # 設 j 是 i 的前一個 while ~ # 前面的元素(a[?])大於 key，而且 j 沒有小於邊界(j>=0) ~ # 前面的元素(a[?])比 key 大，所以往右移 ~ # j 往前移 ~ # 將 key 放入正確位置 print(*a) except: break ``` ### 4. 快速排序(Quick Sort) + [quick sort1](https://ithelp.ithome.com.tw/articles/10202330?sc=iThelpR) + [quick sort2](http://notepad.yehyeh.net/Content/Algorithm/Sort/Quick/Quick.php) ### 5. 合併排序(Merge Sort) + [merge sort](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-%E6%8E%92%E5%BA%8F%E6%B3%95%E9%80%B2%E9%9A%8E-%E5%90%88%E4%BD%B5%E6%8E%92%E5%BA%8F%E6%B3%95-6252651c6f7e) + [Merge Sort | GeeksforGeeks - YouTube](https://www.youtube.com/watch?v=JSceec-wEyw) ### 6. 排序演算法效率比較 + [Sorting Algorithms Animations](https://www.toptal.com/developers/sorting-algorithms) + [Comparison Sorting Algorithms](https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html) + [排序演算法整理](http://notepad.yehyeh.net/Content/Algorithm/Sort/Sort.php) ![](https://i.imgur.com/BYBK9Bh.png) ### 7. 排序演算法應用 + [自訂排序鍵值函數](https://officeguide.cc/python-sort-sorted-tutorial-examples/) ```python= lst=[5,6,8,3,4,6,7,9,8,2] lst.sort() print(*lst) lst.sort(reverse = True) print(*lst) # 預設依第 1 個元素遞增排序，如果相同則以第 2 個元素遞增排序 seg=[[5,6],[8,3],[4,6],[7,9],[8,2]] seg.sort() print(*seg) # 依第 2 個元素遞增排序，如果相同則以第 1 個元素遞增排序。如 Greedy 作業：HWSH Judge a089: P_4_4 幾場華山論劍(activity selection) https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a089 A1：資料顛倒放。 seg=[[6,5],[3,8],[6,4],[9,7],[2,8]] seg.sort() print(*seg) A2：自訂排序的規則。 seg=[[5,6],[8,3],[4,6],[7,9],[8,2]] seg.sort(key = lambda x: x[1]) # 只依第 2 個元素遞增排序，排序完 [5, 6] [4, 6] 為原順序。 print(*seg) # [8, 2] [8, 3] [5, 6] [4, 6] [7, 9]， seg=[[5,6],[8,3],[4,6],[7,9],[8,2]] seg.sort(key = lambda x: (x[1], x[0])) print(*seg) ``` + lambda(匿名函式) ```python lambda 參數1, 參數2, ... : 運算式 即 def func( 參數1, 參數2, ... ) : return 運算式 ``` ```python= def mul(x,y): return x*y print(mul(5,6)) ``` ```python= mul = lambda x,y: x*y print(mul(5,6)) # (lambda parameter: expression)(argument) # print((lambda x,y: x*y)(5,6)) ``` :::info AL_EX_1_4：[b966: 第 3 題 線段覆蓋長度](https://zerojudge.tw/ShowProblem?problemid=b966) + 開10^7^bool陣列，讀一筆線段就從L標計到R，最後計算標計的數量。時間O(n)*O(10^7^)可行嗎？ 空間？ + 將輸入線段依左端點座標排序。則前後兩線段的關係只可能為重疊(包含相連)或不重疊(新線段) - 如果下一線段的左端點 > 前一線段的右端點，表示前一線段已結束，計算並加總覆蓋長度。 - 如果下一線段的左端點 <= 前一線段的右端點，表示前一條線段可延續，調整前一線段右端點位置即可。 + [掃描線演算法(sweep line algorithm)](http://web.ntnu.edu.tw/~algo/Point2.html) ::: ```python= # 線段沒有重疊，無腦暴力法(38%) ``` ```python= # 線段可能重疊，但 N、L、R 都很小，暴力法(72%) seg=[0]*1000 n=int(input()) cnt=0 for _ in range(n): st,ed=map(int,input().split()) for ~ # 將線段左到右的座標，標記為 1 ~ for ~ # 從頭看一遍 if ~ # 如果座標有標記為 1 ~ # 線段覆蓋長度+1 print(cnt) ``` ```python= n=int(input()) seg=[] for _ in range(n): st,ed=map(int, input().split()) ~ # 將線段[左端點, 右端點]加入串列 ~ # 排序，先看看排序結果 L,R=0,0 total=0 for [st,ed] in seg: # for e in seg: 以 e[0]、e[1] 表示 st、ed 比較不方便 if ~ # 如果「沒有重疊」，此線段的左端點 > 前一線段的右端點 ~ # 結算前一線段的總長度 ~ # 以此線段「開始」座標更新 L，以此線段「結束」座標更新 R else: # 如果「有重疊」，此線段的左端點 <= 前一線段的右端點，表示有可能延伸前一線段 ~ # 更新前一線段的右端點為：max(前一線段右端點，此線段右端點) print(total+(R-L)) # Q：答案為何還要加(R-L)？ 不加，3 條線段 [1,3] [2,4] [3,5] 答案為？ ``` :::warning [a737: 10041 - Vito's family](https://zerojudge.tw/ShowProblem?problemid=a737) + 將所有親戚的門牌號碼排序，中位數即為 Vito 新家的門牌號碼。 ::: ```python= t=int(input()) for _ in range(t): a=[*map(int, input().split())] n=a.pop(0) ~ # 將 a 排序 sum=0 for ~ ~ print(sum) ``` :::warning [d150: 11369 - Shopaholic](https://zerojudge.tw/ShowProblem?problemid=d150) + 將商品價格降序(大->小)排序，再取每三個內的最小值。 + for i in range(2, len(a), 3): ::: :::warning [h075. 成績排名](https://zerojudge.tw/ShowProblem?problemid=h075) + 將每個人的(加權分數，資訊，數學，英文，座號)加入list後排序(reverse=True) + 同分座號小的要在前面，可將座號加上負號。 + 輸出格式 ``` python for x in lst: print(f'{-x[-1]} {x[0]/10:g}') ``` ::: <br/> ## 二、搜尋演算法 + 數列需先排序好才可使用二分搜尋。 + 有效率的原因是一個檢測之後，就可以知道有一半的資料不必再檢測，原因來自於單調性。 + [要定義好搜尋的區間是\[a,b\]或\[a,b)或其它](https://www.itread01.com/content/1548961212.html) - [程式設計中左閉右開區間的廣泛應用](https://www.cnblogs.com/fighlone/p/13526864.html) + 區間選擇不正會確導致無窮迴圈，陣列越界 → 模擬剩下一個元素時，是否能正確執行到結束。 :::info AL_EX_2_1：[d732: 二分搜尋法](https://zerojudge.tw/ShowProblem?problemid=d732) + 陣列的索引值從 0 開始。 + 先練習循序搜尋，結果會如何？(TLE) ::: ``` python= n,k=map(int, input().split()) a=[*map(int, input().split())] q=[*map(int, input().split())] for x in q: # 對q中的每個元素 idx=a.index(x) if x in a else -1 # 如果在 a 裏，輸出其 idx print(idx+1) ``` ``` python= n,k=map(int, input().split()) a=[*map(int, input().split())] q=[*map(int, input().split())] for x in q: ~ # 設一個 bool 變數，表示有沒有找到，預設為 False for ~ # 從頭開始找 if ~ # 如果找到 print(i+1) ~ # bool 變數設為 True，表示找到 ~ # 跳出 for 迴圈 if ~ # 沒找到。Q：不可以直接在 for 迴圈裏的 if 直接加 else 印出 0，例如搜尋 3 會印出？ print(0) ``` ``` python= n,k=map(int, input().split()) a=[*map(int, input().split())] q=[*map(int, input().split())] for x in q: L , R = ~, ~ # 左閉，右開 while ~ # 左邊界index < 右邊界index ~ # 計算 m if ~ # 如果找到 print(~) break elif ~ # 中間值 > x，往左半找 ~ else: # 中間值 < x，往右半找 ~ if ~ # 如果 左邊界index == 右邊界index，表示沒找到 print(0) ``` :::info AL_EX_2_2：[f815: TOI_y21m4_a01遊戲升等](https://zerojudge.tw/ShowProblem?problemid=f815) + [最小值最大化](https://www.796t.com/content/1551625085.html)([e616](https://zerojudge.tw/ShowProblem?problemid=e616)) + 對答案二分搜 - 單調性指序列中的某個條件或屬性隨著序列位置的增長保持一致地變化，例如從滿足變成不滿足後會一直保持不滿足。(單調遞減) - 如果有這樣的性質，則可以用二分搜尋來高效地找到第一個滿足(不滿足)該命題的元素位置。先假設一個答案，檢查這個答案是不是符合條件限制，接著以二分搜的方式逼進。 + 結束狀況討論 ![](https://i.imgur.com/Y2vsqCR.png =500x) ::: ``` python= def gold(m): # 計算到等級 m 需要的金幣 sum=0 for ~ # 拿出每個士兵等級 if ~ # 如果士兵等級 < m ~ # 計算需要的花費後加總 return sum n,c=map(int, input().split()) lv=[*map(int, input().split())] L,R=1,20000001 # 左閉，右開，假設最大等級為2千萬（極端狀況，1位士兵10^7級，c=10^14，可以升到2千萬級） while ~ ~ # 預期的等級 m if ~ # 需要的金幣 > 預算，往左半找 ~ else: # 往右半找 ~ print(~) # Q：答案在？ ``` :::warning [g640: 璽羽的壽司](https://zerojudge.tw/ShowProblem?problemid=g640) + 先將壽司的價格(品質)排序，對每個顧客的最低品質標準，以二分搜找>=標準的最小值。如果標準大於所有壽司的品質，則忽略。 + score:60%以上即可。 ::: ``` python= n,m=map(int, input().split()) a=[*map(int, input().split())] q=[*map(int, input().split())] a.sort() sum=0 for x in q: L,R=0,n # 左閉，右開 while ~ m=(L+R)//2 if ~ sum+=a[m] break elif a[m]>x: R=~ else: L=~ if L==R and L<n: sum+=a[L] print(sum) ``` :::warning [c575: APCS 2017-0304-4基地台](https://zerojudge.tw/ShowProblem?problemid=c575) + 對n個服務點排序，並計算服務點兩兩相鄰距離。若要分成K群，則找出前K-1個最大的兩兩相離距離，作為分群切割處。(時間複雜度高) + 實做可用二分搜的觀點。因為基地台直徑的答案一定介於1~(最遠服務點-最近服務點)。先假設可能答案為最大最小值中間，測試k個基地台可否覆蓋所有服務點，不行則調整基地台直徑，以二分搜尋法找出答案(直接對答案進行二分搜)。 ::: :::warning [e616: Aggressive cows](https://zerojudge.tw/ShowProblem?problemid=e616) + [最小值最大化](https://blog.csdn.net/qq_43690454/article/details/104020240) + 對答案二分搜。假設一個答案，檢查這個答案是不是符合條件限件，以二分搜的方式逼進最大值。 ::: <br/> ## 三、貪婪(greedy)演算法 + 假設一個問題可以藉由一系列的選擇來解決，貪婪演算法為在每一步的選擇中，都採取在當前狀態下的最佳選擇，從而希望導致結果是最佳解的演算法。 + [使用貪婪策略的演算法](https://blog.csdn.net/weixin_46072771/article/details/106365035) - 活動選擇(Activity Selection Problem) - 物品可分割背包問題(Fractional Knapsack Problem) - 霍夫曼編碼（Huffman Coding） - 最小生成樹(Min spanning tree problem) : Kruskal’s algorithm and Prim’s algorithm - Dijkstra 最短路徑演算法 :::info AL_EX_3_1：[HWSH Judge a086: P_4_1 少林寺的代幣](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a086) [TCFSH CIRC Judge d042: 例題 P-4-1. 少林寺的代幣](https://judge.tcirc.tw/problem/d042) + 當代幣之間不一定是倍數關係時(如 1、3、4)，局部最佳解不一定會組成全局最佳解。 + 運用 [] 取值，可以使用 index(索引值從0開始)、slice 來存取陣列裡的資料。lst[i:j:k] 可取出索引值 i ~ j-1 的，間隔為k的元素。 ::: ```python= coin=[1,5,10,50] m=int(input()) for _ in range(m): n=int(input()) cnt=0 for ~ # 從 50 元開始換 ~ # 計算可換出的數量 ~ # 剩下沒換零錢的金額 print(cnt) ``` :::info AL_EX_3_2：[f627: 1. 礦砂採集](https://zerojudge.tw/ShowProblem?problemid=f627) + [物品可分割背包問題(Fractional Knapsack Problem)](http://web.ntnu.edu.tw/~algo/KnapsackProblem.html)(選擇物品時，可以只拿物品的一部分，不必須全部拿) - 如果物品不可分割(0-1背包問題)，greedy可行嗎？(範例如[六、2_2. 0-1背包問題](#0-1背包問題)) + 依單位重量價值由大到小排序(reverse=True)。 + 不斷將單位重量價值最大的礦砂放入背包，直到背包已滿或沒有礦砂可放入。 ::: ```python= n,m=map(int, input().split()) ore=[] for _ in range(n): w,p=map(int, input().split()) ~ # 預設依第 1 個元素遞增排序，如果相同則以第 2 個元素遞增排序。因為要根據單位重量價值排序，所以將[p,w]放入串列 ~ # 根據單位重量價值由大到小排序 # 先印出來看看 sum=0 # 礦沙總價值 for ~ # 將每個礦砂list取出 if ~ # 背包重量 > 此礦沙重量 ~ # 更新總價值(將此礦沙全部放入背包) ~ # 背包重量扣掉此礦沙重量 else: # 背包重量 <= 此礦沙重量，沒空間可以放下一個 ~ # 更新總價值(背包剩下的重量全部放此礦沙) break print(sum) ``` :::warning [HWSH Judge a088: P_4_3 十年磨一劍(最少完成時間)](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a088) [TCFSH CIRC Judge d044: 例題 P-4-3. 十年磨一劍(最少完成時間)](https://judge.tcirc.tw/problem/d044) + minimum completion time 經典題 + 放在越前面的工作，等它的人越多，所以短的工作先做。 ::: ```python= n=int(input()) a=[*map(int, input().split())] ~ # 先以 sort 函式將 a 串列由小->大排序 comp,total=0,0 # comp為每把劍磨完時間，total為完成時間之總和 for ~ # 對每一個所需時間 ~ # 計算此劍完成時間 ~ # 計算完成時間總和 print(total) ``` :::warning [HWSH Judge a089: P_4_4 幾場華山論劍(activity selection)](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a089) [TCFSH CIRC Judge d045: 例題 P-4-4. 幾場華山論劍(activity selection)](https://judge.tcirc.tw/problem/d045) + activity selection problem 經典題 + 若[x,y]是還未選取線段中右端點最小的線段，那麼最佳解一定會挑選[x,y]。 + 一開始依照右端點由小到大排序，然後不斷將最小右端的線段挑進最佳解，略過與它重疊的線段。 ::: :::warning [f832: 隕石 (Meteorite)](https://zerojudge.tw/ShowProblem?problemid=f832) + 將隕石重量、捕捉器容量排序 + 由捕捉器容量大到小，決定是否可以裝入此時最大重量的隕石。 ::: <br/> ## 四、分治(divide & conquer)演算法 ### 1. 遞迴複習 :::info AL_EX_4_1：[a623: 3. Combination](https://zerojudge.tw/ShowProblem?problemid=a623) + 以遞迴求組合數。 + $C^n_m = C^{n-1}_m + C^{n-1}_{m-1}$ + $n==m \ 或 \ m==0$ 時，只有一種組合方式。 ::: ```python= def c(n,m): if ~ # 終止條件 return 1 else: ~ # 遞迴呼叫 while True: try: n,m=map(int, input().split()) print(c(n,m)) except: break ``` ### 2. 區域變數 vs. 全域變數 - 在函式中的變數為區域變數，在函式外的變數為全域變數。 ``` python= def fun(): a = 10 # 此處的 a 為區域變數 print('函式內',a) a = 5 # 此處的 a 為全域變數 fun() print(a) # a 印出5 ``` ``` python= def fun(): global a # 使用全域變數 a a = 10 print('函式內',a) a = 5 # 此處的 a 為全域變數 fun() print(a) # a 被函式改變，印出 10 ``` ``` python= def fun(): print('函式內',a) # 可以使用全域變數 a，印出 5 a = 5 # 此處的 a 為全域變數 fun() ``` ```python= def fun(a): # 更改參數 a 不會影響函式外的變數 a = 10 print('函式內',a) a = 5 fun(a) print(a) ``` :::info AL_EX_4_2：[f637: DF-expression](https://zerojudge.tw/ShowProblem?problemid=f637) + [解題參考](https://www.youtube.com/watch?v=LMlQIJoU6PA) + 測資 | ![](https://i.imgur.com/PqOBL6H.png =140x) | ![](https://i.imgur.com/oQ5mLc9.png =140x) |![](https://i.imgur.com/GDhJApH.png =140x) |![](https://i.imgur.com/cvJNgmb.png =250x)| | :--- | :--- | :--- | :--- | | 1<br>8<br>ans=64<br>| 20101<br>8<br>ans=32<br>| 202010101<br>8<br>ans=24<br>|| ::: ```python= def f(n): global s,idx idx+=1 if s[idx]=='0': return 0 elif ~ # 1 表示全部都是黑色，回傳 n*n ~ else: # 2 表示均分為四小塊，用遞迴把四小塊的結果加總回傳 # return f(n//2)+f(n//2)+f(n//2)+f(n//2) sum=0 for ~ ~ return sum s=input() n=int(input()) idx=-1 print(f(n)) ``` + [Python中next()函数、iter()以及next(iter())函数的用法详解](https://blog.csdn.net/weixin_42782150/article/details/109315355) + [深入理解 Python 中的循环和迭代](https://www.freecodecamp.org/chinese/news/loops-and-iterations-in-python/) ```python= def f(n): nx=next(it) # 每從迭代器中取出一項，那一項即從迭代器中「消失」。 if nx=='0': return 0 elif nx=='1': return n**2 else: return sum(f(n//2) for _ in range(4)) it=iter(input()) n=int(input()) print(f(n)) ``` :::warning [e357: 遞迴函數練習](https://zerojudge.tw/ShowProblem?problemid=e357) ::: ```python= ~ # 定義遞迴函數f(x) if ~ # x等於1 ~ # 直接回傳 1 elif ~ # x為偶數 ~ # 回傳 f(x/2)，// 取商 else: ~ # 回傳 f(x-1)+f(x+1) n=int(input()) print(f(n)) ``` :::warning [c002: 10696 - f91](https://zerojudge.tw/ShowProblem?problemid=c002) ::: ### 3. 步驟 + 分割(divid)：將原本的問題分割成多個子問題(規模較小的同類問題)。 + 克服(conquer)：當子問題劃分得足夠小時，用相同的演算法遞迴地解決所有的子問題。 + 合併(combine)：合併(merge)所有子問題的解答成為原本問題的解答。(不一定所有的問題都需要，快速排序 vs. 合併排序) ### 4. 優點 + 將問題分割，較易解決困難的問題。(河內塔) + 可以找出比較有效率的演算法。(合併排序) + 能夠平行處理。(快速排序) ### 5. 分治經典問題 + [找出較輕的假幣](https://market73228.pixnet.net/blog/post/11996380) + 二分搜尋 + 快速排序 + 合併排序 + [河內塔](http://www.novelgames.com/zh-HK/tower/) + [逆序數對](https://zh.wikipedia.org/wiki/%E9%80%86%E5%BA%8F%E5%AF%B9) + [平面最近點對](https://oi-wiki.org/geometry/nearest-points/) + [缺陷棋盤填滿](https://xie.infoq.cn/article/65ba1aaa2135b23eb6180e3ff) :::info AL_EX_4_3：[d219: 00374 - Big Mod](https://zerojudge.tw/ShowProblem?problemid=d219) + [分配律](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 + 測資輸入 b p m 為同一行。 ::: ```python= def dc(b,p,m): if p==0: return 1 elif p==1: ~ else: half=~ # 先算出 b^(p/2)%m if ~ # p 為偶數，( b^(p/2)%m * b^(p/2)%m ) % m # return dc(b,p//2,m)*dc(b,p//2,m)%m return ~ else: ~ # p 為奇數要比偶數時多乘一次b while True: try: b,p,m=map(int, input().split()) print(dc(b,p,m)) except: break ``` :::info AL_EX_4_4：[a233: 排序法~~~ 挑戰極限](https://zerojudge.tw/ShowProblem?problemid=a233)(以合併排序實作) + 時間複雜度O(n^2^)的排序法會TLE + [步驟說明](https://www.cnblogs.com/pythonbao/p/10800699.html) + [L, R) 分為 [L, mid) + [mid, R) 處理。 [L, R) 中元素個數為 R-L。 + [C++ 與 Python 的輸入輸出優化](https://akr.tw/post/6) ::: ```python= import sys def merge_sort(a): if len(a)<=1: return a mid=len(a)//2 left=merge_sort(a[:mid]) # 左半邊以 merge_sort 排序好 ~ # 右半邊以 merge_sort 排序好 output=[] i,j=0,0 while ~ # 將左、右半邊已排序好的序列，依序放至 output 陣列。(i、j 還沒到底) if left[i]<=right[j]: output.append(left[i]) i+=1 else: ~ ~ output+=left[i:] # 當左半邊沒放完 ~ # 當右半邊沒放完 return output n=int(sys.stdin.readline()) a=[*map(int, sys.stdin.readline().split())] sys.stdout.write(' '.join([str(c) for c in merge_sort(a)])) # score:75% # n=int(input()) # a=[*map(int, input().split())] # print(*merge_sort(a)) ``` ```python= # 如果函式參數為可變的(mutable)物件，如list時，在函式中對 list 的修改，也會影響 list 變數。 def f(lst): lst[0]=5 lst=[1,2,3] f(lst) print(lst) ``` ```python= # 在原始串列處理，儘量不搬動，但 score:45% def merge_sort(a): if len(a)<=1: return mid=len(a)//2 left=a[:mid] right=a[mid:] merge_sort(left) merge_sort(right) i,il=0,0 # i 為主串列索引，il 為左半索引 for x in right: while il<len(left) and left[il]<=x: a[i]=left[il] i+=1 il+=1 a[i]=x i+=1 while il<len(left): a[i]=left[il] i+=1 il+=1 n=int(input()) a=[*map(int, input().split())] merge_sort(a) print(*a) ``` :::warning [d636: 大爆炸bomb](https://zerojudge.tw/ShowProblem?problemid=d636) ::: ```python= def dc(a,b): if b==0: return ~ elif b==1: return ~ else: ~ # 先算出 a^(b/2)%10007 if ~ # b 為偶數 ~ else: # b 為奇數 ~ a,b=map(int, input().split()) print(dc(a,b)) ``` :::warning [a227: 三龍杯 -> 河內之塔](https://zerojudge.tw/ShowProblem?problemid=a227) + [解題參考](http://notepad.yehyeh.net/Content/DS/CH02/4.php) ::: :::warning [HWSH Judge a101: P_5_4 反序數量 (APCS201806) ](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a101)[TCFSH CIRC Judge d064: P-5-4. 反序數量 (APCS201806) ](https://judge.tcirc.tw/problem/d064) + 類似 a233 合併排序 score:45% 作法。 + [資訊之芽算法班 第六週 Divide and conquer](https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week06/divide_and_conquer.pdf) + 如果看成從前往後掃，對於每個數a[i]只要能求在i之前有多少大於它的數，即可用線段樹來做。[參考網站](https://zh.codeprj.com/blog/4c8dff1.html) ::: <br/> ## 五、樹搜尋(tree search)與回溯(backtracking)演算法 + 許多問題尋找解答的過程可以表示成樹，建構出解答空間樹(solution space tree)，因此找解答就轉變成一個樹搜尋問題。 + [回溯法](https://www.youtube.com/watch?v=nrHTtjkYEyQ)是暴搜法的一種，用來枚舉所有的候選解。在進行未拜訪節點選擇時，可以先選擇可能會有好結果的分支，或是提早判斷若無解，就不遞迴至下一層，而是回溯退回先前的節點。 + [DFS](https://jason-chen-1992.weebly.com/home/-graph-searching-methods) vs. 回溯 (backtracking) - DFS 可視為回溯法的一種型態，DFS 會遍訪每一個未拜訪過的子節點，如果該節點為樹葉節點，就退回其父節點再遍訪其它分支的節點，強調搜尋的順序。 - 回溯法強調剪枝(pruning)，剪掉不符合條件的分枝，不再繼續遞迴下去。 - [DFS 遇到拜訪過的節點會馬上回溯，backtracking 遇到不合理的解答會馬上回溯。](http://web.ntnu.edu.tw/~algo/Backtracking.html#1) :::info AL_EX_5_1：[d908: 4. 最佳路徑](https://zerojudge.tw/ShowProblem?problemid=d908) + DFS + [相鄰矩陣表示法(Adjacency Matrix)](http://web.ntnu.edu.tw/~algo/Graph.html#3) + Q：NA(score:80%)？ A：有些線段會重複，記錄此線段的最大權重。 ::: ```python= def dfs(now): sum=0 # 從此點往下的路徑總和 for ~ # 從此點(now) 往下檢查 26 個字母是否相連 if ~ # 如果 now 有連到 i (而且 i沒走過) ~ # 從 i 繼續往下走，路徑的權重總和為 now->i 這一段的權重 + 從 i dfs 下去的權重和。取最大值。 return sum s=input() s=ord(s)-ord('A') # A 轉為 0，B 為 1 …， n=int(input()) g=[[0]*26 for i in range(26)] # 初始化一個26*26矩陣，初值均為 0 for _ in range(n): u,v,w=input().split() u=ord(u)-ord('A') # A 轉為 0，B 為 1 …， v=~ w=int(w) ~ # 將相鄰矩陣g[u(轉為數字)][v(轉為數字)]的值設為w ''' 先把範例一的相鄰矩陣印出來看看 for row in g: print(row) 0 7 1 0 0 0 0 0 0 3 5 0 0 0 0 0 0 2 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 ''' print(dfs(s)) ``` :::info AL_EX_5_2：[i644. 列舉八皇后問題所有解](https://zerojudge.tw/ShowProblem?problemid=i644) + backtracking + 以一維陣列 row[9] ([1-based indexing](https://xlinux.nist.gov/dads/HTML/oneBasedIndexing.html)) 記錄皇后的座標。陣列索引為皇后的col，值為皇后的row。 | ![](https://i.imgur.com/9bVpKmW.png =180x) | q[1]={1,1}<br>q[2]={3,2}<br>q[3]={5,3}<br>$\vdots$<br><br>row[1]=1<br>row[2]=3<br>row[3]=5<br>$\vdots$| | -------- | :--------: | + [皇后衝突的判斷](https://iter01.com/kmw2YoS.html) [![](https://i.imgur.com/JWKOD70.png =63x)](https://i.imgur.com/JWKOD70.png)　[![](https://i.imgur.com/kmw2YoS.png =50x)](https://i.imgur.com/kmw2YoS.png) + [棋盤](https://www.datagenetics.com/blog/august42012/) ::: ```python= def attack(r, c): for ~ # 檢查是否衝突到之前已擺放的皇后 if ~ # 在同一列或對角(abs) return True # 表示衝突到 return False def place(c): # 填第幾 col ，即填第幾個皇后 for ~ # 每一列(1~8)都試試看 if ~ # 如果放在 r 列, c 欄的皇后不會衝突之前已擺放的皇后 ~ # 記錄此皇后的位置 if c==8: global cnt print(str(cnt) + ': ' + ~) cnt+=1 else: ~ # 繼續擺下一個皇后 row=[0]*9 # index 為皇后的 col，值為 row cnt=1 place(1) ``` :::info AL_EX_5_3：[c812: 1. 觀光景點](https://zerojudge.tw/ShowProblem?problemid=c812) + [相鄰串列表示法(Adjacency Lists)](http://web.ntnu.edu.tw/~algo/Graph.html#4) ```python g=[[0]*26 for i in range(26)] # 初始化一個26*26矩陣 g=[[] for _ in range(5)] # 相鄰串列，每列放相鄰的點，或[點，邊] ``` + 有三組測資因預設遞迴深度不足會出現 RecursionError: maximum recursion depth exceeded in comparison。需加上 sys.setrecursionlimit(10000) ::: ```python= import sys sys.setrecursionlimit(10000) def dfs(now,r): # r 為起點到現在的點(now) 的相關性 global ans if ~ # 起點到現在的點(now) 的相關性至少為 q ans+=1 for ~ # 對每個連到 now 的節點(nxt) if ~ # 如果 nxt 沒走過 ~ # 將現在的點(now)設為走過 ~ # 從 nxt 繼續往下走，重新估算路徑的相關性 g=[[] for _ in range(5005)] vis=[0]*5005 n,vk,q=map(int, input().split()) for _ in range(n-1): i,j,rij = map(int,input().split()) g[i].append([j,rij]) ~ # 無向圖，i 連到 j ， j 也連到 i ''' 先把範例二的相鄰串列印出來看看 for row in g[:10]: print(row) 1 : [ [6,4] ] 2 : [ [4,10], [3,6] ] 3 : [ [6,3], [5,8], [2,6] ] 4 : [ [2,10] ] 5 : [ [3,8] ] 6 : [ [3,3], [1,4] ] ''' vis[vk]=1 ans=0 dfs(vk,1e9) print(~) # 答案不是 ans，Why？ ``` :::warning [j124: 3. 石窟探險](https://zerojudge.tw/ShowProblem?problemid=j124) + 類似 d908 ::: ```python= def dfs(u): # 找 u 的孩子 v ~ # 使用全域變數 seq 和 idx total_diff=0 for i in range(2+u%2): # 偶數做2次，奇數做3次 idx+=1 v= ~ # v 在 seq 中 idx 的地方 if ~ # 如果 v 有編號，不是 0 total_diff+=~ # u、v差的絕對值，再加上 v 之下差的總和(遞迴) return total_diff seq=[*map(int, input().split())] idx=0 print(dfs(seq[0])) ``` :::warning [a290: 新手訓練系列 ~ 圖論](https://zerojudge.tw/ShowProblem?problemid=a290) + 相鄰串列 + input().split()會 TLE，改用 sys.stdin.readline().split()。需 import sys。 ::: :::warning [d626: 小畫家真好用](https://zerojudge.tw/ShowProblem?problemid=d626) + 分四個方向做DFS。 ```python= # 輸入 mp=[] for _ in range(n): mp.append(list(input())) # 輸出 for i in range(n): print(''.join(mp[i])) ::: :::warning [b554. 5.貪吃龍遊戲](https://zerojudge.tw/ShowProblem?problemid=b554) + backtracking。 + [解題參考](https://hackmd.io/@cyk/112/https%3A%2F%2Fhackmd.io%2F%40cyk%2Fbacktracking#%E7%A8%8B%E5%BC%8F%E7%A2%BC) ::: <br/> ## 六、動態規劃(Dynamic Programming、DP) + [動態規劃簡介](https://mropengate.blogspot.com/2015/01/algorithm-ch2-dynamic-programming.html) + [一個問題若能用 DP 求解，該問題含有以下三個性質](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/HknO-zmQI/https%3A%2F%2Fhackmd.io%2Fs%2FByfT8JZ9E#Week-9-Dynamic-Programming-%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83) - 最佳子結構(optimal substructure)：最佳解能夠由子問題的最佳解構成。([分治與貪心法同樣有著這個特性](https://hackmd.io/@XDEv11/NCKU-AdvCP-2021-DP#%E5%8B%95%E6%85%8B%E8%A6%8F%E5%8A%83%E5%95%8F%E9%A1%8C%E7%9A%84%E7%89%B9%E6%80%A7)) - 重疊子問題(overlapping subproblem) - 無後效性：子問題的解一但確定，就不會受到更大的問題的求解決策影響。 + 規劃步驟 1. 定義子問題(狀態定義)。 - 定義存最佳解的 dp[i] 的 i 是什麼狀態。 2. 找出問題與子問題之間的遞迴關係(狀態轉移方程)。 - 思考 dp[i] 如何用已求得的 dp[i-1], dp[i-2] … 來計算，或思考已求得的 dp[i] 如何延伸去計算 dp[i+1], dp[i+2] …。 - 再思考狀態轉移方程時，要不斷催眠自己 dp[i] 已知道答案，才較容易得到問題與子問題之間的遞迴關係。 3. 規劃初始狀態及轉移順序，避免以遞迴的方式進行計算。(以空間換取時間) - dp[0] 設定初始值。 + 一個DP如果狀態有 O(n^x^) 而狀態轉移方程涉及 O(n^y^) 個狀態，一般可稱為 xDyD 的 DP。 ### 1. 1D0D :::info AL_EX_6_1：[HWSH Judge a106: P_6_2 不連續的表演酬勞](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a106) [TCFSH CIRC Judge d067: P-6-2. 不連續的表演酬勞](https://judge.tcirc.tw/problem/d067) + 每天可以獲得的酬勞放在一維陣列p[]中。 + 狀態定義： dp[i] 是前 i 天可以獲得的最大報酬。 + 狀態轉移方程 - 如果第 i 天不選，前 i 天的獲利就是前 i-1 天的獲利 dp[i]=dp[i-1]。 - 如果第 i 天要選，可以獲利 p[i]，但是第 i-1 天就不可以選，因此最大的獲利是 p[i]+dp[i-2]。 - dp[i]=max(dp[i-1], p[i]+dp[i-2])。 ::: ```python= n=int(input()) p=[*map(int, input().split())] dp=[0]*100005 # dp[i] 記錄到第 i 天的最大報酬 dp[0]=~ dp[1]=~ for ~ # 計算第3~n天的報酬 ~ # 遞迴關係式 print(dp[n-1]) ``` :::warning [d038: 00900 - Brick Wall Patterns](https://zerojudge.tw/ShowProblem?problemid=d038) + dp(1)=1，dp(2)=2 + dp(n)=dp(n-1) + dp(n-2) ::: :::warning [d054: 11310 - DELIVERY DEBACLE](https://zerojudge.tw/ShowProblem?problemid=d054) + dp(0)=1，dp(1)=1，dp(2)=5 + dp(n)=dp(n-1) + 4\*dp(n-2) + 2\*dp(n-3) + [解題參考](http://kos74185foracm.blogspot.kr/2011/06/11310-delivery-debacle.html) ::: ### 2. 2D0D #### 2_1. [最長共同子序列(LCS)](https://yuihuang.com/dp-lcs/) + 狀態定義 - lcs(i, j) 為 x 的前 i 個字元（x[0]~x[i-1]），與 y 的前 j 個字元（y[0]~y[j-1]），最長共同子序列的長度。 - x 字串的 index 由 0 開始，長度 i 的最元素為x[i-1]。 + 狀態轉移方程 - $$ lcs(i,j)= \begin{cases} 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\ \ \ if \ i=0 \ or \ j=0 \\[2ex] lcs(i-1,\ j-1)+1\qquad\qquad\qquad\ \ if \ x[i]=y[j] \\[2ex] max(lcs(i-1,j),\ lcs(i,j-1))\qquad otherwise \end{cases}\qquad\qquad\qquad\qquad\qquad\qquad\qquad $$ + [步驟說明](https://www.youtube.com/watch?v=uX-PJiNVHrs&t=17m33s) :::info AL_EX_6_2：[c001: 10405 - Longest Common Subsequence](https://zerojudge.tw/ShowProblem?problemid=c001) ::: ```python= while True: try: x=input() y=input() dp=[[0]*1005 for i in range(1005)] for ~ # x 的所有元素 for ~ # y 的所有元素 if ~ # x,y 最後一個元素相同 ~ else: # x,y 最後一個元素不同 ~ print(dp[~][~]) except: break ``` :::warning [d378: 最小路徑](https://zerojudge.tw/ShowProblem?problemid=d378) + [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d378) ::: :::warning [a133: 10066 - The Twin Towers](https://zerojudge.tw/ShowProblem?problemid=a133) + [解題參考](https://www.youtube.com/watch?v=7qN9Wg0jmJo) ::: :::warning [a252: Another LCS](https://zerojudge.tw/ShowProblem?problemid=a252) + dp=[[[0]*101 for _ in range(101)] for _ in range(101)] ::: :::warning [i429. 4. 內積 (時限放寬版，給 Python 使用者)](https://zerojudge.tw/ShowProblem?problemid=i429) + [解題參考](https://www.youtube.com/watch?v=EvyyRNAnAtE) ::: #### 2_2. <span id="0-1背包問題">[0-1背包問題](https://www.cnblogs.com/lyeeer/p/12771929.html)</span> + 有 n 個物品，每個物品有重量 w 跟價值 v，背包有最大負重，求在物品不可以分割不重複的情況下，背包可以裝的最大價值為何？ - 相對於物品可分割背包問題，在選擇物品時，要麼完整地選擇，要麼不選擇，不可以只拿物品的一部份(物品不可分割)。 - Greedy不行，假設背包負重30kg，會得到190(50+140)，但最大價值為200(60+140)。 |物品|重量|價值|價值/重量比| |:-:|:-:|:-:|:-:| |1 |5 |50 |10| |2 |10 |60 |6 | |3 |20 |140|7 | - 窮舉法會太多狀況，n 個物品，每個物品可以選擇拿或不拿，會有 2^n^ 種可能性要考慮(例如 d637，n=10000)。 + 狀態定義 - dp[i][j]表示只考慮拿前 i 個物品，放入最大負重為 j 的背包時，可以得到的最大價值。 + 狀態轉移方程 - 假設第 i 項物品的重量為 w[i]，價值為 v[i]。 - 如果 w[i]>j，根本不可能挑選。 - 如果拿第 i 項物品，背包重量剩 j-w[i] (可以從i-1項挑選)，亦即在負重 j 時，第 i 個物品不拿時的價值，與拿了第 i 個物品時的價值，選擇較好的那個。 - $$ dp(i,\ j)=\begin{cases} 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ \ \ if \ i=0 \ or \ j=0 \\[2ex] dp(i-1,\ j) \qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad\ if \ w[i]> j\\[2ex] max(\ dp(i-1,\ j),\ dp(i-1,\ j-w[i]) + v[i]\ )\quad otherwise \qquad\qquad\qquad\qquad\qquad \end{cases} $$ - ![](https://i.imgur.com/W3NOKXG.png) :::info AL_EX_6_3：[d637: 路過的鴨duck](https://zerojudge.tw/ShowProblem?problemid=d637) + [解題參考](https://sites.google.com/a/mail.hpsh.tp.edu.tw/pc/jiao-cai/d637-duck) ::: ```python= dp=[[0]*105 for _ in range(10005)] w=[0]*10005 # w[i]表飼料的體積(物品重量) v=[0]*10005 # v[i]表飼料的飽足感(物品價值) n=int(input()) for i in range(1,n+1): w[i],v[i]=map(int, input().split()) for ~ # 考慮每一個物品要不要拿 for ~ # 考慮每一個背包重量 if ~ # 如果第 i 個物品的重量 > 背包重量，則不拿 ~ else: # 如果如果第 i 個物品放的下，在拿或不拿中選較大的 ~ print(dp[n][100]) ``` :::info AL_EX_6_4：[b184: 5. 裝貨櫃問題](https://zerojudge.tw/ShowProblem?problemid=b184) + [空間優化](https://blog.csdn.net/weixin_44176696/article/details/105209974)([滾動DP](https://hackmd.io/@fdhscpp110/Sk21ZDbvd))：更新藍色格子只需要紅色格子的資料。 ![](https://i.imgur.com/6IPdibf.png) + 若狀態定義 dp(j) 為背包重量為 j 時的最大價值。 + 對第 i 個物品，考慮不拿或拿，狀態轉移方程為 - dp(j)=max( dp(j), dp(j-w[i])+v[i] ) + Q：[如果如上一題由背包重量小->大更新表格，會有什麼問題？](https://hackmd.io/@3xOSPTI6QMGdj6jgMMe08w/ByfT8JZ9E?type=view#01-%E8%83%8C%E5%8C%85%E5%95%8F%E9%A1%8C) A：<font color="#d9edf6">若 dp(j−w[i]) 已經拿 i 物品，更新到 dp(j) 時，拿 i 物品也有較大價值，因為 dp(j)=dp(j−w[i])+v[i]，dp[j] 相當於拿了兩次 i 物品，違反物品只能拿一次的要求。 調整 j 由大->小更新表格，則可避免物品重複拿。</font> ::: ```python= while True: try: dp=[0]*105 w=[0]*105 # w[i]表體積 v=[0]*105 # v[i]表利潤 n=int(input()) for i in range(1,n+1): w[i],v[i]=map(int, input().split()) for ~ # 考慮每一個貨物要不要拿 for ~ # 對這個貨物，從體積 100 往前檢查 ~ # 裝這個貨物的價值比較大，dp[j]就設定成新的(較大的)價值 print(dp[100]) except: break ``` :::warning [b140: NOIP2005 3.採藥](https://zerojudge.tw/ShowProblem?problemid=b140) ::: :::warning [b131: NOIP2006 2.开心的金明](http://zerojudge.tw/ShowProblem?problemid=b131) + [解題參考](https://sites.google.com/view/zsgititit/home/c-cheng-shi-she-ji/b131-noip2006-2-kai-xin-de-jin-ming) ::: :::warning [a522. 12455 - Bars](http://zerojudge.tw/ShowProblem?problemid=a522) + 只是 weight 和 value 一樣的 0/1 背包問題。 + 對第 i 個金屬棒，考慮不拿或拿，狀態轉移方程為 - dp(j)=max( dp(j), dp(j-bar[i])+bar[i] ) ::: :::warning [HWSH Judge a214: Q_6_10 置物櫃出租 (APCS201810)](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a214) [TCFSH CIRC Judge d075: Q-6-10. 置物櫃出租 (APCS201810)](https://judge.tcirc.tw/problem/d075) + 以0-1背包問題的方法，計算剩下空間(總空間-王老要的空間)的最大利益。 + 目前的利益-剩下空間的最大利益即是王老損失的利益。 + [解題參考](https://www.youtube.com/watch?v=0SNyjUl2t4A) ::: #### 2_3. (Bonus) 零錢問題 + [狀態定義 & 狀態轉移方程](https://yuihuang.com/change-coins/) :::info AL_EX_6_5：[d904: 換零錢](https://zerojudge.tw/ShowProblem?problemid=d904) + [解題參考](https://home.gamer.com.tw/artwork.php?sn=4182930) + 零錢可重複，檢查金額時，不需如 b184 大到小檢查。 ::: ```python= coin=[] dp=[1e9]*1005 # dp[]存每種金額，最少的硬幣數量 dp[0]=0 c,n=map(int, input().split()) for _ in range(n): coin.append(int(input())) for ~ # 對每一個種硬幣 for j in range(~, ~): # 對每一金額 j (硬幣幣值以上金額)，重新檢查硬幣數是否會改變 dp[j]=~ # 更新此金額的硬幣數量 print(dp[c]) ``` :::warning [d253: 00674 - Coin Change](https://zerojudge.tw/ShowProblem?problemid=d253) + [解題參考](https://zrn-code.github.io/2020/09/17/d253/) ::: :::warning [b232: TOI2009 第四題：分房子](https://zerojudge.tw/ShowProblem?problemid=b232) + 將1,3,5,7,9…視為幣值，n間房子視為金額 + dp[j]=dp[j]+dp[j-coins[i]] ::: ### 3. 1D1D + 有O(n)個子問題(狀態)，一個子問題(狀態)的計算會牽涉O(n)個前置狀態。 + 如果直接計算時間複雜度為O(n^2^)，很多1D1D的問題會利用資料結構或問題的特性來降低複雜度。 #### [最長遞增子序列(LIS)](http://web.ntnu.edu.tw/~algo/Subsequence.html) + 狀態定義 - dp[i] 表示以 s[i] 為結尾的最長遞增子序列長度(s[0]~s[i]的 LIS 長度) + 狀態轉移方程 - dp[i]=max{ dp[j]+1：0<=j<i and s[j]<s[i] } + 範例 | s[0] | s[1] | s[2] | s[3] | s[4] | s[5] | |:----:|:----:|:----:|:----:|:----:|:----:| | 2 | 7 | 4 | 1 | 8 | 3 | + dp 陣列 | s[] | 2 | 7 | 4 | 1 | 8 | 3 | |:------------------:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 | | dp 陣列值 (s[]為結尾的LIS 長度) | 1 | | | | | | | 7 可接在 2 後 | 1 | 2 | | | | | | 4 可接在 2 後 | 1 | 2 | 2 | | | | | 1 無法接在任何數後 | 1 | 2 | 2 | 1 | | | | 8 可接在 4 後 | 1 | 2 | 2 | 1 | 3 | | | 3 可接在 1 後 | 1 | 2 | 2 | 1 | 3 | 2 | :::info AL_EX_6_6：[HWSH Judge a113: P_6_15 一覽衆山小](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a113) [TCFSH CIRC Judge d078: P-6-15. 一覽衆山小](https://judge.tcirc.tw/problem/d078) + 先完成O(n^2^)的方法。(TLE) ::: ```python= n=int(input()) s=[*map(int, input().split())] # 戰力值 dp=~ # dp[i]表示以s[i]為结尾的最長遞增子序列長度(s[0]~s[i]的LIS長度)。初始化為1(每一個數字本身就是長度為一的 LIS) for ~ # 找出 s[i] 能接在哪些數字後面 for ~ # 檢查 j=0~i-1 if ~ # 如果 s[i]>s[j]，表示 s[i] 能接在 s[j] 後面 ~ # dp[j]+1 若大於 dp[i]，更新為新長度 print(max(dp)) # dp[]之中最大的值即為 LIS 的長度 ``` + 上面的做法，對每個 i 點，都要往前搜尋所有的 j 點，時間複雜度為O(n^2^)，如何加速？(省略不必要的計算) - 如果 s[i]<=s[j] (i>j)，但 dp[i]>=dp[j]，表示s[i]的值比較小，但有比較長的 LIS。那麼可以接在 s[j] 後面的一定也可以接在 s[i] 後面。 * 例如上一個例子，2 4 可以取代 2 7，後面如果有 5 可發展出更長 的 LIS。所以對之後的數字，2 7 不需要再檢查。 * Q：如果刪除沒有用的子問題結果，會剩下甚麼呢？ A：<font color="white">每一種 LIS 長度只會有一個狀態被留下來$\Rightarrow$ 結尾數值最小的狀態。</font> | s[] | 2 | 7 | 4 | 1 | 8 | 3 | |:-----:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 | | LIS 長度| ~~1~~ | ~~2~~ | ~~2~~ | 1 | 3 | 2 | * Q：增加一個元素 5 ，表格會調整為？ | s[] | 2 | 7 | 4 | 1 | 8 | 3 | 5 | |:-----:|:---:|:---:|:---:|:---:|:---:|:---:|:---:| | LIS 的元素 | 2 | 2 7 | 2 4 | 1 | 2 4 8| 1 3 |<font color=white>1 3 5</font>| | LIS 長度| ~~1~~ | ~~2~~ | ~~2~~ | 1 | <font color=white>~~3~~</font> | 2 | <font color=white>3</font>| - 以陣列 last[L] 記錄 LIS 長度為 L 的最後一個元素(選值最小的，讓後續數字有機會發展出更長的 LIS) + 範例 | s[0] | s[1] | s[2] | s[3] | s[4] | s[5] | s[6] | s[7] | |:----:|:----:|:----:|:----:|:----:|:----:|:----:| :---: | | 2 | 8 | 6 | 7 | 1 | 3 | 4 | 9 | + last 陣列 | LIS 長度 | 1 | 2 | 3 | 4 |概念| |:--------------:|:---:|:---:|:---:|:---:|:---| |最後一個元素|2| | | |s[0]=2 | | |2|8<br />(2 8)| | |s[1]=8 | | |2|6<br />(2 6)| | |s[2]=6，26 取代 28| | |2|6|7<br />(2 6 7)| |s[3]=7，7可加在6後，變成長度3| | |1|6|7| |s[4]=1| | |1|3<br />(1 3)|7| |s[5]=3，3可以取代6(13->26)，<br />**找到第一個>=3的元素並取代**| | |1|3|4<br />(1 3 4)| |s[6]=4，134 取代 267，<br />找到第一個>=4的元素並取代| | |1|3|4|9<br />(1 3 4 9)|s[7]=9，找不到直接加在最後面| + last 陣列的元素是單調遞增的，要找 s[i] 可以接在誰後面時，不用循序找，可以用二分搜加速。 + [[Python] 陣列二分演算法（Array bisection algorithm）bisect 筆記](https://clay-atlas.com/blog/2022/11/26/python-bisect-array-bisection-algorithm/) ```python= import bisect a=[1, 2, 5, 5, 6, 8] print(bisect.bisect_left(a, 3)) # 2 print(bisect.bisect_right(a, 3)) # 2 print(bisect.bisect_left(a, 5)) # 2 print(bisect.bisect_right(a, 5)) # 4 print(bisect.bisect_left(a, 9)) # 6 print(bisect.bisect_right(a, 9)) # 6 bisect.insort_left(a, 4) print(*a) # 1 2 4 5 5 6 8 ``` ```python= # O(nlog(n)) import bisect n=int(input()) s=[*map(int, input().split())] # 戰力值 last=[] for e in s: ~ # 在目前 last 陣列中找 >=e 的最小值，以 e 覆蓋此元素可能產生更長的 LIS if ~ # 如果找不到 ~ # 將 e 放在 last 最後 else: # 如果找的到 ~ # 取代這個值 print(len(last)) ``` + [如果要印出 LIS 的元素](https://yuihuang.com/dp-lis/) :::info AL_EX_6_7：[f608: 4. 飛黃騰達](https://zerojudge.tw/ShowProblem?problemid=f608) + [最長嚴格遞增子序列(LIS)的變形](https://www.youtube.com/watch?v=vLS3fCeGpeI) - 將所有點依 x 座標排序後，每個點的 y 座標可看成一個整數序列。對任意 i<j 若y[i]<=y[j]，表示 i 點可以走到 j 點，所以每一種走法就是一個非遞減子序列，本題就是要找一個最長的非遞減子序列(Longest Non-Decreasing Subsequence)。 - 範例 | ![](https://i.imgur.com/bmnj6RK.png =235x)<br> $\bf\fbox 1$ 5 $\bf\fbox 1$ $\bf\fbox 3$ 2 $\bf\fbox 4$ $\bf\fbox 4$ 6 3 $\bf\fbox 5$ 4<br> $\bf\fbox 1$ 5 $\bf\fbox 1$ 3 $\bf\fbox 2$ $\bf\fbox 4$ $\bf\fbox 4$ $\bf\fbox 6$ 3 5 4<br>$\vdots$| 11<br>1 1<br>1 5<br>2 1<br>2 3<br>3 2<br>3 4<br>4 4<br>4 6<br>5 3<br>5 5<br>6 4<br>Ans：6| | :--------: | :-------- | - 飛黃可以向上或『向右』移動，y 座標相等可以加到非遞減子序列。 LIS 在 last 陣列中尋找第一個『>=』(bisect_left) 的元素，這裏要改為尋找第一個 『>』(bisect_right) 的元素(數值相同要保留，不要覆蓋掉)。 ![](https://i.imgur.com/kRdyVp9.png =150x) + 排序時 x 相等則比較 y，list 預設即會這樣比較。 ::: ```python= import bisect n=int(input()) a=[[int(x) for x in input().split()] for _ in range(n)] a.sort() last=[] # 存 y 座標的 lis for ~ # 對每個座標 ~ # 在目前 lis 陣列中找 > 此點 y 座標的最小值，覆蓋此元素可能產生更長的 LIS if ~ # 如果找不到 ~ # 將此點 y 座標從尾端加入 lis else: ~ # 如果找的到，取代這個值 print(len(last)) ``` :::warning [d052: 11456 - Trainsorting](https://zerojudge.tw/ShowProblem?problemid=d052) + [由於火車可以選擇接在前方或後方，所以將原本的數列前接上顛倒的數列](https://yuihuang.com/zj-d052/)，再找 LIS。 + s=s[::-1]+s ::: ### 4. 2D1D #### [切棍子的最小成本](https://www.freesion.com/article/49081335466/) + 狀態定義 - cost(i,j) 表示第 i 點到第 j 點這段的最低切割成本。 - 以座標 0 與 L 當作第 0 與第 n+1 點，即求 cost(0,n+1) + 狀態轉移方程 - $$ cost(i,\ j)=\begin{cases} 0 \qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\quad if \ j=i+1 \\[2ex] \min\limits_{i<k<j}\{\ cost(i,\ k) + cost(k,\ j) \ \} + p[j]-p[i] \quad otherwise \qquad\qquad\qquad\qquad\qquad \end{cases} $$ + 範例 ![](https://i.imgur.com/TYhEJsX.jpg =500x) :::info AL_EX_6_8：[HWSH Judge a114: P_6_17 切棍子](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a114) [TCFSH CIRC Judge d079: P-6-17. 切棍子](https://judge.tcirc.tw/problem/d079) ::: ```python= n,L=map(int, input().split()) p=[0]+[*map(int, input().split())]+[L] cost=[[0]*205 for _ in range(205)] # 點相鄰 cost 為 0 for len in range(2,n+2): # 多用一個變數 len=j-i，代表點i~點j之間的長度，比較好思考。 for ~ # 計算 cost(i, j) j=i+len minCost=1e9 for ~ # 對 i~j 中間每個切割點 k 計算 cost ~ # 求 i~k cost + k~j cost 的最小值 ~ # 得到最小值後，總成本還要加上點i~點j之間的距離。 print(cost[0][n+1]) ``` :::warning [HWSH Judge a217: Q_6_18 矩陣乘法鏈](https://judge.hwsh.tc.edu.tw/ShowProblem?problemid=a217) [TCFSH CIRC Judge d086: Q-6-18. 矩陣乘法鏈](https://judge.tcirc.tw/problem/d086) + [矩陣相乘次序(Matrix Chain Multiplication)](https://web.ntnu.edu.tw/~algo/DynamicProgramming.html#4) + dp(i, j)為從第 i 個矩陣乘到第 j 個矩陣，最少的相乘次數。 + r[i]為第 i 個矩陣的列數。 + c[i]為第 i 個矩陣的欄數。 + $$ dp(i, j) = \min\limits_{i\le k<j} \{ dp(i, k) + dp(k+1, j) + r[i]*c[k]*c[j] \} \qquad\qquad\qquad\qquad\qquad\qquad\qquad$$ ::: :::warning [m934. 4. 合併成本](https://zerojudge.tw/ShowProblem?problemid=m934) + $$ dp(i, j) = \min\limits_{i\le k<j} \{ dp(i, k) + dp(k+1, j) + |sum(i,k)-sum(k+1,j)| \} \qquad\qquad\qquad\qquad\qquad\qquad\qquad$$ + [解題參考](https://hackmd.io/@bangyewu/SkKxG8Oua?fbclid=IwAR09nvTMNtD9ilT1bdtXLjSgTgr-tGe9OxEoodT9bF0xlSYmcgmZmB4etQA) ::: :::warning [f817: TOI_y21m4_a03枯枝](https://zerojudge.tw/ShowProblem?problemid=f817) + dp[i][j] = dp[i][i] + min( max(dp[i+1][k], dp[k+1][j])，i+1 ≦ k < j) + [解題參考](https://www.youtube.com/watch?v=lpPhi25Md1c) :::