九十六学年高雄市程式设计竞赛.docVIP

九十六學年高雄市程式設計競賽 高職組試題 中華民國九十六年十月二十日 第一題：集合運算（14%） 數學集合各種運算以下列符號表示： x屬於(belong to)A記做 x in A A與B聯集(union)記做 A + B A與B交集(intersection)記做 A * B A與B差集(difference)記做 A – B A包含(contain)B記做 A = B 製作一個「集合」類別(set class)，使其能進行聯集、交集、差集、包含等運算。: 第一行表示，…的內容。n=0 時表示輸入結束。: 印出上述運算結果。 範例輸入: 2 Abcdef Cfehi 2 34abcef 34 範例輸出: Test Case 1: A: {abcdef} B: {cefhi} A+B: {abcdefhi} A*B: {cef} A–B: {abd} B–A: {hi} A does not contain B B does not contain A Test Case 2: A: {34abcef} B: {34} A+B: {34abcef} A*B: {34} A–B: {abcef} B–A: {} A contains B B does not contain A 第二題：排列最大值（16%） 給定N個正整數。試著利用連接字串的方式去排列這N個正整數，使其值最大。 : 5 123 124 56 90 9 5 28 285 287 2851 2859 2 25 2523 3 89 898 899 輸出範例: 99056124123 2872859285285128 252523第三題：設計一含小數點的十進位轉二進位的程式（18%） 設計一個可轉換含小數點八位數的十進位轉二進位程式 小數點可在此一八位數中的任何一位，如：1234.5678或1.2345678 請將此一含小數之十進位轉成二進位 輸入範例: 10.5 234.125 輸出範例: 1010.1001 第四題：triple-free（15%） 二元字串是 0 和 1 組成的。給你一個二元字串 ，如果沒有二元字串 S，使得 SSS(三個 S 字串連起來)是 T 的子字串，那 T 就是 triple-free。一個二元字串包含 0, 1 還有星號(*)，星號可以被換成 1 或 0。例如，0**1 可以換成 0001, 0011, 0101, 0111，但是不能換成 1001 或 0000。給你一個二元字串P，它可以換成多少種 triple-free 的字串？ : 每一行表示一組測資，包含二元字串的長度 n(0 n 31)，還有二元字串P。n=0 時表示輸入結束。: 對每組測資，輸出 case number 和答案。 : 4 0**1 5 ***** 7 1**010* 10 **01**01** 0 範例輸出: Case 1: 2 Case 2: 16 Case 3: 4 Case 4: 9 第五題:手機散布訊息（18%） 你有一些消息要告訴每個，必須以最便宜的方法透過電話散佈這些消息。會幾個的朋友，們會一些們的朋友，如此直到所有人都知道這些消息。每個用的手機都不一樣，而且知道對所有A和B，AB的價錢。並不是所有的朋友都喜歡彼此，而且有些人永遠都不要不喜歡的人。的工作是找出最便宜的方法，讓所有的人都知道這些消息。: 輸入第一行是測資數量 N，接著有 N 組測資。每一組測資的第一行包含 n (0=n=1000) 和 m (0=m=40000)。的編號從 0 到 n-1，是 0。接下來 m 行每行都包含三個數字 u,v 和 w 意思是u打給朋友v的成本是 w(0=w=1000)，沒有提到的表示因為討厭對方而不可能 call。: 對每組測資，輸出一行包含Case #x:，接著是發佈消息最便宜的方法的花費。如果沒有方法，則輸出Possums!。: 4 2 1 0 1 10 2 1 1 0 10 4 4 0 1 10 0 2 10 1 3 20 2 3 30 4 4 0 1 10 1 2 20 2 0 30 2 3 100 範例輸出: Case #1: 10 Case #2: Possums! Case #3: 40 Case #4: 130 第六題：樣板比對（19%） 樣板比對(Template matching)是一種簡單演算法可以在二元影像(每個影像點之值為0或1)中尋找出特定的特徵。輸入矩陣T(x,y)(n×n大小)的矩陣，在影像I中所有可能的位置進行比對，找出T(x,y)的子影像(subimage)之左上角座標位置(即以左上角座標代表一個子影像)。若有多個子影像，則輸出所有子影像(subimage)之左上角座標