九十六学年高雄市程式的设计竞赛文档的资料.docVIP

九十六學年高雄市程式設計競賽高職組試題中華民國九十六年十月二十日第一題：集合運算（14%）數學集合各種運算以下列符號表示：x屬於(belong to)A記做 x in AA與B聯集(union)記做 A + BA與B交集(intersection)記做 A * BA與B差集(difference)記做 A – BA包含(contain)B記做 A = B製作一個「集合」類別(set class)，使其能進行聯集、交集、差集、包含等運算。輸入格式:第一行n表示有n個集合，接著有n行分別為集合A、B、C…的內容。n=0 時表示輸入結束。輸出格式:印出上述運算結果。範例輸入:2AbcdefCfehi234abcef34範例輸出:Test Case 1:A: {abcdef}B: {cefhi}A+B: {abcdefhi}A*B: {cef}A–B: {abd}B–A: {hi}A does not contain BB does not contain ATest Case 2:A: {34abcef}B: {34}A+B: {34abcef}A*B: {34}A–B: {abcef}B–A: {}A contains BB does not contain A第二題：排列最大值（16%）給定N個正整數。試著利用連接字串的方式去排列這N個正整數，使其值最大。輸入範例:5 123 124 56 90 95 28 285 287 2851 28592 25 25233 89 898 899輸出範例:99056124123 287285928528512825252389989898第三題：設計一含小數點的十進位轉二進位的程式（18%）設計一個可轉換含小數點八位數的十進位轉二進位程式小數點可在此一八位數中的任何一位，如：1234.5678或1.2345678請將此一含小數之十進位轉成二進位輸入範例:10.5234.125輸出範例:1010.111101010.001第四題：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**15 *****7 1**010*10 **01**01**0範例輸出:Case 1: 2Case 2: 16Case 3: 4Case 4: 9第五題:手機散布訊息（18%）你有一些消息要透過手機告訴每個朋友，但你必須以最便宜的方法透過電話散佈這些消息。你會打給幾個你的朋友，他們會打給一些他們的朋友，如此直到所有人都知道這些消息。每個人用的手機費率都不一樣，而且你知道對所有A和B，A打給B的價錢。並不是所有你的朋友都喜歡彼此，而且有些人永遠都不要打給他不喜歡的人。你的工作是找出最便宜的方法，讓所有的人都知道這些消息。輸入格式:輸入第一行是測資數量 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!。範例輸入:4210 1 10211 0 10440 1 100 2 101 3 202 3 30440 1 101 2 202 0 302 3 100範例輸出:Case #1: 10Case #2: Possums!Case #3: 40Case #4: 130第六題：樣板比對（19%）樣板比對(Template matching)是一種簡單演算法可以在二元影像(每個影像點之值為0或1)中尋找出特定的特徵。輸入矩陣T(x,y)(n×n大小)的矩陣，在影像I中所有可能的位置進行比對，找出T(x,y)的子影像(subimage)之左上角座標位置(即以左上角座標代表一個子影像)。若有多個子影像，則輸出所有子影像(subimage)之左上角座標位置。影像。例如T(x,y)