程式設 計 本書以下兩章解析商科與工科技藝競賽試題, 這些題目都非常有創意且實用, 值得高中職學生臨摹解析, 筆者在此提供解答, 期望更多人一起共襄盛舉 其次, 競賽前的注意事項如下 : 1. 記得自備 USB 鍵盤與滑鼠, 因為每一鍵盤的尺寸與觸感不一, 比賽時間分秒必爭, 當然是要自備以上工具

Transcription

1 商科技藝競賽試題解析 年試題解析 年試題解析 年試題解析 年試題解析

2 程式設 計 本書以下兩章解析商科與工科技藝競賽試題, 這些題目都非常有創意且實用, 值得高中職學生臨摹解析, 筆者在此提供解答, 期望更多人一起共襄盛舉 其次, 競賽前的注意事項如下 : 1. 記得自備 USB 鍵盤與滑鼠, 因為每一鍵盤的尺寸與觸感不一, 比賽時間分秒必爭, 當然是要自備以上工具 2. 競賽前幾天, 腦筋還是要低溫運轉, 這樣一進考場, 才能馬上加速前進 反之, 若停機太久, 則要耗費較多時間, 才能正常運轉 3. 競賽前要有至少兩次 4 小時的模擬考, 這樣才能練習專注力與持續力 4. 競賽給的隨身碟資料要先複製到硬碟, 以免不慎破壞, 尤其工科是逐題交出隨身碟檢查, 一旦回座發現問題, 要能馬上先行更正, 並要求取回重交 若未先行複製檔案, 則必須先取回 重做 再重交, 當然為時已晚 5. 存檔路徑與格式要符合競賽規定, 否則評審可能找不到檔案 6. 要能精準選題, 不要隨便作, 又隨便放棄, 結果一事無成 尤其要先拿到基本題 2~4 題, 就可拿到優勝而上台領獎 不然辛苦一年, 到頭來空手而回, 那就虧大了 年試題解析 一 最長遞增子序列 (21%) ) 考慮一個數列在刪除最少個數的情況下, 使得剩下的數字呈現遞增狀態 例如 : 有一個數列為 8,20,27,17,13,28,35,31, 若保留前三個數字, 其 餘的全部刪除, 剩下的就是一個遞增序列 ; 或者是保留第一 第三 第六 及第七, 其餘的全部刪除, 剩下的也是一個遞增序列, 但是與前一個例子 相比, 其遞增的序列較長 -2

3 商科技藝競賽試題解析 chapter 輸入說明輸入之奇數列為下一行數列中的個數, 偶數列為數列資料, 代表一組測試資料 每個數字與數字間的區隔為一個空白符號, 當奇數列為 0 時表示結束 ( 請參照輸入範例 ) 輸入範圍每個數列最少有 2 個數字, 最多不超過 100 個 每個數列中的數字皆大於 0, 小於 1000, 且不重複 輸入範例 test1.txt 輸出說明 每組測試的數列皆要輸出欲刪除的個數 ( 請參照輸出範例 ) 輸出範例 result1.txt 3 7 輸出結果 -3

4 程式設 計 演算說明 本題可依序由 C 增子序列 程式列印 n n C n n 1 C n n 2 C n n 3 以下程式先使用陣列預設數列資料 檢驗是否遞增, 當遞增時即為最長遞 Private Sub Command1_Click() Dim r, n, k, index As Integer Dim c As Variant r = 25 c = Array(0,, 17, 1, 2, 3, 4, 5, 18, 6, 19, 7, 20, 8, 9, 10, 11, 12, 13, 21, 14, 22, 23, 24, 25, 15) Dim s As String s = "" Dim inc As Boolean inc = False Dim a(30), b(30) As Integer For i = r To 1 Step -1 For j = 1 To i a(j) = c(j) b(j) = c(j) k = 1 index = 1 n = i combi a, b, k, index, r, n, s, inc If inc Then Label1.Caption = s 遞增數列 Label2.Caption = Str(r - i) 刪除個數 Exit Sub Public Sub combi(byval a, ByVal b, ByVal k, ByVal index, ByVal r, ByVal n, ByRef s, ByRef inc) If index > n Then 先假設是遞增 Dim inc1 As Boolean inc1 = True 只要找到一個遞減, 就不是遞增 For j = 1 To n - 1 If b(j) > b(j + 1) Then -4

5 商科技藝競賽試題解析 chapter inc1 = False 只要是遞增, 才蒐集當時的數列 If inc1 Then s = "" For j = 1 To n s = s + Str(b(j)) + "," 此一組合中, 只要有一遞增, 即為遞增 inc = inc Or inc1 Else For i = k To r - (n - index) b(index) = a(i) combi a, b, i + 1, index + 1, r, n, s, inc 以下是按照題意的解答, 其中 combi 副程式同上 Private Sub Command2_Click() Dim dir As String 'dir = "F:\vbprog\ch17\96\1\test1.txt" dir = App.Path + "\test1.txt" Dim out As String out = App.Path + "\result1.txt" Dim c(20) As Integer Dim a(20), b(20) As Integer Dim inc As Boolean Open dir For Input As #1 Open out For Output As #2 Input #1, r Do While r <> 0 inc = False For i = 1 To r Input #1, c(i) For i = r To 1 Step -1 For j = 1 To i a(j) = c(j) b(j) = c(j) k = 1 index = 1 n = i combi a, b, k, index, r, n, s, inc -5

6 程式設 計 If inc Then Print #2, r - i Exit For Input #1, r Loop Close #1 Close #2 二 總和檢查 (%) ) 請檢查一個數列中, 尋找任兩個數字相加後的和是否會等於輸入的檢查值 例如 : 有一個數列為 8,20,27,17,13,28,35,31, 若輸入的檢查值為 48, 會找到 20 及 28 兩個數, 相加的和為 48; 反之, 若輸入的檢查值為 50, 則會找不到配對的數字 輸入說明輸入之第 1 列為下一列數列中的個數, 第 2 列為數列資料 每個數字與數字間的區隔為一個空白符號 第 3 列及以後的資料為輸入的檢查值, 每一列有一個檢查值, 當為 0 時表示結束 ( 請參照輸入範例 ) 輸入範圍輸入的數列最少有 2 個數字, 最多不超過 100 個 每個數列中的數字皆大於 0, 小於 1000, 且不重複 輸入範例 test2.txt

7 商科技藝競賽試題解析 chapter 輸出說明每個檢查值有一個輸出結果, 若有匹配的檢查值, 則輸出為 1, 反之為 -1 ( 請參照輸出範例 ) 輸出範例 result2.txt 1-1 演算說明 1. 本題採用雙迴圈一一提取兩個不同索引的數字, 並檢查是否等於檢查值 程式列印 Private Sub Command1_Click() Dim dir As String dir = App.Path + "\test2.txt" Dim out As String out = App.Path + "\result2.txt" Open dir For Input As #1 Open out For Output As #2 Dim b(20) As Integer Dim r As Integer Input #1, a 資料個數 For i = 1 To a Input #1, b(i) Print b(i) Input #1, c Do While c <> 0 r = -1 For i = 1 To a For j = 1 To a If i <> j Then If b(i) + b(j) = c Then r = 1 Exit For -7

8 程式設 計 Print #2, r Input #1, c Loop 三 數獨 (23%) ) 數獨 sudoku 來自日文, 但概念源自 拉丁方塊, 是十八世紀瑞士數學家歐拉發明的 其遊戲規則為 : 在九個九宮格裡, 填入 1 到 9 的數字, 讓 每個數字在每個行 列及九宮格裡都只出現一次 謎題中會預先填入若 干數字, 其他宮位則留白, 玩家得依謎題中的數字分佈狀況, 邏輯推敲出 剩下的空格裡是什麼數字, 範例如下圖所示 請設計一個程式, 可以幫助 玩家提示空格中尚可填入的數字 例如 : 第 5 行第 3 列的位置尚可填入 1 這 個數字 ; 第 6 行第 7 列的位置尚可填入 7 與 8 這兩個數字 ; 而第 5 行第 5 列的 位置已有數字填入則輸出 0 輸入說明輸入的第 1 列到第 9 列為數獨資料, 每一列由九個數字所組成 數字 1 到 9 為已填入的數值,0 代表尚未填入數值的空格, 每個數字與數字間的區隔為一個空白符號 第 10 列及以後的資料為要提示位置的座標 ( 座標的定義方式為右上角為 9 1, 左下角為 1 9, 第一個數字代表行, 第二個數字代表列 ), 當為 0 0 時表示結束 ( 請參照輸入範例 ) -8

9 商科技藝競賽試題解析 chapter 輸入範例 test3.txt 輸出說明每個提示位置有一列輸出結果, 表示尚可填入的數字, 請由小到大排列 每個數字與數字間的區隔為一個空白符號 若該位置已有填入數字, 或找不到提示的數字, 則輸出 0( 請參照輸出範例 ) 輸出範例 result3.txt 演算說明本例先修改為線上提示的輸出入介面, 當使用者用滑鼠指向某一空白位置時, 即出現可用提示數字, 如下圖 : 1. 滑鼠指向第 1 個位置 ( 索引從 0 開始 ), 座標 1,2, 僅可輸入 7, 如下圖左 : 2. 滑鼠指向第 10 個位置 ( 索引從 0 開始 ), 座標 2,2, 僅可輸入 1,5,7 如下圖右 : -9

10 程式設 計 程式列印 Dim a(9, 9) As Integer Private Sub Form_Load() ' 已經填寫的資料 Dim b(9) As String b(1) = " " b(2) = " " b(3) = " " b(4) = " " b(5) = " " b(6) = " " b(7) = " " b(8) = " " b(9) = " " For i = 1 To 9 For j = 1 To 9 a(i, j) = Mid(b(i), j, 1) ' 動態物件 For i = 1 To 80 Load txt(i) wid = txt(0).width * (i Mod 9) hig = txt(0).height * (i \ 9) txt(i).move txt(0).left + wid, txt(0).top + hig txt(i).text = IIf(a(i \ 9 + 1, i Mod 9 + 1) = 0, "", a(i \ 9 + 1, i Mod 9 + 1)) txt(i).visible = True -10

11 商科技藝競賽試題解析 chapter ' 當資料改變時, 將資料亦寫入陣列 Private Sub txt_change(index As Integer) c = Index c1 = c \ c2 = c Mod a(c1, c2) = Val(txt(c).Text) Private Sub txt_mousemove(index As Integer, Button As Integer, Shift As Integer, X As Single, Y As Single) Dim d(9) As Integer c = Index '0 到 80 共 81 個 c1 = c \ ' 列 c2 = c Mod ' 行 Form1.Caption = Str(Index) + " " + Str(c1) + "," + Str(c2) 'f(1, 1) = 0: f(1, 2) = 1: f(1, 3) = 2: f(1, 4) = 9: f(1, 5) = 10: f(1, 6) = 11: f(1, 7) = 18: f(1, 8) = 19: f(1, 9) = 20 'f(2, 1) = 3: f(2, 2) = 4: f(2, 3) = 5: f(2, 4) = 12: f(2, 5) = 13: f(2, 6) = 14: f(2, 7) = 21: f(2, 8) = 22: f(2, 9) = 23 '3*3 正方形 9 個區塊的編號 Dim e(9) As String Dim f(9, 9) As Byte e(1) = " " e(2) = " " e(3) = " " e(4) = " " e(5) = " " e(6) = " " e(7) = " " e(8) = " " e(9) = " " ' 將以上資料讀入陣列 For i = 1 To 9 For j = 1 To 9 f(i, j) = Val(Mid(e(i), 2 * (j - 1) + 1, 2)) If a(c1, c2) = 0 Then ' 資料為零的才計算 For i = 1 To 9 d(i) = i ' 逐一刪除每一列已經出現的數字 For i = 1 To 9 d(a(i, c2)) = 0 ' 逐一刪除每一行已經出現的數字 For j = 1 To 9 d(a(c1, j)) = 0-11

12 程式設 計 j ' 刪除 9 個 3*3 正方形小區塊已經出現的數字 Select Case c Case 0, 1, 2, 9, 10, 11, 18, 19, 20 c3 = 1 ' 左上角第一區 Case 3, 4, 5, 12, 13, 14, 21, 22, 23 c3 = 2 ' 上面中間 Case 6, 7, 8, 15,, 17, 24, 25, 26 c3 = 3 ' 右上角 Case 27, 28, 29, 36, 37, 38, 45, 46, 47 c3 = 4 Case 30, 31, 32, 39, 40, 41, 48, 49, 50 c3 = 5 Case 33, 34, 35, 42, 43, 44, 51, 52, 53 c3 = 6 Case 54, 55, 56, 63, 64, 65, 72, 73, 74 c3 = 7 Case 57, 58, 59, 66, 67, 68, 75, 76, 77 c3 = 8 Case 60, 61, 62, 69, 70, 71, 78, 79, 80 c3 = 9 End Select For i = 1 To 9 c4 = f(c3, i) ' 取得 0 到 80 的編號 c5 = c4 \ ' 取得二維列編號 c6 = c4 Mod ' 取得二維行編號 d(a(c5, c6)) = 0 ' 刪除數字 ' 將不為 0 的集合起來 t = "" For i = 1 To 9 If d(i) <> 0 Then t = t + Str(d(i)) + "," Else ' 資料不為 0 的直接顯示 0 t = "0" txt(index).tooltiptext = t 自我練習 1. 同上題, 請自行加入輸入錯誤時, 出現錯誤訊息 2. 改為使用讀檔的輸入方式, 輸出亦輸出於檔案 -12

13 商科技藝競賽試題解析 chapter 四 借盤子 (13%) ) 張三把所持有的 1000 個盤子分別裝在 10 個箱子裡, 每個箱子分別裝進 及 489 個盤子 張三將這些箱子依序 標上 1~10 的號碼 有天, 李四想找張三借 N 個盤子, 張三知道每個箱子的 編號與箱子內所放盤子的個數, 但如何設計一個程式, 在不拆開箱子重 新組合盤子的情況下, 告訴張三應拿出哪些箱子給李四, 才能得到李四 要借的盤子數目呢? 輸入說明每列中的數字代表要借的盤子數, 當為 0 時表示結束 ( 請參照輸入範例 ) 輸入範圍每列中的數字皆大於 0, 小於等於 1000 輸入範例 test4.txt 輸出說明每個數字代表箱子的編號, 每個數字與數字間的區隔為一個空白符號, 請由大到小排列 ( 請參照輸出範例 ) 輸出範例 result4.txt

14 程式設 計 演算說明 1. 將 489,256,128,64,32,,8,4,2, 放入陣列, 並一一檢驗是否可減去此值 程式列印 Private Sub Command1_Click() Dim dir As String dir = App.Path + "\test4.txt" Dim out As String out = App.Path + "\result4.txt" Dim d(10) As Integer d(1) = 1: d(2) = 2: d(3) = 4: d(4) = 8: d(5) = d(6) = 32: d(7) = 64: d(8) = 128: d(9) = 256: d(10) = 489 Open dir For Input As #1 Open out For Output As #2 Input #1, r Do While r <> 0 For i = 10 To 1 Step -1 If r >= d(i) Then Print #2, i; r = r - d(i) Print #2, Chr(10) + Chr(13) ' 跳列 Input #1, r Loop Close #1 Close #2 五 尋找第 K 大的位置 (12%) ) 請設計一個程式, 能在一個數列中, 找出此數列第 K 大數字的位置 例如, 有一個數列為 8,20,27,17,13,28,35,31, 第三大的數字為 28, 此數字 的位置在串列中的第 6 個位置 ; 第 5 大的數字為 20, 此數字的位置在串列 中的第 2 個位置 -14

15 商科技藝競賽試題解析 chapter 輸入說明輸入之第 1 列為下一列數列中的個數 第 2 列為數列資料 每個數字與數字間的區隔為一個空白符號 第 3 列及以後的資料為要尋找第 K 大數字的 K 值, 當為 0 時表示結束 ( 請參照輸入範例 ) 輸入範圍輸入的數列最少為 2 個, 最多不超過 100 個 每個數列中的數字皆大於 0, 小於 1000, 且不重複 輸入範例 test5.txt 輸出說明輸入的每個 K 值皆有一個位置的輸出結果, 若超過數列的個數則輸出 -1 ( 請參照輸出範例 ) 輸出範例 result5.txt 程式列印 Private Sub Command1_Click() Dim dir As String dir = App.Path + "\test5.txt" -15

16 程式設 計 Dim out As String out = App.Path + "\result5.txt" Dim d(20) As Integer Dim c(20) As Integer Open dir For Input As #1 Open out For Output As #2 Input #1, n For i = 1 To n Input #1, d(i) ' 位置 For i = 1 To n c(i) = i ' 泡沫排序, 由大而小 For i = 1 To n - 1 For j = 1 To n - i If d(j) < d(j + 1) Then t = d(j): d(j) = d(j + 1): d(j + 1) = t t = c(j): c(j) = c(j + 1): c(j + 1) = t ' 位置 Input #1, a Do While a <> 0 If a > n Then Print #2, -1; Else Print #2, c(a) Input #1, a Loop Close #1 Close #2 六 關係運算子 (7%) ) 請設計一個程式, 能判斷出兩個數值之間三種狀態的關係運算子 : (1) 第一個數字大於第二個數字 (2) 第二個數字小於第一個數字 (3) 兩個數字一樣大 -

17 商科技藝競賽試題解析 chapter 輸入說明每一列由二個數字所組成, 為一組測試資料 每個數字與數字間的區隔為一個空白符號, 當為 0 0 時表示結束 ( 請參照輸入範例 ) 輸入範例 test6.txt 輸出說明對於每組測試資料, 輸出 > < =, 代表該二數字的關係 ( 請參照輸出範例 ) 輸出範例 result6.txt < > = 程式列印 Private Sub Command1_Click() Dim dir As String dir = App.Path + "\test6.txt" Dim out As String out = App.Path + "\result6.txt" Open dir For Input As #1 Open out For Output As #2 Input #1, a, b Dim r As String Do While (a <> 0 And b <> 0) If a > b Then r = ">" Else If a = b Then r = "=" -17

18 程式設 計 Else r = "<" Print #2, r Input #1, a, b Loop Close #1 Close #2 七 密碼解密 (8%) ) 在密碼學裡面有一種很簡單的加密方式, 就是把原始資料的每個字元通通加上某一個整數 K 而得到密碼的字元 ( 原始資料及密碼字元一定都在 ASCII 碼中可列印的範圍內 ) 例如 : 若 K=2, 那麼 apple 經過加密後就變 成 crrng 了 ; 解密則是反過來做 輸入說明第 1 列為加密的 K 值, 第 2 列為要解密的列數, 第 3 列及以後就是需要解密的字串 ( 請參照輸入範例 ) 輸入範例 test7.txt 7 3 1JKJ'pz'{ol'{yhklthyr'vm'{ol'Jvu{yvs'Kh{h'Jvywvyh{pvu5 1PIT'pz'h'{yhklthyr'vm'{ol Pu{lyuh{pvuhs' I zpulzz'thjopul'jvywvyh{pvu5 1KLJ'pz'{ol'{yhklthyr'vm'{ol'Kpnp{hs'Lx pwtlu{'jvywvyh{pvu5 輸出說明 對每一測試資料, 請輸出解密後的原始資料 ( 請參照輸出範例 ) -18

19 商科技藝競賽試題解析 chapter 輸出範例 result7.txt *CDC is the trademark of the Control Data Corporation. *IBM is a trademark of the International Business Machine Corporation. *DEC is the trademark of the Digital Equipment Corporation. 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + \test7.txt Dim out As String out = App.Path + \result7.txt Open dir For Input As #1 Open out For Output As #2 Dim data() As String Dim str As String Dim encascii As Integer Input #1, k 加密的 k 值 Input #1, n ' 列數 ReDim data(n) As String Do While Not EOF(1) i = i + 1 Line Input #1, str data(i) = str Loop For i = 1 To UBound(data) str = data(i) destr = "" For j = 1 To Len(str) destr = destr & Chr(Asc((Mid(str, j, 1))) - k) Print #2, destr i Close #1 Close #2 End -19

20 程式設 計 年試題解析 一 等差數列或等比數列 (10%) ) 在數列中有等差數列及等比數列, 若已知數列的前四項, 請判斷出此數列是等差或是等比數列, 並求出公差或公比 輸入說明第 1 行是數列的數目 t(0 t 10) 以下每行均包含四個以空白隔開的整數, 表示數列的前四項 數列的前四項均為不大於 的自然數, 等比數列的比值也是自然數 輸出說明對輸入的每個數列, 輸出兩個欄位, 欄位與欄位之間以一個空白隔開, 若是等差數列, 則第一欄輸出 A 若為等比數列, 則第一欄輸出 G; 第二欄則根據數列的判斷結果, 輸出其公差或是公比 輸入範例 輸出範例 A 2 G 2-20

21 商科技藝競賽試題解析 chapter 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\test1.txt" Dim out As String out = App.Path + "\result1.txt" Open dir For Input As #1 Open out For Output As #2 Dim data() As String Dim str As String Input #1, n ReDim data(n) As String Do While Not EOF(1) i = i + 1 Line Input #1, str data(i) = str Loop For i = 1 To UBound(data) flaga = False flagg = False ex = Split(data(i), ) 以空白分解字串 If (Val(ex(1)) - Val(ex(0))) = (Val(ex(3)) - Val(ex(2))) Then a = Val(ex(1)) - Val(ex(0)) ' 公差 flaga = True If (Val(ex(1)) / Val(ex(0))) = (Val(ex(3)) / Val(ex(2))) Then g = Val(ex(1)) / Val(ex(0)) 公比 flagg = True If flaga Then Print #2, «A «& a If flagg Then Print #2, «G «& g i Close #1 Close #2-21

22 程式設 計 二 極大值問題 (11%) ) 有一個 n 位數的正整數 A, 請問刪除其中 k 個連續或不連續的位數 (k< n), 將剩下的數字依序合併形成一個新的正整數 B,B 的最大可能值是多少? ( 請注意,A 和 B 的首位都不能是 0) 輸入說明奇數列有兩個以空白隔開的正整數 n 及 k (1 k < n ) 偶數列會有一個長度為 n 的正整數 A 輸出說明請輸出 B 的最大可能值 輸入範例 輸出範例 執行結果 -22

23 商科技藝競賽試題解析 chapter 演算說明 本題採用組合的方法 例如,5 個要刪除 2 個, 則計算 C5 取 3 的最大值即可 程式列印 Private Sub Command2_Click() Cls Dim a(5) As Integer Dim b(5) As Integer a(0) = 0: a(1) = 4: a(2) = 1: a(3) = 2: a(4) = 3: a(5) = 5 b(0) = 0: b(1) = 4: b(2) = 1: b(3) = 2: b(4) = 3: b(5) = 5 l = UBound(a) Dim r, n, k, index, max As Integer Dim s As String r = 5 n = 3 C5 取 3, 刪去 2 個 k = 1 index = 1 Call combi(a, b, k, index, r, n, s, max) Print s Print Str(max) Public Sub combi(byval a, ByVal b, ByVal k, ByVal index, ByVal r, ByVal n, ByRef s, ByRef max) If index > n Then Dim max1 As Integer For j = 1 To n s = s + Str(b(j)) max1 = 10 * max1 + b(j) s = s + Str(max1) + vbcrlf If max1 > max Then max = max1 Else For i = k To r - (n - index) b(index) = a(i) Call combi(a, b, i + 1, index + 1, r, n, s, max) -23

24 程式設 計 自我練習 1. 請改用題目規定的檔案的方式, 重做本題 三 黑盒子 (12%) ) 有一個黑盒子支援 Insert, Inquire, Clean, End 四種指令 : Insert x: 將 x 放入黑盒子中 Inquire k: 輸出黑盒子當中第 k 大的數字, 若找不到該數, 則不輸出 Clean: 更換另一組測試資料, 清空黑盒子 End: 結束程式 輸入說明 請參考範例輸入, 所有數字都為整數 一組測試資料的指令數不會超過 1000 個 輸出說明 請將每一個合法的 Inquire k 值輸出 輸入範例 Insert 4 Inquire 1 Insert 1 Inquire 2 Insert -3 Insert 3 Insert 7 Insert -99 Inquire 4 Clean Insert 3 Inquire 2 Inquire 1 END -24

25 商科技藝競賽試題解析 chapter 輸出範例 程式列印 Dim bbox(100), bi, index As Integer Private Sub Form_Activate() Dim dir As String dir = App.Path + \in.txt Dim out As String out = App.Path + \out.txt Open dir For Input As #1 Open out For Output As #2 Dim data(100) As String Dim str As String Do While Not EOF(1) Line Input #1, ss data(i) = ss i = i + 1 Loop For i = 0 To UBound(data) - 1 str = data(i) If str = END Then Exit For ex = Split(str, ) Select Case ex(0) Case Insert Call push(val(ex(1))) Case Inquire Call Sort If bbox(ex(1)) <> Then Print bbox(ex(1)) Case Clean Call clear End Select Close Sub push(v) If bi < 100 Then bi = bi + 1 bbox(bi) = v -25

26 程式設 計 Sub pop() If bi > 0 Then bbox(bi) = 0 bi = bi - 1 Sub Sort() For m = 1 To bi For n = 1 To m If bbox(m) > bbox(n) Then t = bbox(m) bbox(m) = bbox(n) bbox(n) = t n m Sub clear() For m = 1 To bi bbox(m) = m bi = 0 自我練習 以上僅將資料寫到表單, 請自行改寫, 並將輸出結果寫到檔案 四 排列最小值 (13%) ) 一串數字內有 n 個正整數 試著利用連接字串的方式去排列這 n 個正整數, 使其值最小 輸入說明 每組輸入包含一串數字, 內有 n 個正整數, 數字與數字間以一個空白隔開 -26

27 商科技藝競賽試題解析 chapter 輸出說明 每組輸出排列後的最小正整數 輸入範例 輸出範例 執行結果 演算說明本題採用排列的暴力法, 將所有排列一一檢驗, 並求其最小值, 排列的演算法請看本書 7-5 節 程式列印 Private Sub Command1_Click() Dim a(10) As String n = 3 k = 1 a(1) = 1 : a(2) = 36 : a(3) = 3647 min = # perm a, k, n, min Print min Private Sub Command2_Click() -27

28 程式設 計 Dim a(10) As String n = 4 k = 1 a(1) = 8 : a(2) = 79 : a(3) = 797 : a(4) = 799 min = # perm a, k, n, min Print min Public Sub perm(byval b, ByVal k, ByVal n, min) If k = n Then s = For j = 1 To n Debug.Print b(j); s = s + b(j) Debug.Print If Val(s) < min Then min = Val(s) Else For i = k To n t = b(i): b(i) = b(k): b(k) = t perm b, k + 1, n, min 五 兩直線間的關係 (14%) 在 2 維平面中兩條直線間的關係共有三種 : 1. 相交於一點 2. 重疊 ( 無限多交點 ) 3. 平行 ( 沒有交點 ) 輸入 4 個點, 分別代表兩條直線 請輸出這兩條直線間的關係 輸入說明每組輸入包含 8 個以空白隔開的數字 x 1 y 1 x 2 y 2 x 3 y 3 x 4 y 4, 分別代表 4 個點 (x 1, y 1 ) (x 2, y 2 ) (x 3, y 3 ) (x 4, y 4 ) 其中第一條直線會通過 (x 1, y 1 ) (x 2, y 2 ); 第二條直線會通過 (x 3, y 3 ) (x 4, y 4 ) -28

29 商科技藝競賽試題解析 chapter 輸出說明請輸出這兩條直線的關係, 如果是相交於一點, 請輸出 I; 如果這兩條線是重疊, 請輸出 L; 如果這兩條線是平行, 請輸出 N 輸入範例 輸出範例 N L I 演算說明 1. 將點轉為直線方程式 由已知兩點座標 A(x1,y1),B(x2,y2), 求經過此兩點的直線方程式, 稱為兩點式 其方法如下 : (y-y1)/(x-x1)=(y2-y1)/(x2-x2) 此方法是依照相似三角形等比的觀念推得 令 y2-y1=m,x2-x1=n 上式乘開 : mx-mx1= ny-ny1 重新整理 : mx-ny=mx1-ny1 對照直線標準式 ax+by=c, 得到 a=m,b=-n,c=mx1-ny1 2. 兩個直線方程式的重疊 平行與有一解, 請看本書 4-4 節 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\in.txt" -29

30 程式設 計 Dim out As String out = App.Path + "\out.txt" Open dir For Input As #1 Open out For Output As #2 Dim data(100) As String Dim str As String Do While Not EOF(1) Line Input #1, str data(x) = str x = x + 1 Loop Dim x1, y1, x2, y2 As Integer Dim m, n As Integer Dim a1, b1, c1 As Integer Dim a2, b2, c2 As Integer For i = 0 To x - 1 ex = Split(data(i), ««) 第一條直線 x1 = ex(0): y1 = ex(1): x2 = ex(2): y2 = ex(3) m = y2 - y1 n = x2 - x1 a1 = m b1 = -n c1 = m * x1 - n * y1 ' 第二條直線 x1 = ex(4): y1 = ex(5): x2 = ex(6): y2 = ex(7) m = y2 - y1 n = x2 - x1 a2 = m b2 = -n c2 = m * x1 - n * y1 Dim result As String If (a1 * b2 - a2 * b1) = 0 And (b1 * c2 - b2 * c1) = 0 Then result = L 重疊 Else If (a1 * b2 - a2 * b1) = 0 And (b1 * c2 - b2 * c1) <> 0 Then result = "N" ' 平行 Else result = "I" ' 相交於一點 Print #2, result Close -30

31 商科技藝競賽試題解析 chapter 六 因數 (11%) ) 已知兩個整數 n 和 d, 請你找出 n 這個值, 會有多少個因數可以被 d 整除 輸入說明每組輸入包含兩個以空白隔開的數字 n 及 d, 其 n ( 0 < n < ), 而 d (2 d < 1000) 輸出說明對於每組測試資料, 輸出 n 這個值, 會有多少個因數可以被 d 整除 輸入範例 輸出範例 6 4 演算法則 1. 用迴圈暴力法找出 n 的因數 2. 計算 n 的因數可以整除 d 的個數 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\in.txt" Dim out As String out = App.Path + "\out.txt" Open dir For Input As #1 Open out For Output As #2 Dim str As String Dim tot As Integer -31

32 程式設 計 Dim div As Integer Do While Not EOF(1) Line Input #1, str tot = 0 ex = Split(str, " ") For j = 1 To Val(ex(0)) div = Val(ex(0)) Mod j If div = 0 And (j Mod Val(ex(1))) = 0 Then tot = tot + 1 Print #2, tot Loop Close #1, #2 End 七 正多邊形的面積 (14%) ) 已知圓的半徑 r, 和內接正多邊形的邊數 n, 請計算出正多邊形的面積, 而圓周率設為 3.14 輸入說明每組輸入包含兩個數字 r 及 n,r (0 < r < 10000) 代表圓半徑,n (2 < n < 10000) 代表內接正多邊形的邊數 輸出說明對於每組測試資料, 輸出圓內接正多邊形的面積, 請四捨五入到整數位 輸入範例 輸出範例

33 商科技藝競賽試題解析 chapter 演算說明 1. 內接正三角, 表示可分割成 3 個三角形, 每個三角形面積如下 : s=(r*r*sinθ)/2, θ=360/3 所以其面積是 s=3*(r*r*sinθ)/2, θ=360/3 2. 內接正四邊形, 表示可分割成 4 個三角形, 每個三角形面積如下 : s=(r*r*sinθ)/2, θ=360/4 所以其面積是 s=4*(r*r*sinθ)/2, θ=360/4 3. 度度量轉為徑度量的公式如下 : θ*pi/180 程式列印 Private Sub Form_Activate() Const pi = Dim dir As String dir = App.Path + "\in.txt" Dim out As String out = App.Path + "\out.txt" Open dir For Input As #1 Open out For Output As #2 Dim r, n, a As Double Dim str As String Do While Not EOF(1) Line Input #1, str ex = Split(str, ) r = Val(ex(0)) n = Val(ex(1)) a = (1 / 2) * r ^ 2 * Math.Sin(360 / n * pi / 180) a = Int(a * n + 0.5) 四捨五入 Print #2, a Loop Close -33

34 程式設 計 八 文字繞圈圈 (15%) ) 已知有一個字串, 請找出可以將此字串填入的最小正方形, 而填入的方式是由正方形的左上角開始, 依順時針蚊香方向由外向內填入 輸入說明每組輸入包含一列字串, 字串內的字元皆由英文字母及數字所組成, 字串的長度最長不會超過 1000 個字元 輸出說明對於每組測試資料, 輸出填入最小正方形後的結果, 每組測試資料以一列空白隔開 輸入範例 ABCDE 輸出範例 0123 BCD4 A E 演算說明 本題使用類似老鼠走迷宮的方式, 以順時鐘的方式, 探索每一數字的位置 -34

35 商科技藝競賽試題解析 chapter 程式列印 Private Sub Command1_Click() Dim dir As String dir = App.Path + "\in.txt" Dim out As String out = App.Path + "\out.txt" Open dir For Input As #1 Open out For Output As #2 Dim m(3, 2) As Integer m(0, 0) = 0: m(0, 1) = 1 m(1, 0) = 1: m(1, 1) = 0 m(2, 0) = 0: m(2, 1) = -1 m(3, 0) = -1: m(3, 1) = 0 Dim b(10, 10) As Integer Dim a As String Dim l, c, dire, g1, h1, g2, h2 As Integer Do While Not EOF(1) Input #1, a Debug.Print (a) l = Len(a): Debug.Print (l) 找出正方形的邊長 For j = 1 To 10 If j * j > l Then c = j ' 正方形邊長 Exit For Debug.Print (c) For j = 1 To 10 For k = 1 To 10 b(j, k) = 0 b(1, 1) = 1 g1 = 1: h1 = 1: dire = 0 Dim found As Boolean ' 以順時針的方式, 逐一填入正方形的數字 For j = 2 To l found = False Do g2 = g1 + m(dire, 0) h2 = h1 + m(dire, 1) If g2 >= 1 And h2 >= 1 And g2-35

36 程式設 計 <= c And h2 <= c And b(g2, h2) = 0 Then ' 正式走入這一點 g1 = g2 h1 = h2 b(g1, h1) = j Debug.Print g1, h1, j found = True Else dire = (dire + 1) Mod 4 Loop Until found 輸出對應的位置 For j = 1 To c For k = 1 To c Debug.Print b(j, k); Debug.Print ' 將數字轉為對應字元 Dim bs As String For j = 1 To c bs = "" For k = 1 To c If b(j, k) = 0 Then bs = bs + " " Else bs = bs + Mid(a, b(j, k), 1) Print #2, bs ' 兩列空白 Print #2, Print #2, Loop Close #2 Close #1-36

37 商科技藝競賽試題解析 chapter 年試題解析 一 找出文章中使用的英文單字字數 (14%) ) 現在網際網路盛行, 網路使用者可以利用搜尋引擎找出特定的網路資訊 在搜尋技術中, 關鍵字搜尋是最常見的方法 建立關鍵字有很多種不 同的方法, 其中一種方法是找出使用的單字來當作關鍵字 本題就是要 請你寫一個程式, 可以在一段英文文章中, 找出使用的英文單字字數 輸入說明第 1 行是要建立關鍵字的英文文章篇數, 第 2 行開始為英文文章的內容 每篇文章之間, 以一行空白作為區隔 在建立關鍵字時, 我們簡化一些文法上的規則, 每個英文單字與英文單字之間, 扣除標點符號之後, 以空白作為區別, 稱之為一個單字, 大小寫視為相同 使用到的標點符號則包括下列三個 :,,., 以及 : 輸出說明對輸入的每篇文章, 分別以一行輸出使用的英文字字數 輸入範例 2 He works hard from morning till night. He is a hard worker. I once heard him speaking in English. He is a very good speaker of English. 輸出範例

38 程式設 計 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\test1.txt" Dim out As String out = App.Path + "\result1.txt" Open dir For Input As #1 Open out For Output As #2 Dim data() As String Dim i As Integer Dim str As String Dim count As Integer Input #1, n For i = 1 To n Line Input #1, str str = Replace(str, ",", " ") str = Replace(str, ".", "") str2 = Split(str, " ") All = UBound(str2) + 1 For j = 0 To UBound(str2) For k = j To UBound(str2) If j <> k Then If str2(j) = str2(k) Then All = All - 1 Print #2, All i End 二 求餘數 (13%) ) 求餘數對於會寫程式的人來說, 是個簡單的問題, 例如用 VB 來求餘數時, 可以用 mod 這個關鍵字來實作 但如果算式為 R = BP mod M 的型 態, 給 B P 及 M, 要算出餘數 R, 當 B 或 P 很大時, 那就變得不簡單了 現 在, 請你設計一個程式, 來解決上述這個不簡單的問題 -38

39 商科技藝競賽試題解析 chapter 輸入說明第 1 行的數字, 表示有幾個問題要求解, 第二行開始的每一行為一個獨立的問題 每一行包含三個數字, 分別為 B P 及 M, 例如 : 代表 B=10 P=2009 M=9 所有數字均為正整數, 其範圍屬於 [1, ] 輸出說明對輸入的每個問題分別以一行輸出餘數 R 輸入範例 輸出範例 1 3 演算說明 本題同工科技藝競賽 96 年第五題試題, 請看第 17-4 節 程式列印 Private Sub Mod2(ans, m, n) a = m Do Until (a < n) a = a - n Loop ans = a Private Sub Command2_Click() Dim a, b, c, s As Long Dim D, F As Single a = Val(Text1.Text) b = Val(Text2.Text) c = Val(Text3.Text) -39

40 程式設 計 k = Int(Sqr(c)) + 1 ReDim bb(k) As Integer By = b 轉為 2 進位 For i = 0 To k bb(i) = By Mod 2 By = By \ 2 ' 輸出 2 進位 For i = k To 0 Step -1 Print bb(i); i Print s = 1 For i = k To 0 Step -1 's = (s * s) Mod c ' 先乘再 mod 導致溢位 D = c / s ' 等號兩邊同除以 s Mod2 F, s, D ' 等於 F=s mod D s = F * s ' 再乘回來 If bb(i) = 1 Then 's = (a * s) Mod c ' 溢位 D = c / s ' 等號兩邊同除以 s Mod2 F, a, D ' 等於 F=s mod D s = F * s ' 再乘回來 Print s Label4.Caption = s 三 最大連續元素和 (15%) ) 給一串數列, 有 n 個整數, 請寫一個程式, 找出這個數列中, 連續元素相加的最大值 例如 :1, 2, -3, 4, 5 這一數列, 最大連續元素和是 4+5=9 輸入說明第 1 行的數字, 代表有幾組測試資料, 第 2 行開始的每一行即為一筆測試資料 每一筆測試資料是不定個數的整數數列, 以空格分開數字 數字的範圍為 [-10000, 10000] 間的整數 -40

41 商科技藝競賽試題解析 chapter 輸出說明 對每一筆測試資料, 以一行輸出最大連續數值和 輸入範例 輸出範例 輸出結果 演算法則 1. a= 陣列長度 2. 第一次取連續 6 個數字相加, 第二次取連續 5 個數字相加, 第三次取連續 4 個數字相加 3. 每次運算次數 陣列索引的起點與終點, 如下表 : -41

42 程式設 計 取數字的個數運算次數陣列索引的起點與終點 i (a To 1) j k(j To j+a-1 ) 6 1 1~ ~5 2~ ~4 2~5 3~ ~3 2~4 3~5 4~ ~2 2~3 3~4 4~5 5~ ~1 2~2 3~3 4~4 5~5 6~6 程式列印 Dim c As Variant Private Sub Command1_Click() c = Array(0, 10, -5, 7, 6, -1, -3) Dim a As Integer a = UBound(c) - 1 Dim max As Integer max = -999 Dim sum As Integer sum = 0 Dim s, maxs As String maxs = "" For i = a To 1 Step -1 For j = 1 To a i sum = 0-42

43 商科技藝競賽試題解析 chapter s = "" For k = j To j + i - 1 sum = sum + c(k) s = s & Str(c(k)) If sum > max Then max = sum maxs = s Label1.Caption = Str(max) Label2.Caption = maxs 四 用正方體填滿 (12%) ) 在進入社會找工作時, 通常會經過面試的過程, 來決定是否要錄用這個人 假設今天你去一家程式設計公司面試, 面試的主考官出了一道題目 請你設計一個程式來解決下面的問題 : 給你一個長方體, 請問最少要用幾個大小相同的正方體, 才能把這個長 方體填滿, 你可以使用的正方體大小不限, 長方體及正方體的邊長必須 均為正整數 輸入說明第 1 行的數字, 代表有幾個長方體 第 2 行開始的每一行, 記錄了每個長方體長寬高的邊長, 邊長的範圍為 [1, 1000] 間的整數 輸出說明對輸入的每個長方體, 分別以一行輸出所使用正方體的個數 輸入範例

44 程式設 計 輸出範例 演算說明 1. 三邊長假設是 a,b,c 2. 求輸入邊長的最大公因數, 假設是 d 3. 計算 (a*b*c)/(d*d*d) 即為所求 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\test4.txt" Dim out As String out = App.Path + "\result4.txt" Open dir For Input As #1 Open out For Output As #2 Input #1, n Dim result As Integer For i = 1 To n Line Input #1, ss ex = Split(ss, ) result = lcm(val(ex(0)), Val(ex(1))) result = lcm(result, Val(ex(2))) Print #2, result i End Function gcd(byval m As Integer, ByVal n As Integer) Dim r As Integer Do While (n <> 0) r = m Mod n m = n n = r Loop gcd = m End Function Function lcm(byval m As Integer, ByVal n As Integer) lcm = m * n / gcd(m, n) End Function -44

45 商科技藝競賽試題解析 chapter 五 計算位元為 1 的個數 (10%) ) 計算機概論是一門令人又愛又恨的科目, 它的內容可謂包羅萬象 遇到考試時, 事前需要花很多時間準備, 才能拿到高分 在學習的內容中, 有 個章節是數字系統轉換, 內容是將一個十進位的數字, 轉換成二進位的 數字 現在請你設計一個程式, 計算由十進位數字轉換的二進位數字中, 位元等於 1 的個數 輸入說明第 1 行的數字, 代表有幾個十進位的數字 第 2 行開始的每一行, 為一個十進位數字, 其範圍為 [0, ] 的整數 輸出說明對輸入的十進位數字, 以一行分別輸出轉換成二位進數字中, 位元等於 1 的個數 輸入範例 輸出範例 3 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\test5.txt" Dim out As String -45

46 程式設 計 out = App.Path + "\result5.txt" Open dir For Input As #1 Open out For Output As #2 Input #1, n For x = 1 To n Input #1, d d = Val(d) ans = 0 Do ans = ans + d Mod 2 d = d \ 2 Loop Until d = 0 Print #2, ans x End 六 測謊機 (11%) ) 小明請小華猜出他心理想的一個數字, 這個數字為 [1, 100] 間的整數 猜測的規則為 : 每一回小華猜測一個數字, 小明則回應小華猜得太高 (too high), 太低 (too low), 或是猜中 (righton), 猜中後立即結束遊戲 因為過 程中小明可能會說謊, 你必須寫一個程式, 在每次結束之後, 驗證小明他 的回應是否都正確 輸入說明輸入中含有多次遊戲的記錄 在每一次遊戲中會包含許多次的猜測及回應的過程 每一次遊戲的最後都必須猜中才能結束 在最後一組遊戲後, 由僅含有 0 的一列代表輸入結束 輸出說明針對每一次的遊戲, 程式以一行輸出小明是否有說謊 如果這次遊戲有說謊則輸出 0; 沒有說謊則輸出 1-46

47 商科技藝競賽試題解析 chapter 輸入範例 5 too high 3 too high 1 too low 2 right on 33 too low 34 too high 32 right on 0 輸出範例 1 0 演算說明此題使用二分逼近法, 每次範圍均依照使用者的答案而縮小, 當小明回答 right on 時, 只要檢查答案是否在範圍內, 即可判斷是否說謊 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\test6.txt" Dim out As String out = App.Path + "\result6.txt" Open dir For Input As #1 Open out For Output As #2 Dim max, min, n As Integer Dim m As String Do Input #1, n If n = 0 Then Exit Do -47

48 程式設 計 Line Input #1, m If m <> right on Then If m = too high Then max = n If m = too low Then min = n Else If n > min And n < max Then Print #2, 1 Else Print #2, 0 Loop End 七 圍成正方形 (17%) ) 這是個有趣的題目, 給你已知長度的 n 根棍子, 請你試著寫一個程式, 把這 n 根棍子連成一個正方形 連接的限制條件如下 : 1. 棍子只可以用端點來連接 2. 不能折斷它 3. 每一根棍子都必須使用到 輸入說明第 1 行的數字, 代表有幾個問題要求解 第 2 行開始的每一行, 為一個獨立的問題 每一行的第一個整數為棍子數目 n, 其範圍為 [4, 20] 的整數 接下來的 n 個整數, 分別代表這 n 根棍子的長度 每根棍子的長度範圍為 [1, 100] 間的整數 輸出說明對每一個問題以一行輸出, 如果所給定的棍子可以連成一個正方形, 則輸出 1 否則輸出 0-48

49 商科技藝競賽試題解析 chapter 輸入範例 輸出範例 0 1 演算說明本例採用刪除法 因為所有的棍子要能圍成正方形, 一定要完全滿足以下條件, 只要一個不滿足, 即可刪除 1. 總長度要 4 的倍數, 並計算邊長 2. 若有一根棒子的長度大於正方形邊長, 此即不可能組成正方形 3. 將所有棍子由大而小排序, 要能找到四組棍子, 且這四組的長度和都等於邊長的棍子 程式列印 Private Sub Command1_Click() Dim dir As String dir = App.Path + "\test72.txt" Dim out As String out = App.Path + "\result7.txt" Open dir For Input As #1 Open out For Output As #2 Input #1, n Print n For x = 1 To n ' 組數 Line Input #1, ss ex = Split(ss, " ") l = 0 Print UBound(ex) For j = 1 To UBound(ex) l = l + Val(ex(j)) -49

50 程式設 計 j ' 總長度要 4 的倍數 If l Mod 4 <> 0 Then Print #2, 0 GoTo aa: Avg = l / 4 ' 任一邊的長度, 大於邊長 For j = 1 To UBound(ex) - 1 If Val(ex(j)) > Avg Then Print #2, 0 GoTo aa: j Dim sum(4) As Integer 由大到小排序 For j = 1 To UBound(ex) - 1 For k = 1 To UBound(ex) - j If ex(k) < ex(k + 1) Then t = ex(k): ex(k) = ex(k + 1): ex(k + 1) = t For j = 1 To 4 sum(j) = ex(j) t = 0 找出 4 組等長的邊 For j = 1 To 4 If sum(j) = Avg Then ' 單一根就構成正方形的一邊 t = t + 1 Else ' 開始拼湊 If sum(j) < Avg Then For k = UBound(ex) To 5 Step -1 If sum(j) + Val(ex(k)) <= Avg And ex(k) <> "" Then sum(j) = sum(j) + Val(ex(k)) ex(k) = If sum(j) = Avg Then 拼湊完成 t = t + 1 Exit For -50

51 商科技藝競賽試題解析 chapter If t = 4 Then ' 有 4 組等長 Print #2, 1 Else Print #2, 0 aa: Close #2 Close #1 八 計算平均值 (8%) ) 給你一組數字, 請寫一個程式計算出這組數字的平均值, 四捨五入至小數第 2 位 輸入說明第 1 行的數字, 代表有幾個問題要求解 第 2 行開始的每一行, 為一個獨立的問題 每一行的第一個整數為這個問題所屬數字的數目 n, 其範圍為 [2, 100] 間的整數 接下來的 n 個整數, 分別代表這 n 個數字的數值, 數值範圍為 [1, 100] 間的整數 輸出說明對輸入的每個問題, 分別以一行輸出平均數, 輸出的格式請四捨五入至小數第二位 輸入範例 輸出範例

52 程式設 計 程式列印 Private Sub Form_Activate() Dim dir As String dir = App.Path + "\test8.txt" Dim out As String out = App.Path + "\result8.txt" Open dir For Input As #1 Open out For Output As #2 Dim sum As Integer Dim aa(100), k As Integer Dim outstr As String Input #1, n For x = 1 To n ' 組數 Line Input #1, ss sum = 0 ex = Split(ss, " ") For j = 1 To UBound(ex) aa(j + 1) = ex(j) sum = sum + aa(j + 1) j k = ex(0) 每組的個數 outstr = Format(sum / k, "##0.00") Print #2, outstr x End 年試題解析 99 年的題目真的很有難度, 相信命題單位也花費不少時間, 這些題目非常適合學生用心咀嚼, 才能體會程式解題的樂趣 其實筆者也要花一些時間, 有些題目也不是一下子就想出來, 而是反覆推敲 琢磨, 有時候走路 等人或睡覺都會反覆思考, 但是一旦突發奇想, 從天而降一個念頭而解決問題時, 其樂趣當然是旁人無法體會 所以在這邊還是要呼籲讀者不要急著偷瞄我的解答, 這樣不但無法體會程式設計的樂趣, 您的思緒也會被我綁死 䦛一 文章的用字統計 本試題輸入檔為一篇中文文章, 文章內容可能包括 中文 及若干 全型符號 文章中可能使用的 全型符號 包括, ;! -52

53 商科技藝競賽試題解析 chapter 及? 6 種 在中文中有若干文字, 如 臺 與 台, 在某些時候意義相同, 但在本題中, 只要是字碼不同, 選手都應視為 不同字 處理 請由程式讀 入給定的中文文章, 並做以下的統計 : 子題 1.(8%) ) 請統計文章中使用的 中文字 及其 出現次數 文章中除了 中文字, 其餘符號均不列入統計 請選手輸出 出現次數最多 的中文字及 其出現次數 若有多個中文字之統計次數均為 最多 時, 請將其全部輸 出, 其輸出之前後順序不限制 輸入說明第 1 行表示文章的行數, 第 2 行開始為文章的內容 文章不超過 20 行, 每行不超過 50 個中文字 ( 含符號 ), 而文章總字數不超過 1000 字 輸出說明若統計結果只有 1 個 最多出現次數者, 則以 1 行輸出最多出現次數的 中文字 及其 出現次數 但若有 多個 最多出現次數者, 則以多行輸出 每一行資料輸出 1 個 中文字 及其 出現次數, 輸出資料間以至少 1 個空白隔開 輸入檔案 輸入檔案 1: 檔名 :in1.txt 8 為達成永續發展的目標, 行政院規劃六年國家重點發展計畫, 由教育部規劃的永續校園推廣計畫, 為建立一個進步 安全 衛生 健康 人性化的學習環境空間為主, 並於擴大內需刺激景氣的期程內, 加速推行校園公共工程改造計畫, 藉由突破傳統校園封閉的環境與制式管理原則下, 整合社區共同意識 建立社區風貌 拓展生態旅遊等課題, 改造校園環境成為具有社區特質的公共活動空間, 結合校園綠色技術實施應用, 轉化國內相關產業技術, 進而增進綠色產業推廣效益, 落實擴大內需進而促進產業升級與提振國內景氣之功效, 從而發揮永續台灣 環境教育之積極意義與促成教育改革之目的 -53

54 程式設 計 輸入檔案 2: 檔名 :in2.txt 8 台灣地區資源短缺, 興建大型水庫使用現階段推行不易, 替代水源的之開發與再利用已成為未來資源開發的之重要途徑, 推動節約用水, 推廣再利用的中水系統, 使全國平均之人均用水量逐步降至每日使用二百五十公升以下 落實國家水資源永續經營之理念, 水利署推動雨水利用及生活雜排水回收再使用增加替代水源使用, 並委託台灣雨水利用協會針對學界及各級學校相關人員, 依各縣市所在之地理位置劃分北中南三區各辦理一場次雨水貯集使用及生活雜排水再利用講習演討會議, 將邀請國內相關領域有豐碩成果與使用經驗之專家學者擔任主講員, 對國內教育單位相關人員, 以水資源永續利用 雨水貯集利用 生活雜排水再使用及節約用水等議題進行講習與研討 輸出檔案 輸出檔案 : 檔名 :out.txt 的 7 水 17 用 17 演算說明方法一 : 1. 假設資料 a= abbcde 2. 將字串 a 的 全型符號 包括, ;! 及? 等 6 種去掉 3. 將字串 a 轉為字元 b() 陣列 4. 以雙迴圈逐一統計每一字元出現的次數, 如下表 Index b() A b b c d a C() 找出 c() 最大值 6. 第一名不只一個, 所以將重複字元刪除 本例將 b() 陣列逐一放入 d() 陣 列, 但先檢查是否該字元已經存在, 若不存在, 則將此字元放入 d() -54

55 商科技藝競賽試題解析 chapter 執行結果 程式列印 Private Sub Command1_Click() Dim b(10000) As String Dim c(10000) As Integer Dim d(10) As String Dim found As Boolean Open App.Path + "\in2.txt" For Input As #1 Input #1, n Print n s = For i = 1 To n Line Input #1, a s = s + a Print a Print s 符號既然不列入考慮, 所以刪除 s = Replace(s,,, ) s = Replace(s,, ) s = Replace(s, ;, ) s = Replace(s,, ) s = Replace(s,!, ) s = Replace(s,?, ) 'Print Len(s) For i = 1 To Len(s) b(i) = Mid(s, i, 1) For i = 1 To Len(s) For j = 1 To Len(s) If b(i) = b(j) Then c(i) = c(i)

56 程式設 計 For i = 1 To Len(s) If c(i) > Max Then Max = c(i) maxs = b(i) 第一名不只一個, 所以將重複字元刪除 本例將 b() 陣列逐一放入 d() 陣列, 但先檢查是否該字元已經存在, 若不存在, 則將此字元放入 d() d(1) = maxs: m = 1 For i = 1 To Len(s) If c(i) = Max Then found = False For j = 1 To m If b(i) = d(j) Then found = True If Not found Then m = m + 1 d(m) = b(i) For i = 1 To m Print d(i); Max Close (1) 方法二 : 1. 有些字元重複, 所以將重複字元刪除 本例將 b() 陣列逐一放入 b1() 陣列, 但先檢查是否該字元已經存在, 若已經存在, 則其字元次數加一, 若不存 在, 則將此字元放入 b1() b1(1) = b(1): c(1) = 1 n = 1 For i = 2 To Len(s) bb = b(i) For j = 1 To n found = False If bb = b1(j) Then -56

57 商科技藝競賽試題解析 chapter found = True Exit For If found Then c(j) = c(j) + 1 Else n = n + 1 b1(n) = bb c(n) = 1 找出極大值 Max = 0 For i = 1 To n If c(i) > Max Then Max = c(i) 輸出極大值的字元與次數 For i = 1 To n If c(i) = Max Then Print b1(i); ":"; c(i) Close (1) 子題 2.(8%) ) 請選手在讀入的文章中, 統計 出現次數最多 且 包含 2 個中文字 的 詞 在文章中, 假設所有 兩兩相鄰的中文字 均可視為一個 詞 本題所要統計的 詞, 只包括 2 個中文字, 其中不包含任何 全型符號 ; 我們也假設, 一個 詞 不一定只出現在同一行中, 也可 能被切斷分隔在文章的前 後 2 行 例如, 有一篇文章內容為 : 我們是學生 今天要上學 在此文章中, 所有包括 2 個字的 詞 有 : 我們 們是 是 學 學生 生 今 今天 天要 要上 上學 及 學 共 11 組 雖然有些 詞 並不具明顯意義, 如 : 們 是 是學 天要 及 要上, 但本題仍將其視為一種 詞, 並加入統計 但是 生 今 及 學 等 3 者, 因為其中包括 全型符號, 則不算是 詞, 不列入統計 請選手統計並輸出出現次 數最多 只包括 2 個中文字的 詞 -57

58 程式設 計 輸入說明第 1 行表示文章的行數, 第 2 行開始為文章的內容 文章不超過 20 行, 每行不超過 50 個中文字 ( 含符號 ), 而文章總字數不超過 1000 字 輸出說明若統計結果只有 1 個 最多出現次數者, 則以 1 行輸出 出現次數最多的 詞 及其 出現次數 但若有 多個 最多出現次數者, 則以多行輸出 每一行輸出 1 個 詞 及其 出現次數, 輸出資料間以至少 1 個空白隔開 輸入檔案 輸入檔案 1: 檔名 :in1.txt 8 為達成永續發展的目標, 行政院規劃六年國家重點發展計畫, 由教育部規劃的永續校園推廣計畫, 為建立一個進步 安全 衛生 健康 人性化的學習環境空間為主, 並於擴大內需刺激景氣的期程內, 加速推行校園公共工程改造計畫, 藉由突破傳統校園封閉的環境與制式管理原則下, 整合社區共同意識 建立社區風貌 拓展生態旅遊等課題, 改造校園環境成為具有社區特質的公共活動空間, 結合校園綠色技術實施應用, 轉化國內相關產業技術, 進而增進綠色產業推廣效益, 落實擴大內需進而促進產業升級與提振國內景氣之功效, 從而發揮永續台灣 環境教育之積極意義與促成教育改革之目的 輸入檔案 2: 檔名 :in2.txt 8 台灣地區資源短缺, 興建大型水庫使用現階段推行不易, 替代水源的之開發與再利用已成為未來資源開發的之重要途徑, 推動節約用水, 推廣再利用的中水系統, 使全國平均之人均用水量逐步降至每日使用二百五十公升以下 落實國家水資源永續經營之理念, 水利署推動雨水利用及生活雜排水回收再使用增加替代水源使用, 並委託台灣雨水利用協會針對學界及各級學校相關人員, 依各縣市所在之地理位置劃分北中南三區各辦理一場次雨水貯集使用及生活雜排水再利用講習演討會議, 將邀請國內相關領域有豐碩成果與使用經驗之專家學者擔任主講員, 對國內教育單位相關人員, 以水資源永續利用 雨水貯集利用 生活雜排水再使用及節約用水等議題進行講習與研討 輸出檔案 輸出檔案 : 檔名 :out.txt 校園 5 利用 7 使用 7-58

59 商科技藝競賽試題解析 chapter 演算說明 本題請自行發揮 䦛二 資料表示方式的應用 子題 1.(11%) ) 在圖形結構中, 有一種特別的圖形, 稱之為 樹狀圖 在一個樹狀圖中, 包含若干個 節點, 每個節點和它的 上一層節點 及 下一層 節點 各有一個 邊 相連 每個節點有 1 個 或是 沒有 上一層節 點, 同時也可能有 1 個 多個 或是 沒有 下一層節點 這些節 點中, 只有 1 個節點沒有上一層節點, 所以它是最頂層的節點, 我們稱之 為 樹根 其他 非樹根 的節點, 都有 1 個上一層節點, 我們稱這些 上一層節點 是該節點的 父親, 而自己則稱為 父親 節點的 兒 子 在樹狀圖中, 有若干節點沒有任何 兒子 節點, 我們稱之為 樹 葉 現在給定一個樹狀圖資料, 請選手輸出所有 樹葉 節點, 並輸出 從 樹根 到該樹葉, 最少要經過幾個 邊 舉例, 由圖 2-1 這個樹狀 圖來說, 節點 a 是樹根 另外, 節點 d 節點 e 和 節點 g 三 者是樹葉, 因為它們都沒有 兒子 節點 從樹根到 節點 d 至少要經 過 2 個 邊 ; 到 節點 e 至少要經過 2 個 邊 ; 到 節點 g 至少要經 過 3 個 邊 輸入說明第 1 行表示樹狀圖共有多少個節點 ( 節點總數不超過 100 個 ), 第 2 行起每行包括 1 個節點資料 每行的節點資料包括 2 個符號, 以逗號隔開 : 第 1 個符號為 節點名稱, 第 2 個符號為其 父親名稱 若是 樹根 節點, 其父親表示為 個連續減號 輸出說明輸出所有 樹葉 節點, 並輸出從 樹根 到該 樹葉 至少需經過的 邊 的個數 每行輸出 1 組 樹葉 及 至少經過的 邊 的個數 資料, 其間以空白隔開, 各 樹葉 節點輸出之順序不限 -59

60 程式設 計 a b c d e f g 圖 2-1 一個樹狀圖 輸入檔案 輸入檔案 1: 檔名 :in1.txt 11 A, --- B, A C, A D, B E, B F, C G, E H, G I, G J, I K, I 輸入檔案 2: 檔名 :in2.txt 12 A, --- B, A C, A D, A E, B F, B G, C H, C I, D J, D K, E L, E -60

61 商科技藝競賽試題解析 chapter 輸出檔案 輸出檔案 : 檔名 :out.txt D 2 H 4 J 5 K 5 F 2 K 3 L 3 F 2 G 2 H 2 I 2 J 2 演算說明 1. 以二維 a(,) 儲存所有樹葉 樹根 2. 逐一判斷每一樹葉是否也為別人的樹根, 若也為別人的樹根, 則此點不是純樹葉 若僅為純樹葉, 則逐一向上探索其樹根, 直到其樹根為 A 為止 程式列印 Private Sub Command1_Click() Dim a(20, 2) As String Open App.Path + "\in2.txt" For Input As #1 Input #1, n ' 節點個數 For i = 1 To n For j = 1 To 2 Input #1, a(i, j) For i = 1 To n For j = 1 To 2 Print a(i, j); Print For i = 2 To n b = a(i, 1) -61

62 程式設 計 判斷此節點是否為父節點 found = False For j = 2 To n If b = a(j, 2) Then found = True Exit For If Not found Then ' 樹葉節點 Print b; num = 1 c = a(i, 2) ' 父節點 For j = i - 1 To 1 Step -1 c1 = a(j, 1) If c1 = "A" Then ' sucess Print num Exit For Else If c1 = c Then ' 找到父節點 c = a(j, 2) ' 向上攀升 num = num + 1 Close (1) 子題 2.(11%) ) 在一張地圖上標示有 8 個城市, 分別稱為 城市 1 到 城市 8 假設地圖上存在若干單行道, 這些單行道直接連接 1 個起點城市及 1 個終點城 市 我們以 二維陣列 表示地圖上的城市及單行道的關係 : 我們設定一 個二維陣列, 假設陣列名稱為 a, 而 a(i,j) 表示陣列中的元素, 其中 i 和 j 的值 介於 1 和 8 之間 當 a(i,j)=1 時, 表示存在一條直接從 城市 i 到 城市 j 的單行道 ; 若 a(i,j)=0, 表示不存在此單行道 問題 : 在一個給定的陣列 資料中, 判斷是否存在 正好經過 3 條單行道 的道路, 該道路從特定的 起點城市 開始, 並且在特定的 終點城市 結束 註 1 同一條單行道可以在求解的 3 條單行道 中重複使用 註 2 若選手找出的道路只使用 1 條或 2 條單行道, 都 不能算 存在此 道路 在本題中, 必須是 正好使用 3 條單行道 才能算是存在此道路 註 3 為了說明方便, 題目中假設陣列名稱為 a, 但選手撰寫程式時不限 定陣列之命名 -62

63 商科技藝競賽試題解析 chapter 輸入說明第 1~8 行表示城市陣列的元素, 每一行分為 8 個元素, 以 逗號 區隔 第 i 行的第 j 個元素, 表示 a(i,j) 的值 例如 : 第 1 行的第 1 個元素, 表示 a(1,1) 的值 ; 第 1 行的第 2 個元素, 表示 a(1,2) 的值 ; 第 2 行的第 1 個元素, 表示 a(2,1) 的值, 其餘類推 第 行, 每行分別有 2 個元素, 也是以 逗號 區隔, 表示選手需要檢查的 1 組 起點城市 及 終點城市 編號 ( 其值均介於 1 和 8 之間 ) 每個檔案檢查 4 組資料 輸出說明共輸出 4 行結果, 依序表示輸入檔的 4 組起訖城市, 是否存在 正好經過 3 條單行道 的道路? 有則輸出 有路徑, 沒有則輸出 沒路徑 輸入檔案 輸入檔案 1: 檔名 :in1.txt 0, 1, 1, 0, 1, 0, 0, 0 0, 0, 0, 0, 0, 0, 0, 0 0, 0, 0, 0, 0, 1, 1, 0 0, 1, 0, 0, 0, 1, 0, 1 0, 0, 0, 0, 0, 0, 0, 0 0, 0, 0, 0, 1, 0, 0, 0 0, 1, 0, 1, 0, 0, 0, 0 0, 0, 1, 1, 0, 0, 0, 0 1, 5 2, 3 3, 8 4, 1 輸入檔案 2: 檔名 :in2.txt 0, 0, 1, 0, 1, 0, 1, 0 0, 0, 0, 0, 1, 1, 0, 0 0, 0, 0, 0, 0, 1, 0, 1 0, 0, 0, 0, 0, 0, 1, 0 0, 0, 0, 1, 0, 1, 0, 0 0, 0, 0, 0, 0, 0, 1, 0 0, 0, 0, 0, 0, 0, 0, 1 1, 1, 0, 0, 0, 0,0, 0 1, 7 2, 5 3, 6 4, 7-63

64 程式設 計 輸出檔案 輸出檔案 : 檔名 :out.txt 有路徑沒路徑有路徑沒路徑 有路徑沒路徑有路徑沒路徑 演算說明本題採用老鼠走迷宮的演算法, 逐一探索 8 個位置,1 代表有路徑, 即走進去, 並將目前位置與方向放入堆疊, 並繼續往前探索, 若往前沒路, 往後退一步 ( 即自堆疊取出 ) 程式列印 Dim t As Integer Dim s(1000, 3) As Integer Private Sub Form_Load() t = 0 Public Sub push(c, k, j) t = t + 1 s(t, 1) = c s(t, 2) = k s(t, 3) = j Debug.Print t, c, j, k Public Sub pop(c, k, j) c = s(t, 1) k = s(t, 2) j = s(t, 3) t = t - 1 Private Sub Command1_Click() -64

65 商科技藝競賽試題解析 chapter Dim a(8, 8) As Integer Dim b(8, 2) As Integer Open App.Path + \in1.txt For Input As #1 For i = 1 To 8 For j = 1 To 8 Input #1, a(i, j) For i = 1 To 8 For j = 1 To 8 Print a(i, j); Print c = 1: d = 5 起點, 終點 c = 2: d = 3 起點, 終點 c = 3: d = 8 起點, 終點 c = 4: d = 1 起點, 終點 j = 1 k = 1 Do Do While j <= 8 And k <= 3 c1 = a(c, j) If c1 = 1 Then If j = d And k = 3 Then 'success Print 有路徑 GoTo KK push c, k, j + 1 將目前的點, 放入堆疊 k = k + 1 路徑數量 c = j 踩進新的點 j = 1 從方向 1 開始 Else j = j + 1 嘗試下一方向 Loop 8 個點都已經嘗試完畢 pop c, k, j 退回上一點 Loop While t >= 0 And k <= 3 Print 沒路徑 KK: -65

66 程式設 計 䦛三 字串特徵的判斷 此問題為給定某些文句, 請選手判斷這些文句是否符合某些檢查條件? 子題 1.(12%) ) 本子題給定的文句內容只有 英文 數字 空白及標點符號, 並且 沒有 任何全型字 文句中使用的 標點符號 只包括, 及. 2 種 我 們定義一個 表示式, 是一個包含若干個 表示符號 的字串 而本 題的 表示符號 只包括 # * 和 $ 3 種 其中,1 個 # 表示 1 個 0~9 的數字 另,1 個 * 表示 1 個大寫的英文字母, 而 1 個 $ 表示 1 個小寫的英文字母 請選手在檢查文句中, 找尋是否存在符合某個 給定 表示式 的子字串 例如 : 有個 表示式 為 ###**$, 表示為 連續 3 個數字, 緊接著連續 2 個大寫英文字, 其後緊接著 1 個小寫英文 字 輸入說明第 1 行表示欲檢查的 表示式, 其長度不超過 20 個字 第 2~5 行表示待檢查的 4 句英文文句, 每行文句均獨立檢查, 每句文句不超過 100 個字 輸出說明產生 4 行輸出, 依序表示輸入檔第 2~5 行英文文句的檢查結果 若檢查的文句中存在符合 表示式 的子字串, 請輸出 符合 ; 否則輸出 不符合 輸入檔案 輸入檔案 1: 檔名 :in1.txt #***$$ Its password is axyz3kbgna. MA is a code of a machine gun. Your employee number is 5AAAbb. The serial number AQ773276UKD was printed in this case. -66

67 商科技藝競賽試題解析 chapter 輸入檔案 2: 檔名 :in2.txt *#$# Its password is M5k3. This serial number is 63M43Kk. Her employee number is 8J3m75. Those item numbers are AQ43 and KM4M. 輸出檔案 輸出檔案 : 檔名 :out.txt 符合不符合符合不符合符合不符合符合不符合 程式列印 Private Sub Command1_Click() Dim found As Boolean Dim b(4) As String Open App.Path + "\in1.txt" For Input As #1 Input #1, a Print a For i = 1 To 4 Line Input #1, b(i) Print b(i) alen = Len(a) For i = 1 To 4 四句 blen = Len(b(i)) found = False For k = 1 To blen - alen + 1 c = Mid(b(i), k, alen) ' 逐一取出與關鍵字同長度片段 If match(c, a) Then ' 只要一個片段符合, 整句就符合 Print 符合 found = True Exit For -67

68 程式設 計 If Not found Then Print 不符合 Public Function match(c, a) Dim found, f1 As Boolean found = True alen = Len(a) For i = 1 To alen a1 = Mid(a, i, 1) c1 = Mid(c, i, 1) Select Case a1 Case # found = isnum(c1) Case * found = isbc(c1) Case $ found = issc(c1) End Select If Not found Then 只要找到一個字元不符, 整個片段就是不符 match = False Exit Function i match = True End Function Public Function isnum(a) If Asc(a) >= 48 And Asc(a) <= 57 Then isnum = True Else isnum = False End Function Public Function isbc(a) If Asc(a) >= 65 And Asc(a) <= 90 Then isbc = True Else isbc = False End Function Public Function issc(a) If Asc(a) >= 97 And Asc(a) <= 122 Then issc = True Else issc = False End Function -68

69 商科技藝競賽試題解析 chapter 子題 2.(12%) ) 請選手判斷輸入檔中的 4 行文句, 是否存在符合條件的 日期字串 在文句中, 只可能包括 中文 及 半型數字, 並且不包含任何空白及標 點符號 待檢查的 日期字串 格式為 民國 yyy 年 mm 月 dd 日, 其中 民國 年 月 及 日 的順序不可改變 屬於年的 yyy 部分, 合法值是 1~999, 可存在 前置 0, 但其長度僅能是 1 2 或 3 位數 例如民國 9 年, 可表現為 民國 9 年 民國 09 年 或 民國 009 年 關於月份部分, 合法值是 1~12, 同樣接受 前置 0, 其 長度僅能是 1 或 2 位數 日期部分的範圍是 1~31, 亦接受 前置 0, 其長度僅能是 1 或 2 位數 選手應另注意, 符合條件的日期值不應超過該 年當月份的最大天數, 例如某年某月份有 30 天, 則符合條件的日期值為 1~30 註 1 西元年 = 民國年 註 2 在本題限制的年份中, 若其西元年 可被 400 整除 或是 可被 4 整除而且不被 100 整除, 則當年是閏年, 其 2 月有 29 天, 否則為 28 天 輸入說明輸入檔中的第 1~4 行, 表示待檢查的 4 句文句, 每行文句均獨立檢查, 每句文句不超過 100 個字 輸出說明依序 4 行輸出, 分別對應輸入檔第 1~4 行文句之檢查結果 若文句中存在符合條件的 日期字串 請輸出 符合 ; 若不存在時, 請輸出 不符合 輸入檔案 輸入檔案 1: 檔名 :in1.txt 他的生日是民國 89 年 2 月 29 日她的生日是民國 90 月 2 年 29 日民國 90 年 3 月 25 日是他的到職日民國 90 年 25 日 3 月是她的到職日輸入檔案 2: 檔名 :in2.txt 他的生日是民國 89 年 12 月 32 日 -69

70 程式設 計 她的生日是民國 89 年 12 月 31 日民國 090 年 03 月 02 日是他的到職日民國 1000 年 12 月 31 日是她的到職日 輸出檔案 輸出檔案 : 檔名 :out.txt 符合不符合符合不符合不符合符合符合不符合 演算說明 1. 本題判斷閏年程式如下 : '400,800,4,8, 等是閏年 100,200,300 是平年 y = Val(Text1.Text) Dim a(12) As Integer 定義每一個月的日期總數 a(1) = 31: a(2) = 28: a(3) = 31: a(4) = 30: a(5) = 31: a(6) = 30 a(7) = 31: a(8) = 31: a(9) = 30: a(10) = 31: a(11) = 30: a(12) = 31 If y Mod 400 = 0 Or ((y Mod 4 = 0) And (y Mod 100)) <> 0 Then a(2) = 29 Print a(2) 2. 搜尋關鍵字 民國 月 日, 之間的數字即為年 月 日, 並 檢查是否符合 -70

71 商科技藝競賽試題解析 chapter 䦛四 排列組合的應用 子題 1.(9%) ) 某個菜攤最多有 8 種類型的商品出售 當類型齊全時, 該 8 種商品依序包括 肉 菜 蛋 果 魚 蝦 豆 及 菇 假設當菜攤進了 n 種類型商品, 即表示菜攤進了 8 種商品中的前 n 種類型 商品 ( 例如 : 菜攤進了 3 種類型商品, 表示進了 肉 菜 及 蛋 等 3 種商品 ) 今將此 n 類商品由左至右分類排列, 但是 : 肉果 肉豆 肉菇 菜蛋 菜魚 菜豆 菜菇 蛋 果 蛋蝦 蛋菇 果魚 果豆 果菇 魚 蝦 魚豆 魚菇 蝦豆 豆菇 此 18 種商品組合, 兩兩 不可左右緊鄰放置 ( 其間沒有擺設其他商品 ) 以第 1 組 肉果 為例, 肉 不可放在 果 的 正左邊 或 正右邊, 而兩者之間沒有其他 任何商品 在給定 n 的條件下, 請輸出共有哪些商品排列方式 輸入說明第 1 行的數字表示商品進貨種類 n, 而 n 的值介於 1 和 8 之間 輸出說明從第 1 行起每行輸出 1 組符合條件的 商品排列, 每行輸出的 商品排列 間不限制是否有空白相隔, 各種排列方式的輸出順序不限 最後 1 行輸出總共有多少種排列方式 ( 只輸出數字即可 ) 輸入檔案 輸入檔案 1: 檔名 :in1.txt 3 輸入檔案 2: 檔名 :in2.txt 4-71

72 程式設 計 輸出檔案 輸出檔案 : 檔名 :out.txt 菜肉蛋蛋肉菜 2 蛋肉菜果果菜肉蛋 2 演算說明 1. 將不能左右放置的商品以陣列儲存 例如, a(1)=" 肉果 ":a(2)=" 肉豆 ":a(3)=" 肉菇 ":a(4)=" 菜蛋 ":a(5)=" 菜魚 " a(6)=" 菜豆 ":a(7)=" 菜菇 ":a(8)=" 蛋果 ":a(9)=" 蛋蝦 ":a(10)=" 蛋菇 " a(11)=" 果魚 ":a(12)=" 果豆 ":a(13)=" 果菇 ":a(14)=" 魚蝦 ": a(15)=" 魚豆 ":a()=" 魚菇 ":a(17)=" 蝦豆 ":a(18)=" 豆菇 " 2. 三項商品的排列共有 8 種, 四項商品的排列共有 種, 將這些商品一一列 出 3. 將所有排列與 a 陣列比對, 將有 a 陣列部分集合者刪除 例如 :" 肉菜蛋 " 就 不行, 因為含有 " 菜蛋 " 4. 排列問題, 商科每年必考, 請參考本書第 8 章或 98 年解析 ( 見書附光碟第 章 pdf 檔 ) 子題 2.(9%) ) 有一天菜攤上有 8 種類型商品, 包括 肉 菜 蛋 果 魚 蝦 豆 及 菇, 每種產品單項價格由輸入檔輸入 某個前來購買的客人, 共有 k 元預算, 表示客人的總購買金額不可超過 k 元 若客人對於每種類型商品只可選擇買一項或不買, 在預算之內, 客 人共有哪些購買組合? -72

73 商科技藝競賽試題解析 chapter 輸入說明第 1 行是客人之預算金額 k, 其值為整數, 並且不超過 5000 元 第 2~9 行有各商品的品名及單價, 中間以逗號隔開 商品單價均為整數, 且不超過 200 元 輸出說明每行輸出一種符合預算的購買組合及其支出總金額, 但不輸出 都不買 的組合 輸出資料 ( 購買的商品組合及其支出總金額 ) 間, 以至少 1 個空白隔開 若購買組合包括多種商品, 則商品間不限制是否有空白相隔 選手請依支出總金額由大到小依序輸出, 但支出金額相同之資料, 其輸出順序不限 輸入檔案 輸入檔案 1: 檔名 :in1.txt 90 肉, 65 菜, 45 蛋, 30 果, 75 魚, 80 蝦, 95 豆, 55 菇, 60 輸入檔案 2: 檔名 :in2.txt 100 肉, 65 菜, 45 蛋, 30 果, 75 魚, 80 蝦, 95 豆, 55 菇, 60-73

74 程式設 計 輸出檔案 輸出檔案 : 檔名 :out.txt 蛋菇 90 蛋豆 85 魚 80 果 75 菜蛋 75 肉 65 菇 60 豆 55 菜 45 蛋 30 菜豆 100 蝦 95 肉蛋 95 蛋菇 90 蛋豆 85 魚 80 菜蛋 75 果 75 肉 65 菇 60 豆 55 菜 45 蛋 30 演算說明 1. 將八種商品列表如下, 每種商品僅能買或不買, 剛好可以使用 2 進位表示, 所以共有 64 種情況, 但題目規定不可以全不買, 所以還要扣掉編號 0 2. 將編號轉為 2 進位字串, 字串位元對照如下表 : 編號 菇,60(7) 豆,55(6) 蝦,95(5) 魚,80(4) 果,75(3) 蛋,30(2) 菜,45(1) 肉 65(0) 小計 將以上每一情況, 皆計算其小計 4. 當輸出小計符合規定者, 即為其解 -74

75 商科技藝競賽試題解析 chapter 䦛五 特定排序方式的應用 子題 1.(10%) ) 若現在有 8 張撲克牌, 點數分別是 1 點至 8 點, 各張牌的點數都不同, 並且 8 張牌已依點數由小到大排列 選手若要改變排列順序, 只能用 插 牌 動作 假設一個 插牌 的動作, 可以將順序中的第 1 張牌 ( 首牌 ) 插入其他牌的後面, 形成 1 個新的牌組順序 我們現在用 1 個長度為 8 的 字串, 表示 1 個牌組順序 例如以字串 , 表示這 8 張牌現在 依其點數由小到大排列 如果我們進行第 1 次 插牌 動作, 假設將 牌 1 ( 首牌 ) 放到 牌 5 之後, 就形成新的牌組順序 如 果要進行第 2 次的 插牌, 就將 牌 2 ( 首牌 ) 插入其他牌之後, 即可 形成下一個牌組順序 現在給一個 目的地牌組順序, 請從牌組順序 開始, 用最多 7 次的 插牌 動作, 最後轉換成 目的地牌 組順序 輸入說明第 1 行為給定的 目的地牌組順序 字串 ( 長度為 8) 輸出說明第 1 行輸出 起始牌組順序 ( ), 最後 1 行輸出給定的 目的地牌組順序 第 2 行起依序輸出每次 插牌 後的牌組順序 ( 答案並非唯一, 評分時會逐行檢查正確性 ) 輸入檔案 輸入檔案 1: 檔名 :in1.txt 輸入檔案 2: 檔名 :in2.txt

76 程式設 計 輸出檔案 輸出檔案 : 檔名 :out.txt ( 準備提回 1) ( 準備提回 2) ( 準備提回 3) ( 準備提回 4) ( 準備提回 5) ( 準備提回 6) ( 準備提回 7) ( 準備提回 1) ( 準備提回 2) ( 準備提回 3) 演算說明本題乍看之下好像也是老鼠走迷宮的問題, 但嘗試點也未免太多了 仔細觀察題目標題, 往 排序 方面思考, 終於體會如下 : 1. 本題先假設是輸入 a= 若插入一次, 則表示搜尋 1, 並將 1 提回, 所以 a= , 也就是交換一次即可 2. 假設 a= (1) 若僅插入一次, 則先搜尋 1, 將 1 提回, 所以 a= , 但 a 並不等於 , 表示不可能僅插入一次 (2) 假設插入兩次, 則第一次先搜尋 2, 找出 2 的位置, 並將 2 提到前面, 所以 a= , 第二次搜尋 1, 找出 1 的位置, 並將 1 提到前面, 所以 a= , 表示插入兩次即可 3. 同理,a= , 也是先假設插入 1 次,2 次, 直到插入 7 次, 也就是先搜尋 7, 找出 7 的位置, 將 7 提到前面, 得到 a= , 其次, 搜尋 6, 找出 6 的位置, 並將 6 提到前面, 依此類推, 即可求解 -76

77 商科技藝競賽試題解析 chapter 程式列印 Private Sub Command1_Click() Dim b(10) As Integer Dim c(10) As String i = 0 Do i = i + 1 a = a = num = Len(a) 分解為字元陣列 For j = 1 To num b(j) = Val(Mid(a, j, 1)) For j = i To 1 Step -1 For k = 1 To num If b(k) = j Then ' 往前提到位置 1 '1 到 j 先後移 For m = k To 2 Step -1 b(m) = b(m - 1) b(1) = j ' 組合成字串 c(j) = "" For k = 1 To num c(j) = c(j) + Trim(Str(b(k))) 檢查是否全定位 ok = True For j = 1 To num ok = ok And (b(j) = j) Loop Until ok For j = 1 To i Print c(j) Print a -77

78 程式設 計 子題 2.(10%) ) 若現在有 5 張撲克牌, 點數分別是 1 點至 5 點, 各張牌的點數都不同, 並且 5 張牌已依點數由小到大排列 選手若要改變排列順序, 只能用 換牌 動作 假設一個 換牌 的動作, 可以將順序中的第 1 張牌 ( 首牌 ) 與其 他牌 交換 位置, 形成 1 個新的牌組順序 我們現在用 1 個長度為 5 的字 串, 表示 1 個牌組順序 例如以字串 12345, 表示這 5 張牌現在依其點 數由小到大排列 如果我們進行第 1 次 換牌 動作, 假設將 牌 1 ( 首 牌 ) 與 牌 5 交換, 就形成新的牌組順序 如果要進行第 2 次 的 換牌, 就將 牌 5 ( 首牌 ) 與其他牌交換, 即可形成下一個牌組 順序 現在給一個 目的地牌組順序, 請從牌組順序 開始, 用最多 10 次的 換牌 動作, 最後轉換成 目的地牌組順序 輸入說明第 1 行為給定的 目的地牌組順序 字串 ( 長度為 5) 輸出說明第 1 行輸出起始牌組順序 12345, 最後 1 行輸出 目的地牌組順序 第 2 行起依序輸出每次 換牌 後的牌組順序 輸入檔案 輸入檔案 1: 檔名 :in1.txt 輸入檔案 2: 檔名 :in2.txt 輸出檔案 輸出檔案 : 檔名 :out.txt (5. 將首位 3 定位 ) (4. 將首位 4 定位 ) (3. 將首位 5 定位 ) -78

79 商科技藝競賽試題解析 chapter (2. 擬將 5 定位 ) (1. 將首位 2 定位 ) (3. 將首位 5 定位 ) (2. 擬將 4 定位 ) (1. 擬將 2 定位 ) 演算說明本題正向思考也是有點難, 所以依上題的思考模式, 採用反推法, 終於體會如下 : 1. 依序讓 定位, 則 1 也會自動定位 2. 要讓 5 定位, 至少要兩個步驟, 先搜尋 5 的位置, 並與 1 先交換, 其次將位置 1 與位置 5 交換 3. 要讓 4 定位, 至少要兩個步驟, 先搜尋 4 的位置, 並與 1 先交換, 其次將位置 1 與位置 4 交換 4. 同理, 請將 3 與 2 定位, 所以 8 個步驟內一定可以排序完成 5. 因為定位的順序不同, 結果也不同, 所以, 本題答案當然不唯一 例如 : 您也許是先讓 2 定位, 再讓 3 定位 6. 排序完成後, 將排序的過程反相顛倒輸出, 即為本題的解 程式列印 Private Sub Command1_Click() Dim b(5) As Integer Dim c(5) As Boolean Dim e(10) As String Dim ok As Boolean -79

80 程式設 計 a = "21534" ' 將字串分解為字元陣列 For i = 1 To 5 b(i) = Val(Mid(a, i, 1)) c(i) = (b(i) = i) 檢查該位置是否定位 i = 1 e(1) = a Do i = i + 1 If b(1) <> 1 Then Else ' 將該數字定位 d = b(1) t = b(1): b(1) = b(d): b(d) = t c(d) = True ' 已經定位 ' 將該位置提到位置 1 For j = 2 To 5 ' 組合字串 If Not (c(j)) Then For j = 1 To 5 t = b(1): b(1) = b(j): b(j) = t Exit For e(i) = e(i) + Trim(Str(b(j))) ' 輸出排序過程 Print e(i) ' 檢查是否全定位 ok = True For j = 1 To 5 Loop Until ok ' 反向輸出排序過程 Print "OK" ok = ok And (b(j) = j) For j = i To 1 Step -1 Print e(j) -80