全國高級中等學校 100 學年度商業類科學生技藝競賽 程式設計 職種 術科 正式試卷 選手證號碼 : 姓名 : 選手請先閱讀 : 本試題共有 4 個問題, 每個問題有 2 個子題 各個子題有各別指定使用的資料夾, 其中已存放提供選手參考的輸出入檔, 選手的程式及輸出檔亦應存放及產生在相同的資料夾中 每個子題有 2 組測試輸入檔案, 選手的程式應將 輸入檔案 1 及 輸入檔案 2 依序讀入, 並產生 1 個 輸出檔案 選手輸出由 輸入檔案 1 產生的結果後, 請先輸出一行空白, 再輸出 輸入檔案 2 的結果, 以作為區隔 程式在執行時, 應先關閉所有顯示介面及訊息, 畫面不可有任何顯示資訊, 請選手特別注意 ; 與題目要求無關之空格輸出或是否對齊, 不計為錯誤, 選手不必特別處理之 Problem 1: 字串的處理此問題為給定由 整數數字 + - 及 特定符號 組成 邏輯表示式, 判斷此邏輯表示式的敘述是否為真? 子題 1:( 程式執行限制時間 : 3 秒 ) 10 分 使用路徑:c:\Problem1\ 子題 1\ 程式名稱:p11 在此子題中, 邏輯表示式的內容只包括 整數數字 + - == 及 空格 其中 + 代表數字運算的 加法, 而 - 代表 減法 ; 另 == 代表邏輯運算的 是否相等 已知 == 運算, 在前後比較值 相同 時, 其結果為 ; 若 不同 時, 其結果為 在邏輯表示式中的空白均不具運算意義, 選手可忽略之 輸入檔的資料, 每行代表一個邏輯表示式, 請選手判斷其邏輯運算的最後結果 若最後結果為真, 該相對應輸出為 ; 若為假, 輸出 輸入的字串, 不存在邏輯表示式語法的錯誤, 選手可不必另外檢查之 其運算的優先順序是 先算加 減法, 最後才比是否相等 輸入說明 : 每個輸入檔案有 4 行資料, 每行有 1 個邏輯表示式, 每行最多 120 個字 整數數字 介於 0 到 100 之間, 數字運算結果介於正負 1000 之間 輸出說明 : 依序列出輸入檔對應的邏輯表示式檢查結果 若輸入行檢查結果為真, 該行相對應輸出為, 反之輸出 ( 輸出均為大寫, 選手請注意 ) 第 1 頁, 共 19 頁
輸入檔案 1: 檔名:in1.txt 25+4-33+22-2==16 15+30==13-58 20+10-50==40-60 20==10+10+10+10-30 輸入檔案 2: 檔名:in2.txt 24-4+10==10-40 33+5-10==43-5-5-3-2 10-20-30==30-40-30 30-40+10==10-20+30-20 輸出範例 : 檔名:out.txt 第 2 頁, 共 19 頁
子題 2:( 程式執行限制時間 : 3 秒 ) 14 分 使用路徑:c:\Problem1\ 子題 2\ 程式名稱:p12 在此子題中, 邏輯表示式 除了原有的 整數數字 + - == 及 空格 外, 另外有一個運算符號 *, 代表 乘法運算, 其運算優先權 高於 加法及減法 請選手在輸出檔中輸出相對表示式檢查的結果 輸入說明 : 每個輸入檔案有 4 行資料, 每行有 1 個邏輯表示式, 每行最多 120 個字 整數數字 介於 0 到 100 之間, 數字運算結果介於正負 1000 之間 輸出說明 : 依序輸出對應的邏輯表示式檢查結果 若輸入行之檢查結果為真, 該行輸出為, 反之輸出 ( 輸出均為大寫, 選手請注意 ) 輸入檔案 1: 檔名:in1.txt 20+3*5==7*5 13*3+2*3==123 6+5*4-8==18 4-5+15-3*3==0 輸入檔案 2: 檔名:in2.txt 10*3+5==5*7 12*4-10+5==43 72-10*5==20+2 5-4*10+50==60 輸出檔案 : 檔名:out.txt 第 3 頁, 共 19 頁
Problem 2: 二維陣列的應用子題 1:( 程式執行限制時間 : 3 秒 ) 12 分 使用路徑:c:\Problem2\ 子題 1\ 程式名稱:p21 有一長及寬均是 15 公分的正方形地圖, 其長及寬各以 1 公分為長度畫分為 15 個小單位, 而地圖內共有 225 個單位 在這些單位中, 有的已被填色, 有的是空白 被 填色 的單位代表其 不可通過, 而 空白 的單位則 可通行 假設地圖上 最左上角 及 最右下角 分別代表 起點 及 終點, 起 迄兩點一定是 空白, 請問從起點到終點, 在最多只能通過若干個空白單位的限制條件下, 是否有可通行的路徑?( 任一單位只能透過上 下 左 右四個方向連到下一單位 ) 輸入說明 : 第 1 行是最多能通過的空白單位數目 ( 不包括起點及終點 ) 第 2~16 行是第 1 張地圖的資料, 依序代表地圖上的每個橫列 每行有 15 個符號, 依序代表地圖上每個橫列的 15 個小單位 若符號為 0, 表示該單位為 空白 ; 若為 1, 表示已 填色 第 17 行為空行 接著另有 15 行資料, 代表第 2 張地圖, 其表示方式和第 1 張地圖相同 輸出說明 : 第 1 2 行是輸入檔案 1 的檢查結果 第 1 行輸出第 1 張地圖在條件限制下是否有可通行的路徑, 若有則輸出, 沒有則輸出 第 2 行輸出第 2 張地圖的檢查結果, 其值是 或 第 3 行是空白 第 4 5 行是輸入檔案 2 的檢查結果 第 4 行輸出第 1 張地圖的檢查結果, 其值是 或 第 5 行輸出第 2 張地圖的檢查結果, 其值是 或 ( 輸出均為大寫, 選手請注意 ) 第 4 頁, 共 19 頁
輸入檔案 1: 檔名:in1.txt 40 011111110010000 000000000010000 000001000010000 000001000010000 000001000010000 111101000010000 000001011000000 000001000000000 100001000011111 100000000000000 100111111111110 100000000000000 100000000001000 100000000001000 100000000001000 011111110010000 000000000010000 000001000010000 000001000011110 000001000010010 111110100010100 000001011000100 000001001000100 100001001011111 100000001000000 100111111111111 100000100110000 100000100001000 100000000001000 100000000001000 第 5 頁, 共 19 頁
輸入檔案 2: 檔名:in2.txt 40 000000000000111 100011111110000 100010000000000 111110000000000 100000000000000 100010111111111 100010000000000 100010001111000 101010001001000 101110001001000 100000001001000 111111111001000 000000000001000 000000000001000 000000000000110 010000000000000 010000000111100 010000000100100 000000000100100 111111111100100 000001000000100 000001001000100 000001001000100 000001001000100 000001001000000 000001001111111 000001000100000 000001000100000 000001000100000 000000000000000 第 6 頁, 共 19 頁
輸出檔案 : 檔名:out.txt 第 7 頁, 共 19 頁
子題 2:( 程式執行限制時間 : 3 秒 ) 16 分 使用路徑:c:\Problem2\ 子題 2\ 程式名稱:p22 假設地圖上的每個小單位都有一個 (x, y) 座標, 其中 x 代表該單位的橫列值,y 代表縱列值 地圖上 最左上角 的小單位其座標值是 (1, 1), 該橫列第 15 個小單位其座標值是 (1, 15); 第 15 個橫列的第 1 個小單位是 (15, 1), 該橫列最後 1 個小單位是 (15, 15) 如果我們任意給定地圖上 起點 及 終點 的座標, 在地圖上此兩點均為 空白, 請問從起點到終點, 在最多只能通過若干個空白單位的限制條件下, 是否有可通行的路徑?( 任一單位只能透過上 下 左 右四個方向連到下一單位 ) 輸入說明 : 第 1 行是最多能通過的空白單位數目 ( 不包括起點及終點 ) 第 2~16 行是地圖的資料, 依序代表地圖上的每個橫列 每行有 15 個符號, 依序代表地圖上每個橫列的 15 個小單位 若符號為 0, 表示該單位為 空白 ; 若為 1, 表示已 填色 第 17 行為空行 第 18 19 行是檢測第 1 組資料 第 18 行是 起點座標, 第 1 個數字是起點的 x 座標, 空格後接著 y 座標 第 19 行是 終點座標, 第 1 個數字是終點的 x 座標, 空格後接著 y 座標 第 20 行為空行 第 21 22 行是檢測第 2 組資料 第 21 行是 起點座標, 第 1 個數字是起點的 x 座標, 空格後接著 y 座標 第 22 行是 終點座標, 第 1 個數字是終點的 x 座標, 空格後接著 y 座標 輸出說明 : 第 1 2 行是輸入檔案 1 的檢查結果 第 1 行輸出第 1 組檢測資料, 在通過空白單位數目限制下, 是否有可通行的路徑, 若有則輸出, 沒有則輸出 第 2 行輸出第 2 組檢測資料的檢查結果, 其值是 或 第 3 行是空白 第 4 5 行是輸入檔案 2 的檢查結果 第 4 行輸出第 1 組檢測資料的檢查結果, 其值是 或 第 5 行輸出第 2 組檢測資料的檢查結果, 其值是 或 ( 輸出均為大寫, 選手請注意 ) 第 8 頁, 共 19 頁
輸入檔案 1: 檔名:in1.txt 15 011111110010000 000000000010000 000001000010000 000001000011110 000001000010010 111110100010100 000001011000100 000001001000100 100001001011111 100000001000000 100111111111111 100000100110000 100000100001000 100000000001000 100000000001000 3 3 5 13 14 11 8 5 第 9 頁, 共 19 頁
輸入檔案 2: 檔名:in2.txt 15 010000000000000 010000000111100 010000000100100 000000000100100 111111111100100 000001000000100 000001001000100 000001001000100 000001001000100 000001001000000 000001001111111 000001000100000 000001000100000 000001000100000 000000000100000 3 3 6 3 10 7 10 10 輸出檔案 : 檔名:out.txt 第 10 頁, 共 19 頁
Problem 3: 檢查碼問題 子題 1:( 程式執行限制時間 : 3 秒 ) 11 分 使用路徑:c:\Problem3\ 子題 1\ 程式名稱:p31 中華民國身分證的號碼是經由一串公式所產生出來的, 目前中華民國身分證字號一共有十碼, 包括第一個大寫的英文字母與接續的九個阿拉伯數字 (1) 第一個碼代表地區, 轉換方式為 :A 轉換成 1,0 兩個字元,B 轉換成 1,1, 餘如下 : A B C D E F G H I J K L M N O P Q R S T U V W X Y Z 10 11 12 13 14 15 16 17 34 18 19 20 21 22 35 23 24 25 26 27 28 29 32 30 31 33 (2) 第二個碼代表性別,1 代表男性,2 代表女性 (3) 第三個碼到第九個字元為流水號碼 (4) 第十個碼為檢查號碼 例如 :A123456789,A 的轉換字元是 1 和 0, 其餘各碼亦轉換成字元 轉換後的字元數值依序存在的變數中, 如下 : 1 0 1 2 3 4 5 6 7 8 9 n 1 n 2 n 3 n 4 n 5 n 6 n 7 n 8 n 9 n 10 n 11 然後再把每一個變數, 依序乘上 1 9 8 7 6 5 4 3 2 1 1 的加權, 再相加, 如下 : 將身分證號碼 A123456789 套入公式, 其結果為 : 然後再除以 10, 如果整除, 該組身分證字號為有效 在客服電話系統中, 需要使用者輸入個人身分證號碼, 因為電話按鈕只有數字鍵, 為了方便使用者輸入身分證, 只輸入身分證後面 9 個數字, 再由客服電話系統告知那些英文字母和這輸入身分證後面 9 個數字合起來是有效的身分證號碼, 由使用者最後確認身分證號 請寫出客服電話系統需要的程式, 使用者輸入身分證後面 9 個數字, 找出對應有效的英文字母 例如輸入身分證後面 9 個數字 123456789, 和這數字合起有效的身分證號碼為 A123456789 M123456789 和 W123456789, 則客服電話系統中依英文字母順序輸出 AMW 第 11 頁, 共 19 頁
輸入說明 : 第 1 行的數字 n 代表有幾筆資料要測試,n 的值介於 1 和 5( 含 ) 之間, 之後每行為身分證後面 9 個數字, 不含第一個大寫的英文字母 程式不用檢查輸入格式 輸出說明 : 從第 1 行起每行輸出對應的英文字母, 其和輸入身分證後面 9 個數字可合為有效的身分證號碼 列出這些對應到有效的身分證號碼的所有字母, 結果依英文字母順序大寫輸出 ( 輸出均為大寫, 選手請注意 ) 輸入檔案 1: 檔名:in1.txt 3 123456789 123456788 223344556 輸入檔案 2: 檔名:in2.txt 3 102345678 108881111 101111111 輸出範例 : 檔名:out.txt AMW KLY DOQ ER GT BNZ 第 12 頁, 共 19 頁
子題 2: ( 程式執行限制時間 : 2 秒 ) 14 分 使用路徑:c:\Problem3\ 子題 2\ 程式名稱:p32 漢明碼 (Hamming Code) 1. 具有自動偵錯與更正錯誤一個位元的功能, 兩個位元有誤只能偵測 2. m 個位元資料, 須 r 個同位元查出錯誤 而 m 和 r 的限制式為 m+r+1 2^r 3. 同位元 (Parity) 放置位置為 2^(r-1) m: 資料位元長度 r: 檢查位元長度 (2^r) n: 總傳送位元數 ( n= m+ r ) 舉例來說, 如果需要傳送 7 個位元 110 0001 資料, 則 m = 7,7+4+1 < =2^4,r 由限制式算出至少為 4, 因此 r= 4,n = 7 + 4, 檢查位元需要 4 個位元 如果需要傳送 16 個位元資料, 則檢查位元需要 5 個位元 同位元檢查, 分為兩種, 一種為奇同位檢查另一種為偶同位檢查, 以偶同位例子來說, 0110110, 已經有 4 個 1, 其值為偶數, 所以偶同位元就填入 0, 保持為 1 的個數為偶數, 資料加偶同位為 01101100 接下來的計算都用偶同位 假設, 要傳的 16 位元資料為 0001 0010 0011 0101, 則其漢明碼的檢查碼至少需五碼, 分別為 P1P2P3P4P5, 要傳送的位元資料的 1 2 4 8 16 這幾個位置插入這五位元的漢明碼檢查碼, 如下圖 : 位置 1 2 3 4 5 6 7 8 9 10 11 P1 P2 0 P3 0 0 1 P4 0 0 1 位置 12 13 14 15 16 17 18 19 20 21 0 0 0 1 P5 1 0 1 0 1 目前檢查位元 P1 P2 P3 P4P5 是未知, 對應的位置分別為 1 2 4 8 16, 需要透 過同位元檢查來取得, 位置分別以十進制和二進制表示, 如下圖 : 位置 二進位數字 1(00001) 0 0 0 0 P1 2(00010) 0 0 0 P2 0 3(00011) 0 0 0 0 0 4(00100) 0 0 P3 0 0 5(00101) 0 0 0 0 0 6(00110) 0 0 0 0 0 7(00111) 0 0 1 1 1 8(01000) 0 P4 0 0 0 9(01001) 0 0 0 0 0 10(01010) 0 0 0 0 0 第 13 頁, 共 19 頁
11(01011) 0 1 0 1 1 12(01100) 0 0 0 0 0 13(01101) 0 0 0 0 0 14(01110) 0 0 0 0 0 15(01111) 0 1 1 1 1 16(10000) P5 0 0 0 0 17(10001) 1 0 0 0 1 18(10010) 0 0 0 0 0 19(10011) 1 0 0 1 1 20(10100) 0 0 0 0 0 21(10101) 1 0 1 0 1 同位元檢查 1 0 1 0 0 要注意的是位置 7 11 15 17 19 21 為 1, 所以在二進位數字那邊分別要填入 00111 01011 01111 10001 10011 10101, 其他數字因為都為 0, 所以位置填 00000 同位元檢查那邊以 P1 那一欄來說, 一共有 6 個 1, 所以 P1 需要填入 0,P5 那一欄來說, 一共有 3 個 1, 所以 P5 需要填入 1,P2P3P4 以此類推,16 位元資料 0001 0010 0011 0101, 漢明碼檢查碼 P1P2P3P4P5 為 00101 十六進制在數學中是一種逢 16 進 1 的進位制, 一般用數字 0 到 9 和字母 A 到 F 表示 ( 其中 :A~F 即 10~15), 由 1,2,3,---,9,A,B,C,D,E,F 等十六個基本數字所組成, 數量計數從 0 到 F, 滿十六即進位, 其中 A,B,C,D,E,F 分別代表十進制的 10,11,12,13,14,15 例如十進制數 78, 在二進制寫成 01001110, 在 16 進制寫成 4E(4 = 0100, E = 1110) 下表列出 0~15 的二進制 十進制與十六進制的對照 : 二進制 十進制 十六進制 0000 0 0 0001 1 1 0010 2 2 0011 3 3 0100 4 4 0101 5 5 0110 6 6 0111 7 7 1000 8 8 1001 9 9 1010 10 A 第 14 頁, 共 19 頁
1011 11 B 1100 12 C 1101 13 D 1110 14 E 1111 15 F 假設每筆輸入資料都有 16 位元 ( 二進制 ) 資料要傳送, 輸入資料以十六進制來表示, 以 4 位元 ( 二進制 ) 為一字元 ( 十六進制 ), 則每筆輸入資料四個字元, 每個字元為 0~9 和 A~F 輸入說明 : 第 1 行的數字 n 代表有幾筆資料要傳送,n 的值介於 1( 含 ) 和 5( 含 ) 之間, 每筆輸入資料為四個字元的十六進制, 字元 A~F 為大寫 程式不用檢查輸入格式 輸出說明 : 輸出為四個字元資料所對應的漢明碼 P1P2P3P4P5 檢查碼 輸入範例 : 檔名:in1.txt 5 1235 1234 6F00 8000 1000 輸入範例 : 檔名:in2.txt 2 C80B 8828 輸出範例 : 檔名:out.txt 00101 10000 11100 11000 11100 00111 11101 第 15 頁, 共 19 頁
Problem 4: 其他 子題 1: 找零錢問題 ( 程式執行限制時間 : 2 秒 ) 8 分 使用路徑:c:\Problem4\ 子題 1\ 程式名稱:p41 假設在某地區使用的銅板有 50 元 20 元 10 元 5 元 1 元共五種 今天媽媽請小華去買東西換銅板回來, 且媽媽交待, 要小華請老闆找零錢的數目要最少, 小華帶了 n 張的 100 元紙幣, 買了 n 項金額少於 100 元東西, 有 n 筆數量的零錢要找給小華, 請幫老闆算一算每筆交易需找多少個 50 元 20 元 10 元 5 元 1 元的銅板, 其銅板數目最少 輸入說明 : 檔案輸入第一行為總共幾筆金額, 其值介於 1( 含 ) 和 5( 含 ) 之間, 接下來是每筆交易金額大小, 交易金額介於 0( 不含 ) 和 100( 不含 ) 之間 輸出說明 : 請算出每筆交易金額可換回的銅板數量, 每筆交易都會各別找回 50 元 20 元 10 元 5 元 1 元銅板若干, 請算出每筆交易找回的銅板, 依序計算其 50 元銅板數量,20 元銅板數量,10 元銅板數量,5 元銅板數量,1 元銅板數量總和 例如三筆交易金額分別為 59 51 34, 每筆交易找回的銅板分別為 : 50,0 20,2 10,0 5,0 1,1 50,0 20,2 10,0 5,1 1,4 50,1 20,0 10,1 5,1 1,1 最後輸出交易找回 50 元 20 元 10 元 5 元 1 元銅板總合 : 50,1 20,4 10,1 5,2 1,6 例如二筆交易金額分別為 25 10, 每筆交易找回的銅板分別為 : 50,1 20,1 10,0 5,1 1,0 50,1 20,2 10,0 5,0 1,0 最後輸出交易找回 50 元 20 元 10 元 5 元 1 元銅板總合 : 50,2 20,3 10,0 5,1 1,0 每個檔案 in1.txt 和 in2.txt, 各輸出一個結果 第 16 頁, 共 19 頁
輸入範例 : 檔名:in1.txt 3 59 51 34 輸入範例 : 檔名:in2.txt 2 25 10 輸出範例 : 檔名:out.txt 50,1 20,4 10,1 5,2 1,6 50,2 20,3 10,0 5,1 1,0 第 17 頁, 共 19 頁
子題 2: 撲克牌遊戲 ( 程式執行限制時間 : 3 秒 ) 15 分 使用路徑:c:\Problem4\ 子題 2\ 程式名稱:p42 小朋友常喜歡玩很多撲克牌的遊戲 撲克牌有四種花色, 黑桃 紅桃 方塊 和梅花 同花順 為同花色五張連續數字, 相同花色的 順子 四條 為四張同數字的牌, 外加任一單張的五張牌 ; 葫蘆 為三張同數字, 另兩張同數字的牌 ; 一個 一對 和 三條 所組成的五張牌 ; 順子 為五張數字連續的牌, 數字各差 1 點的連續牌, 從最小 A-2-3-4-5(1-2-3-4-5), 到最最大 10-J-Q-K-A(10-11-12-13-14), 但不包括 J-Q-K-A-2 的連續方式 三條 為三張同數字; 兩對 是有兩對兩兩同數字的牌; 一對 則是只有兩張同數字; 雜牌 指不屬於以上任何一種組合 五張牌依照牌面可能有多種組合, 一般判斷大小的順序如下 : 同花順 > 四條 > 葫蘆 > 順子 > 三條 > 兩對 > 一對 > 雜牌同樣組合時, 先比數字大小 (A 最大再來是 K(13) 大,2 最小 ), 再比花色 每張牌以一個字母表示花色 (S 表黑桃,H 表紅桃,D 表方塊,C 表梅花 ) 及一個介於 1~13 之間的數字 (A:1 J:11 Q:12 K:13) 花色大小順序為 : 黑桃 > 紅桃 > 方塊 > 梅花 例如黑桃同花順 9 10 J(11) Q(12) K(13) 小於紅桃同花順 10 J(11) Q(12) K(13) A, 但大於方塊同花順 9 10 J(11) Q(12) K(13) 葫蘆以三條的大小作判斷, 也就是說 2 2 10 10 10 大於 8 8 9 9 9 兩對則以較大的對作判斷, 同樣數字時, 有黑桃的人贏 例如 :H1 D6 C6 H12 S12 大於 H2 D9 C9 D12 C12, 因為 S12 為黑桃 12 雜牌以其中最大的牌作判斷 請幫小朋友們寫個程式, 判斷那個小朋友手上的五張牌, 找出誰的牌最大和最小 輸入說明 : 輸入資料含多個測試案例, 每個檔案 in1.txt 和 in2.txt 都在各有一副牌 52 張的情況下, 第 1 行的數字 n 代表有幾筆資料要測試, 而 n 的值介於 3( 含 ) 和 8( 含 ) 之間, 每個案例有五張牌, 每個測試案例, 是其中一位小朋友手上的牌 輸出說明 : 按照小朋友手上的五張牌, 在 n 個測試案例中, 找出那個小朋友的牌是最大和最小, 結果按照原來牌的順序輸出那二位小朋友牌是最大和最小的五張牌 每個檔案 in1.txt 和 in2.txt, 各找出一組最大和最小的五張牌 第 18 頁, 共 19 頁
輸入範例 : 檔名:in1.txt 4 S3 H5 S4 D5 C5 H7 H8 H10 H9 H11 H1 D6 C6 H12 S12 D12 C12 D9 C9 S13 輸入範例 : 檔名:in2.txt 4 D2 H5 S2 D5 C5 D3 H4 S1 D7 C8 H1 S7 C7 H13 S13 C2 S3 S4 S6 S8 輸出範例 : 檔名:out.txt H7 H8 H10 H9 H11 D12 C12 D9 C9 S13 D2 H5 S2 D5 C5 D3 H4 S1 D7 C8 第 19 頁, 共 19 頁