---
# System prepended metadata

title: DS 讀書會 - 第 9 週
tags: [' tossug', hackpad-import]

---

---
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.

![](http://interactivepython.org/runestone/static/pythonds/_images/maze.png)

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)
