---
hackpadID: 4JWjIIROlhk
hackpadWorkspace: tossug
tags: hackpad-import, tossug
---
# DS 讀書會 - 第 9 週
01/20/2015
[« 回首頁](/JwdmDZwMwE3BacBGApgDngFkwYx/NAVjQxlgCZgkdo0AjNIA)
## 討論範圍
* Recursion
* Complex Recursive Problems - Programming Exercises
## 預定進度
* Sorting and Searching
* Objectives - Hashing
## 認領狀態
* The Binary Search
* [RJ Hsiao](/ep/profile/BzrOLagTOUQ)
* Hashing
* Wen00072
## 心得筆記
**Exploring a Maze**
The maze problem has roots as deep as the Greek myth about Theseus who was sent into a maze to kill the minotaur. Theseus used a ball of thread to help him find his way back out again once he had finished off the beast.
Procedure:
* 向北走（↑）
* 向南走（↓）
* 向西走（←）
* 向東走（→）
* 處理撞牆
* 避開死路
* 找到出口 / 沒有找到
* def searchFrom(maze, startRow, startColumn):
* maze.updatePosition(startRow, startColumn)
* if maze[startRow][startColumn] == OBSTACLE: return False
* if maze[startRow][startColumn] == TRIED: return False
* if maze.isExit(startRow,startColumn):
* maze.updatePosition(startRow, startColumn, PART_OF_PATH)
* return True
* maze.updatePosition(startRow, startColumn, TRIED)
* found = searchFrom(maze, startRow-1, startColumn) or \
* searchFrom(maze, startRow+1, startColumn) or \
* searchFrom(maze, startRow, startColumn-1) or \
* searchFrom(maze, startRow, startColumn+1)
* if found:
* maze.updatePosition(startRow, startColumn, PART_OF_PATH)
* else:
* maze.updatePosition(startRow, startColumn, DEAD_END)
* return found
**Dynamic Programming**
局部最佳解可以決定全局最佳解。
小偷背包容量有限，如何創造最大獲利？
Docker 架 cluster 如何充分運用每個節點？
factorial(5) 呼叫下去，中間過程都重複計算了，factorial(1) 就算了 10 次！
可以把每一次的過程都記下來，需要之前的結果，就回來查表，快速又省時。
Dynamic Programming 範例告訴我們，有些問題雖然可用 recursion，但不一定最合適。
<undefined>* 名詞解釋</undefined>
* Greedy method
* 嘗試用手上最方便的方法解決問題，直到沒有辦法再換招
<undefined>* 範例</undefined>
* 自動販賣機找零要如何最少的硬幣？
* 情況一：硬幣有1元，五元，十元
* 假設情況：自動販賣機要找24元
* 第一步，24減十直到不能減。所以有兩個10元硬幣
* 第二步，4減五直到不能減。所以有0個5元硬幣
* 第三步，4減一直到不能減。所以有四個1元硬幣
* 結論：要用２+４＝６個硬幣
* 如果中央印鈔廠發神經，發行八元硬幣。使用上面方式會是
* 第一步，24減十直到不能減。所以有兩個10元硬幣
* 第二步，4減八直到不能減。所以有0個8元硬幣
* 第三步，4減五直到不能減。所以有0個5元硬幣
* 第四步，4減一直到不能減。所以有四個1元硬幣
* 結論：要用２+４＝６個硬幣
* 呃，8 * 3 不是24嘛？怪怪的
<undefined>* **名詞解釋二**</undefined>
* Dynamic programming
* 把問題切割成小問題，再處理
* 這和recursion有什麼差別 (／‵Д′)／~ ╧╧
* Wen的觀察，**歡迎打臉**
* Recursion
* 減法策略。先把把大的問題一路切成小的問題，當問題小的不能再小，就一路處理回來。就像發條或是溜溜球。
* Dynamic programming
* 先定義最小問題
* 從最小問題開始解，後面的結果會根據前面結果做判斷
* 不懂？我也不懂。看範例比較快
<undefined>* 找零問題教材範例</undefined>
* #!/usr/bin/env python3
* def dpMakeChange(coinValueList, change, minCoins):
* for cents in range(change + 1):
* coinCount = cents
* for j in [c for c in coinValueList if c <= cents]:
* if minCoins[cents - j] + 1 < coinCount:
* coinCount = minCoins[cents - j] + 1
* minCoins[cents] = coinCount
* return minCoins[change]
* if __name__ == "__main__":
* clist = [1, 5, 8, 10]
* minCoins = [None] * 25
* dpMakeChange(clist, 24, minCoins)
* print(minCoins)
* # for 寫得很醜我知道
* for i in range(len(minCoins)):
* print(str(i) + ’: ’ + str(minCoins[i]))
輸出結果：[0, 1, 2, 3, 4, 1, 2, 3, 1, 2, 1, 2, 3, 2, 3, 2, 2, 3, 2, 3, 2, 3, 4, 3, 3]
0: 0
1: 1
2: 2
3: 3
4: 4
5: 1
6: 2
7: 3
8: 1
9: 2
10: 1
11: 2
12: 3
13: 2
14: 3
15: 2
16: 2
17: 3
18: 2
19: 3
20: 2
21: 3
22: 4
23: 3
24: 3
????
前情回顧：
* Dynamic programming
* 先定義最小問題
* 最小單位為一元
* 從最小問題開始解，後面的結果會依前面結果做判斷
* 每個金額的找零等於前面的硬幣數量加上一元硬幣。五元就是4個一元硬幣加上一個一元硬幣，找的零錢是一個五元
這個演算法trick部份，就是要查表！
* 找九元要多少硬幣？
* 9減掉單一幣值(一元、五元、八元、或十元)後剩餘金額所需硬幣數量 + 1元
* 九元從下面的3種硬幣扣掉會有三種結果，從最大幣值的開始看
* 第一次迴圈
* 9 - 8 = 1
* 找1元需要一個硬幣，所以目前找9元可以用兩個硬幣
* 下一次迴圈
* 9 - 5 = 4
* 找4元需要4個硬幣，所以目前找9元可以用五個硬幣
* 下一次迴圈
* 9 - 1 = 8
* 找8元需要1個硬幣，所以目前找9元可以用兩個硬幣
* 這3個中最小的是2，所以找9元可以用兩個硬幣
## 活動簽到
[Alexis Li](/ep/profile/qgzacbCzAmu)
[Carl Su](https://tossug.hackpad.com/ep/profile/n5euV0AaWLn)
[FourDollars](https://tossug.hackpad.com/ep/profile/tgNQRpN8EgG)
[Jonathan Hsieh](/ep/profile/v2IkzygwDuI)
[RJ Hsiao](/ep/profile/BzrOLagTOUQ)
[StarNight](/ep/profile/sDJQZaRfOhF)
[Ted Wu](/ep/profile/xo5A62wXl3B)
[violetson](/ep/profile/oJusv72f72w)
[Wen00072](/ep/profile/H12yKD7rYmT)
Sign in with Wallet
Connect another wallet