主题模拟题与其他问题课件

1、主题模拟题与其他问题主题模拟题与其他问题模擬題殺人問題曆法轉換Robot撲克牌猜數字Life GameLoop Detection2模擬題殺人問題4例: A.305 Joseph有 k 個好人 (1 k) 與 k 個壞人 (k+1 2k) 排成一圈，從編號 1 開始數，每次殺第 m 個人，請問要讓所有壞人比所有好人先死的 m 最小為多少？0 k 143例: A.305 Joseph有 k 個好人 (1 k)k = 3123654m = 4123654m = 54k = 3123654m = 4123654m = 5解題技巧在讀入 k 之前，先把 k = 1 13 的答案算出來並紀錄，接下來不管

2、讀入任何 k 都直接查表印出答案即可直接模擬若 m % 2k k 則此 m 不是答案，因為第一步就殺到好人 一步一步模擬直到所有壞人殺光或殺到好人為止5解題技巧在讀入 k 之前，先把 k = 1 13 的答案例: A.602 What day is it?給予日期 (m d y) 請問此日期的 weekday8 10 2004 Tuesday閏年規則: 若年份是 4 的倍數，且不為 400 的倍數則是閏年曆法修正: 因為閏年修正的關係，所以 1752/9/02 的下一天是 1752/9/146例: A.602 What day is it?給予日期 (解題技巧直接模擬檢查給予的日期是否合法看看

3、今天的 weekday 往回推小心閏年規則與曆法修正日期7解題技巧直接模擬9例: A. 10500 Robot maps給一個 n m 的地圖，地圖上有空格與障礙物，1 n, m 10給予機器人的起始位置 (必定是空格)，每次機器人會先讀取上下左右格子的資訊，接下來移動到第一個沒走過的格子 (檢查順序是由上方開始順時針方向 )，一直到週圍都已走過或是障礙物為止輸出機器人所偵測到的地圖8例: A. 10500 Robot maps給一個 n ?xxx?xxxxxx9?xxx例: A.131 The psychic poker player手上有五張牌，桌上有五張牌，可以換一次牌(從手上丟掉任意

4、k 張，從桌上依序拿取 k 張)，請問最大可以換到什麼牌手上: 2H 2S 3H 3S 3C桌上: 2D 3D 6C 9C 10H最好的換法: 換兩張2H 2S 3H 3S 3C2H 2S 3H 3S 3C 2D 3D10例: A.131 The psychic poker pla解題技巧從換 0 張到換 5 張不換牌所有丟掉 1 張牌的可能組合 + 依序拿進 1 張所有丟掉 2 張牌的可能組合 + 依序拿進 2 張比較牌組大小時先比數字再比花色11解題技巧從換 0 張到換 5 張13例: A.296 Safebreaker猜 4 位數字遊戲，給予數行 (110) 猜數字的過程，請判斷有唯一解

5、，無解，還是不只一組解xxxx A/B: xxxx 是這回合猜的數字，A 表示數字對且位子也對的數目，B 代表數字對但是位置不對的數目12例: A.296 Safebreaker猜 4 位數字遊戲，9793 0/12384 0/26264 0/13383 1/02795 0/00218 1/0 答案: 3411139793 0/12384 0/26264 0/1338解題技巧開一個大小為 10000 的陣列，對於每一組猜測都把不可能的數字標記掉最後看剩幾組數字沒標記0組: 無解1組: 唯一解多於 1 組: 不只一組解14解題技巧開一個大小為 10000 的陣列，對於每一組猜測都把例: A.45

6、7 Linear cellular automata給 40 個細菌培養皿，每個培養皿有自己的細菌濃度 (從 0 到 3)，與濃度轉換公式每天每個培養皿會根據昨天自己的濃度、左右兩個培養皿濃度及轉換公式得到新的濃度:denday j+1i = 公式(denday ji + denday ji1 + denday ji+1)請列出所有培養皿從第 1 天到第 50 天的狀態15例: A.457 Linear cellular autom轉換公式:01 11 22 30 4153 63 72 82 90123332003202320016轉換公式:123332003202320018解題方法仔細閱讀

7、題目敘述與假設第一天第 20 個培養皿濃度是 1，其他皆為 0假設在第 1 個左邊與第 40 個右邊各有一個濃度一直為 0 的培養皿按照題目敘述與轉換公式逐日模擬並輸出17解題方法仔細閱讀題目敘述與假設19例題: W.96.1 20-30-40給予一副牌，按照順序發成三疊在發了任一張牌後，若任何一疊中，有(1)底部一張與最上面兩張 (2) 底部兩張與最上面兩張 (3) 底部連續三張加起來點數為 10、20 或 30，則把這三張牌拿起來進入手上牌疊若某疊牌拿起三張後仍符合上述條件，則一直拿到不符合條件為止若有某一疊的牌完全被拿光了，則以後不在往這疊發牌請輸出最後結果: (1) 三疊牌都清空了 (

8、2) 手上牌疊空了 (3) 進入無窮迴圈18例題: W.96.1 20-30-40給予一副牌，按照順序發進階技巧 loop detection需要偵測是否有迴圈出現方法一: 模擬比對每跑出一個新狀態，就從頭開始再跑一次看是否出現過同樣的狀態方法二: 紀錄狀態把所有出現過的狀態記錄下來比對19進階技巧 loop detection需要偵測是否有迴圈模擬比對/ 這 function 用來模擬從狀態 a 發一張牌後的情況state DispatchOneCard(state a);/ 主要用來直接模擬比對的迴圈while (not_win_lose) now_state = DispatchOneC

9、ard(last_state);step+;CheckWinLose(now_state);pre_state = init_state;for (i = 1; istep; i+)if (pre_state = now_state) return;else pre_state = DispatchOneCard(pre_state);20模擬比對/ 這 function 用來模擬從狀態 a 發一紀錄狀態可能的狀態數目在記憶體範圍內，則用列舉法列舉所有可能的狀態，標記出現過的狀態可能的狀態數目超過記憶體容量狀態可以比較大小: 用 search tree 紀錄所有出現過的狀態狀態較難比較大小:

10、使用 hash value 來加速尋找重複的狀態21紀錄狀態可能的狀態數目在記憶體範圍內，則用列舉法23Search tree一開始， search tree 是空的，第一個出現的狀態成為 root每一個 tree node 上會代表一個狀態在這個 node 的 subtree 中Left subtree: 比這個狀態小 (字典順序或編碼順序) 的狀態Right subtree: 比這個狀態大的狀態22Search tree一開始， search tree 是空例: ABCD 的組合ACBD開始沒有狀態 tree 是空的產生狀態 ACBD，加入 tree產生狀態 ABCC，加入 tree產生狀

11、態 BADA，加入 tree產生狀態 CCCB，加入 tree產生狀態 BADB，加入 tree產生狀態 ACDD，加入 treeABCCBADACCCBBADB產生狀態 ABCC，loop!ACDD23例: ABCD 的組合ACBD開始沒有狀態 tree 是Hash用一個多對一的 hash function h(x) 來把狀態 x 對應到既定範圍內的數字不同的狀態可以對應相同的數字同一個狀態必須對應同一個數字每出現一個狀態，就檢查相同 hash value 的狀態裡是否有一樣的狀態24Hash用一個多對一的 hash function h(x)例: 0123的所有組合H(s1s2s3s4)

12、= s1 + s2 + s3 + s4 0123456789101112狀態 0002, H(0002) = 20002狀態 1220, H(1220) = 51220狀態 0010, H(0010) = 10010狀態 0110, H(0110) = 2011025例: 0123的所有組合H(s1s2s3s4) = s1 +儲存相同 hash value 的狀態用 link list Sorted list: insert 較慢，但搜尋較快Unsorted list: insert 快，但搜尋要看完 list用 search tree 程式較複雜效率介於上述兩者之間建議用 hash + un

13、sorted lists26儲存相同 hash value 的狀態用 link list倒水問題: A.571 Jugs給兩個罐子及其容量 A 與 B (A , B 互質)，允許的動作是把某罐子清空或倒滿水，把某個罐子的水倒到另一個罐子裡直到一邊空了或滿了為止給予一目標 N，請問最少的動作次數才能倒出 N 來27倒水問題: A.571 Jugs給兩個罐子及其容量 A 與 解題技巧存在一組最佳解，不是 A 一直注滿 B 一直倒空，就是 B 一直注滿 A 一直倒空Hint: 一個罐子不會發生又被注滿又被倒空的情形28解題技巧30例: A = 5, B = 3, N = 4AB 注滿 A 從 A 倒

14、 B 清空 B 從 A 倒 B 注滿 A 從 A 倒 B 4 出現!29例: A = 5, B = 3, N = 4AB 注滿 A作法把 A 注滿從 A 倒 B若 B 滿，清空 B若 A 沒了，注滿 A檢查是否出現 N ，若無則重複以上步驟把 A 與 B 的角色對調並重複上述步驟，取動作次數較少的即為答案30作法把 A 注滿32貼郵票問題: A.165 Stamps給 h 與 k (h + k 9)，h 是總共可以貼的郵票張數，k 是面額種類，請幫忙決定用怎麼樣的面額，使得從 1 開始到 N 的所有數字都可以貼出來，並且 N 最大例: h = 3, k = 2，則 1 與 3 可以貼出最大的

15、N面額 = 1, 2, 可貼出 = 1, 2, 3, 4, 5, 6面額 = 1, 3, 可貼出 = 1, 2, 3, 4, 5, 6, 7, 9面額 = 1, 4, 可貼出 = 1, 2, 3, 4, 5, 6, 8, 9, 1231貼郵票問題: A.165 Stamps給 h 與 k (h 解題技巧暴法展開填表法用暴力法展開所有可能的幣值若已知面額，則可用填表法來得知 N 面額 1面額 1, 2面額 1, 2, 3面額 1, 2面額 1面額 1, 3面額 1 1 一定要2 要不要3 要不要32解題技巧暴法展開填表法面額 1面額 1, 2面額 1, 2,實作技巧在 recursive 過程中

16、使用一陣列來記錄現在能貼的數字與最小使用張數，在加入新的面額後可以很快得知新的結果面額 1,2面額 1, 2,3123456112233N最小張數123456111222N最小張數7893333實作技巧在 recursive 過程中使用一陣列來記錄現在能如何避免無窮的 recursive?已經使用 h 種面額時不再往下長 在決定面額 m 時，若先前決定的最大 N 為 m1，則面額 m 非使用不可例: 若在決定面額 6 時，之前所用的面額只能湊出 1, 2, 3, 4, 5，則面額 6 非用不可，不然往後因為面額都比 6 大，不可能湊出 6tree 的高度 k2h34如何避免無窮的 recurs

17、ive?已經使用 h 種面額時不四則運算式一般我們使用的四則運算式稱之為 infix 表示法，因為運算元是在運算子中間5 + 8 3 ( 4 / 2 ) + 9infix 比較不適合用電腦做運算，因為有運算順序 (先乘除後加減) 與括號，使得我們要記錄之前的運算元與運算子35四則運算式一般我們使用的四則運算式稱之為 infix 表示法Posfix 表示法運算元在運算子之後，沒有運算順序與括號的問題，較適合電腦運算，只需一 stack 來記錄運算子規則: 看到運算元則對之前兩個運算子做運算，結果會成為新的運算子infix:A + B C ( D / E ) + 9posfix: ABC+DE/9

18、+36Posfix 表示法運算元在運算子之後，沒有運算順序與括號的T2 = A + T1push(T2)T1 = B Cpush(T1)push(C)push(B)實作用一 stack 存放，由左至右 scan 運算式運算子: push運算元: pop 兩個運算子運算，push結果 例: ABC+DE/push(A)ABCT1 = B CT2 = A + T137T2 = A + T1T1 = B Cpush(C)pupop(), pop(+)push()輸出 Cpush()輸出 Bpush(+)Infix 轉換 posfix (無括號)用一 stack 存放運算元，由左至右 scan運算子:

19、 直接輸出運算元: 若運算順序小於等於 stack 最上面的運算元，則 pop 並輸出到大於為止，然後就 push 此運算元infix: A+BCD/E輸出 APosfix:A+BC+DE/38pop(), pop(+)輸出 Cpush()輸出 BpInfix 轉換 posfix (有括號)一樣由左至右 scan遇到左括號，push遇到右括號，pop 直到左括號為止 (括號不用輸出)，也不用 push 右括號其餘同上一頁，在 pop 過程中遇到左括號則停止 popInfix: A ( B/C + D)Posfix: ABCD/+(/+39Infix 轉換 posfix (有括號)一樣由左至右

20、sc例: H.92.3 多邊形的辨識一有 105 點的圖形，每個點按規則編號，給數個點，判斷這數個點是否構成直角三角、正方、長方、平行四邊或六角形13245678910111213141540例: H.92.3 多邊形的辨識一有 105 點的圖形，每個範例132456789101112131415161718192021222324252627286, 13, 15 直角三角形1, 2, 5, 3 正方形19, 25, 26, 20 平行四邊形11, 16, 23, 24, 18, 12 六邊形8, 12, 18 不是直角三角形41範例1324567891011121314151617181標

21、示座標按照順序幫每個點標示座標按斜列順序標示1324567891011121314150 1 2 3 4 x座標4 3 2 1 0第 i 斜列的第一點座標: (i1, 0) 第二點座標: (i 2, 1) 第三點座標: (i 3, 2) ( x 座標遞減, y 座標遞增)第 3 斜列的第一點 (4) 座標: (2, 0) 第二點 (5) 座標: (1, 1) 第三點 (6) 座標: (0, 2)42標示座標按照順序幫每個點標示座標13245678910111解題技巧因為圖形中沒有 / 方向的線段，因此任何合法的圖形必定存在一左上點(x 座標最小，y 座標最大)1324567891011121314151617181920212223242526272843解題技巧因為圖形中沒有 / 方向的線段，因此任何合法的圖形