靜宜大學資訊學院 程式設計解題範例 中華民國一 六年十一月三十一日

靜宜大學資訊學院 程式設計解題範例 中華民國一 六年十一月三十一日

目錄 目錄... I 程式範例 1. 名稱 : 判斷日期先後順序... 1 程式範例 2. 名稱 : 密文解碼... 2 程式範例 3. 名稱 : 三號出局... 3 程式範例 4. 名稱 : 比較字串的大小... 4 程式範例 5. 名稱 : 發鈔票... 5 程式範例 6. 名稱 : 絕對值最小的乘積... 6 程式範例 7. 名稱 : 二進位制的加法... 7 程式範例 8. 名稱 : 最大公因數及最小公倍數... 8 程式範例 9. 名稱 : 數字比對... 9 程式範例 10. 名稱 : 英文字母大小寫更換... 10 程式範例 11. 名稱 : 二維整數座標點間的最短距離計算... 11 程式範例 12. 名稱 : 輸入數字總合計算... 12 程式範例 13. 名稱 : 質因數分解... 13 程式範例 14. 名稱 : 尋找數字... 14 程式範例 15. 名稱 : 整數集合之交集與聯集... 15 程式範例 16. 名稱 : 統計字母出現次數... 17 程式範例 17. 名稱 : 十進位轉換十四進位... 18 程式範例 18. 名稱 : 後序式的四則計算... 19 程式範例 19. 名稱 : 二維座標點排序... 20 程式範例 20. 名稱 : 繪製長條圖... 22 程式範例 21. 名稱 : 猜數字遊戲... 23 程式範例 22. 名稱 : 計算找零錢的所有找法... 24 程式範例 23. 名稱 : 前段和與後段和... 25 程式範例 24. 名稱 : 迴文數目... 26 程式範例 25. 名稱 : 路徑問題... 27 程式範例 26. 名稱 : 盈數 虧數與完全數問題... 28

程式範例 27. 名稱 : 身分證驗證... 29 程式範例 28. 名稱 : 平面上的極大點... 30 程式範例 29. 名稱 : 邏輯運算... 32 程式範例 30. 名稱 : 字串讀取... 33 程式範例 31. 名稱 : 三角形的最小路徑... 34 程式範例 32. 名稱 : 圓括號對應 Parenthesis Matching... 35 程式範例 33. 名稱 : 二元樹的拜訪 Binary Tree Traversal... 36 程式範例 34. 名稱 : 二元樹的節點分析 Binary Tree Node Analysis... 37 程式範例 35. 名稱 :Max Heap Construction... 38 程式範例 36. 名稱 : 建立二元搜尋樹 Binary Search Tree Construction... 39 程式範例 37. 名稱 : 迴文質數... 40 程式範例 38. 名稱 : 前置計算器... 41 程式範例 39. 名稱 : 三個整數的最大公因數及最小公倍數... 42 程式範例 40. 名稱 :3n+1 基本題... 43 程式範例 41. 名稱 :3n+1 進階題... 44 程式範例 42. 名稱 : 態度最重要 的人生密碼... 45 程式範例 43. 名稱 :Ugly Numbers... 46 程式範例 44. 名稱 : 阿姆斯壯數... 47 程式範例 45. 名稱 :RGB 三色顯示調整... 48 程式範例 46. 名稱 : 旋轉字串... 49 程式範例 47. 名稱 : 分式加法... 50 程式範例 48. 名稱 : 整數位元組對調... 51 程式範例 49. 名稱 : 單字長度排序... 52 程式範例 50. 名稱 : 反轉句中的單字... 53 II

程式範例 1. 名稱 : 判斷日期先後順序 題目難度 [*] 輸入日期 A 與日期 B 若日期 A 在 B 之前, 輸出 Before ; 若日期 A 在 B 之後, 輸出 After ; 若日期 A 與 B 相同, 輸出 Same 兩個日期 A 與 B, 格式為 dd/mm/yyyy 日期之間以空格隔開 兩個日期 A 與 B 的先後關係 04/05/1999 20/02/1995 04/05/1999 20/02/2003 20/02/2003 20/02/2003 After Before Same 1

程式範例 2. 名稱 : 密文解碼 題目難度 [*] 某公司為了避免在網路上傳輸的訊息被竊取, 所以將所有的英文字母做移位, 再傳給客戶 假設傳輸的文字只考慮 26 個大寫英文字母, 且移位規則如下 : 原來字母 A B C X Y Z 轉換後字母 D E F A B C 請將客戶收到的已移位訊息自動轉回原來的文字 一段編碼過的文字, 該文字由 26 個大寫英文字母組成 將收到的文字解碼 DSSOH CRR APPLE ZOO 2

程式範例 3. 名稱 : 三號出局 題目難度 [*] 有 n 個人圍成一圈, 順序排號 ( 從 1 號編到 n 號 ) 從第一個人開始報數( 從 1 到 3 報數 ), 凡報到 3 的人出局退出圈子, 問最後留下的是第幾號 輸入人數 n, n > 50 最後一個未出局者的編號 1 5 2 60 3 100 1 4 2 41 3 91 3

程式範例 4. 名稱 : 比較字串的大小 題目難度 [*] 輸入三個實文字串, 將此三個字串由小而大輸出到定串 輸入三個字串 先比較第一個字元大小, 如同等再比較第兩個字元, 如還相等繼續往下比, 比完由小而大輸出字串 abc cde bkg abc bkg cde 4

程式範例 5. 名稱 : 發鈔票 題目難度 [*] 某國共發行了 1,5,10,50,100 不同面額的鈔票, 若有人要從銀行領出 N 元, 銀行行員要如何發給鈔票, 則使用的張數會最少 正整數 1-N 1, 5-N 2, 10-N 3, 50-N 4, 100-N 5 (N 1, N 2, N 3, N 4, N 5 為大於等於零的整數 ) 478 1022 555 1-3, 5-1, 10-2, 50-121, 100-4 1-2, 5-0, 10-2, 50-0, 100-10 1-0, 5-1, 10-0, 50-1, 100-5 5

程式範例 6. 名稱 : 絕對值最小的乘積 題目難度 [*] 輸入五個整數, 任取二個數相乘, 輸出這些乘積中絕對值最小者 五個整數, 數與數之間用 space 隔開 整數 2-5 7-2 1 3 4 5-6 -7-3 4 5-2 -1 2 12 2 6

程式範例 7. 名稱 : 二進位制的加法 題目難度 [*] 假設有一系統採 2 進位制 ( 只有 0, 1), 寫一程式可做二個 2 進位制之數之加法 兩個二進位制的整數, 數與數之間用 space 隔開 二進位制的整數 111 1 1000 1001 10101 1010 1000 10001 11111 7

程式範例 8. 名稱 : 最大公因數及最小公倍數 題目難度 [*] 計算兩個正整數的最大公因數及最小公倍數 兩個正整數, 數與數之間用 space 隔開 最大公因數 :S, 最小公倍數 :T (S 及 T 為正整數 ) 27 18 1000 49 200 40 最大公因數 :9, 最小公倍數 :54 最大公因數 :1, 最小公倍數 :49000 最大公因數 :40, 最小公倍數 :200 8

程式範例 9. 名稱 : 數字比對 題目難度 [*] 輸入一個正整數 n, 再輸入 n 個整數, 由小到大輸出有重複的整數值及其重複次數 輸入一個正整數 n, 再輸入 n 個小於 10000 的整數 由小至大輸出有重複出現的整數及次數 5 6 8 6 8 8 6 2 8 3 9

程式範例 10. 名稱 : 英文字母大小寫更換 題目難度 [*] 輸入一段以英文字母的組成的字串, 並且將字串中開頭與所有位於句點之後的第一個非大寫的英文字母改成大寫 輸入一段英文字母的字串, 最少有一句點後第一個字母為英文小寫字母 輸出開頭與所有句點後第一個字母皆為大寫的字串 This is a book. that is a pen. they are students. this is a iphone5s. it is a nice phone. I will buy it. This is a book. That is a pen. They are students. This is a iphone5s. It is a nice phone. I will buy it. 10

程式範例 11. 任意兩點之間的最短距離 名稱 : 二維整數座標點間的最短距離計算 題目難度 [*] 輸入一個點的個數 n, 然後輸入 n 個二維整數座標值 這 n 個點任意兩點之間的最短距離 取到小數點 1 位 ( 四捨五入 ) 1 3 5 3 2 7 5 1 2 4 5 3 2 9 1 15 3 7 3 5 2 9 11 3 7 16 5 38 12 2 1 2.0 2 2.2 3 1.4 11

程式範例 12. 名稱 : 輸入數字總合計算 題目難度 [*] 輸入一字串, 統計出 : 字串中包含的數之總和 輸入的字串由英文字母 數字 空白組成 ( 句子前面可能有空白, 兩 words 的間隔空白可 能不只一個 ) 輸出字串中包含的數之總和 25 is 5 5 book 100 135 12

程式範例 13. 名稱 : 質因數分解 題目難度 [*] 設計一程式, 輸入一個正整數, 改用質因數乘積表達此數, 若該質因數出現多次, 則用次方表示之 例如 : 12 = 2 ^ 2 * 3 50 = 2 * 5 ^ 2 輸入一個正整數 n 輸出能表達正整數 n 的質因數乘積積 1 1000 2 127 3 123456 1 1000=2^3*5^3 2 127 3 123456=2^6*3*643 13

程式範例 14. 名稱 : 尋找數字 題目難度 [*] 請寫一個程式, 判斷一個數字 N 出現在另外一個數字 M 中的次數 N 為小於 100 的非負整數, M 9999999 每筆資料有兩個整數,N 和 M,0 N 99,-9999999 M 9999999 每筆測資輸出一個整數, 也就是 N 出現在 M 裡面的次數, 以及 N 出現在 M 裡面的位數, 輸出格式請參考以下範例 第一行輸出的數值代表出現的次數, 第二行將所在的位數加以輸入 1 90 9090999 2 11 1110111 3 230 1230230 1 2 // 出現兩次 7 5 // 出現在右邊數過來第 7 位數與第 5 位數 2 4 7 6 3 2 3 2 6 3 14

程式範例 15. 名稱 : 整數集合之交集與聯集 題目難度 [*] 利用兩個一維整數陣列儲存兩個元素為正整數的集合 A B, 程式必須包括以下功能 : (1) 插入一個集合元素 ;(2) 運算兩個集合的交集 ;(3) 運算兩個集合的聯集 n 1 n 2 : 將正整數 n 2 輸入集合 n 1 (n 1 = 1 代表集合 A,n 1 = 2 代表集合 B) 印出 A 集合的所有元素, 由小到大排列, 中間以 ',' 分隔, 不含空白 印出 B 集合的所有元素, 由小到大排列, 中間以 ',' 分隔, 不含空白 判斷 A 集合是否為 B 集合的子集合, 若是則印出 "A B", 否則印出 "A B" 印出 A B 交集的所有元素, 由小到大排列, 中間以 ',' 分隔, 不含空白 印出 A B 聯集的所有元素, 由小到大排列, 中間以 ',' 分隔, 不含空白 1 1 3 1 1 1 4 2 5 2 2 2 3 2 1 26 1 19 2 51 2 26 2 33 2 19 3 1 38 1 11 1 24 1 50 2 11 2 38 1 1,3,4 15

2,3,5 A B 3 1,2,3,4,5 2 19,26 19,26,33,51 A B 19,26 19,26,33,51 3 11,24,38,50 11,38 A B 11,38 11,24,38,50 16

程式範例 16. 名稱 : 統計字母出現次數 題目難度 [*] 以小寫英文字母輸入一行英文句子後, 列出句子中出現的英文字母以及每個字母出現的的次數 如果輸入的字母包含大寫, 將之視為小寫 任意輸入一行英文, 內容不拘 依照英文字母的排序規則, 列出句子中出現的英文字母以及其出現的的次數 1 How are you. 2 Good morning. 3 Try your best to do it. 1 (a,1)(e,1)(h,1)(o,2)(r,1)(u,1)(w,1)(y,1) 2 (d,1)(g,2)(i,1)(m,1)(n,2)(o,3)(r,1) 3 (b,1)(d,1)(e,1)(i,1)(o,3)(r,2)(s,1)(t,4)(u,1)(y,2) 17

程式範例 17. 名稱 : 十進位轉換十四進位 題目難度 [*] 將一個十進位數字轉換成十四進位, 其 0 到 13 的表示法為 {0,1,,9,A, D} 輸入一個十進位數字 n (500 n 10000 ) 輸出其十四進位表示法 1 600 2 2000 3 5000 1 30C 2 A2C 3 1B72 18

程式範例 18. 名稱 : 後序式的四則計算 使用後序表示法來進行四則運算 題目難度 [**] 輸入一個運算式的後序表示法, 每個數字或符號之間用空格隔開 在後序式表示法中, 其中輸入的數字個數在十個以內 輸出運算結果 1 12 5 2 * - 2 1 2 + 3 * 4 5 * + 25-3 1 2 + 3 4 * + 4 7 * 6 2 / - + 1 2 2 4 3 40 19

程式範例 19. 名稱 : 二維座標點排序 題目難度 [*] 輸入 n 個二維平面上的座標點, 所有的座標點按照以 x 軸座標為第一關鍵字,y 軸座標為第二關鍵字的優先順序從小到大來進行排序 輸入一個點的個數 n, 然後輸入 n 個二維整數座標值 按照以 x 軸座標為第一關鍵字,y 軸座標為第二關鍵字的方式從小到大來進行排序印出 1 3 5 3 2 7 5 1 2 4 3 7 6 8 3 4 9 3 3 5 2 8 7 9 5 4 6 2 2 4 5 8 1 2 7 5 1 5 3 2 3 4 3 7 6 8 9 3 20

3 2 4 2 8 5 4 5 8 6 2 7 8 9 10 9 21

程式範例 20. 名稱 : 繪製長條圖 題目難度 [**] 輸入 20 筆介於 0 至 100 的整數 若輸入值介於 90 到 100, 則將其歸類為 "Grade A"; 若輸入值介於 80 到 89, 則歸類為 "Grade B"; 若輸入值介於 70 到 79, 則歸類為 "Grade C"; 若輸入值介於 60 到 69, 則歸類為 "Grade D"; 若輸入值介於 0 到 59, 則歸類為 "Grade E" 統計出每一類的數量, 並以星號畫出直長條圖 整數 N 1 N 2 N 3 N 20,0 N 1,N 2,N 3,,N 20 100 畫出以星號構成之直長條圖, 以 E D C B A 為 x 軸數值, 每一個長條圖以空格隔開 1 78 66 32 69 78 88 92 95 76 66 89 73 87 44 52 65 62 71 65 82 2 77 69 62 79 78 88 98 93 86 66 10 53 32 10 49 59 22 99 39 19 3 18 66 22 68 72 88 92 96 77 66 89 77 97 52 61 60 71 45 55 33 1 * * * * * * * * * * * * * * * * * * * * - - - - - E D C B A 2 * * * * * * * * * * - - - - - E D C B A 3 * * * * * * * * * * * * * * * * - - - - - E D C B A 22

程式範例 21. 名稱 : 猜數字遊戲 題目難度 [**] 程式需要使用者輸入四位數的解答, 每一位數的數值介於 1 到 9, 而且不可重複 程式需定義一個方法 ( 函式 ), 將解答的四個數值分別儲存於整數陣列的第一至第四個元素中 ( 索引值 0 至 3), 並回傳 程式執行時, 由使用者從鍵盤輸入四位數的猜數, 程式自動判斷使用者猜測的結果為幾個 A 幾個 B 規則 : 使用者猜測的四位數中, 若某一數之位置和數值都與程式產生的數一致, 則為 1A; 若猜測的某一數值出現在答案中但位置不對, 則為 1B 程式需定義一個方法( 函式 ), 包含一個整數參數和一個長度為 2 的整數陣列參數 (guess(int num, int[] result) ) 陣列參數的第一個元素紀錄猜中 A 的個數, 第二個元素紀錄猜中 B 的個數 方法 ( 函式 ) 執行完畢將此陣列回傳 四位數整數 n 1 n 2 n 3 n 4,1 n 1,n 2,n 3,n 4 9,n 1 n 2 n 3 n 4 輸出幾個 A 幾個 B 以及猜數與解答 1 1234 7164 2 9876 6541 3 1357 2751 1 1A1B 猜數 :1234 解答 :7164 2 0A1B 猜數 :9876 解答 :6514 3 1A2B 猜數 :1357 解答 :2751 23

程式範例 22. 名稱 : 計算找零錢的所有找法 題目難度 [**] 如果你有不限量的 1 元 5 元 10 元的硬幣, 要找 n 元給顧客, 有幾種找法? 例如 : 15 元中分別用 (1 元, 5 元, 10 元 ) 的找法有 (15,0,0)(10,1,0) (5,2,0) (5,0,1) (0,3,0) (0,1,1) 等 6 種 請輸入你要給顧客的金額大小 輸出共有幾種找零錢方法 1 10 2 20 3 100 1 4 2 9 3 121 24

程式範例 23. 名稱 : 前段和與後段和 題目難度 [**] 假設有一個陣列 x[], 它有 n 個元素, 每一個都大於零 ; 我們說 x[0]+x[1]+...+x[i] 是個前段和 (Prefix Sum), 而 x[j]+x[j+1]+...+x[n-1] 則是個後段和 (Suffix Sum) 請寫一個程式, 求出 x[] 中有多少組相同的前段和與後段和 輸入一個整數 n, 再輸入 n 個整數給 x[0] x[1]... 到 x[n-1] 輸出陣列中有多少組相同的前段和與後段和 1 6 1 2 3 4 5 6 2 6 2 2 2 2 2 2 3 10 1 2 3 4 5 6 7 8 9 10 1 3 2 6 3 3 25

程式範例 24. 名稱 : 迴文數目 題目難度 [**] 所謂的 迴文, 就是指一個字串從頭開始唸跟倒著唸結果完全一樣 例如 abccaaccba 就是一個迴文字 而所謂的 全排列, 則是指一個字串裡的每個字母在經過順序的調換以後所能得到的各種排列 例如 abcd 的全排列就是 : abcd abdc acbd acdb adbc adcb bacd badc bcad bcda bdac bdca cabd cadb cbad cbda cdab cdba dabc dacb dbac dbca dcab dcba 請寫出一個程式, 對於輸入的字串, 算出在這個字串的全排列裡有多少個是迴文 例如 aabb 的全排列為 :aabb abab abba baab baba bbaa, 其中 abba 和 baab 是迴文, 因此 aabb 的全排列裡有 2 個迴文 輸入一行長度至少為 1 且不超過 20 的字串, 這個字串會完全由小寫的英文字母構成 請輸出這行字串的全排列中, 存在的迴文總數 ( 如果全排列裡一個迴文都沒有的話, 就輸出 0) 1 cccaaddbb 2 aaabbb 3 aaaabbcccc 1 24 2 0 3 30 26

程式範例 25. 名稱 : 路徑問題 題目難度 [**] 在座標上, 我們從原點 (0,0) 出發, 每次移動只能往上 往右 往右上 三種方向其中一種方向前進, 所有路徑座標 x 恆大於等於 y; 我們可以以人工的方式算出, 走到 (1,1) 有 2 種走法 (2,2) 有 6 種走法 輸入兩個正整數 x y, 代表終點位置的座標 輸出總共有幾種走法 1 2 2 2 3 3 3 4 5 1 6 2 22 3 90 27

程式範例 26. 名稱 : 盈數 虧數與完全數問題 題目難度 [**] 對一個正整數 N 而言, 將它除了本身以外所有的因數加起來的總和為 S, 如果 S>N, 則 N 為盈數, 如果 S<N, 則 N 為虧數, 而如果 S=N, 則 N 為完全數 (Perfect Number) 例如 10 的因數有 1 2 5 10,1+2+5=8<10, 因此 10 為虧數, 而 12 的因數有 1 2 3 4 6 12,1+2+3+4+6=16>12, 因此 12 為盈數 至於 6 的因數有 1 2 3 6, 1+2+3=6, 所以 6 是完全數 輸入一個正整數 N 印出 N 是盈數 虧數還是完全數 1 30 2 26 3 28 1 盈數 2 虧數 3 完全數 28

程式範例 27. 名稱 : 身分證驗證 題目難度 [**] 我國的身分證字號有底下這樣的規則, 因此對於任意輸入的身分證字號可以有一些基本 的判斷原則, 請您來判斷一個身分證字號是否是正常的號碼 ( 不代表確有此號 此人 ) (1) 英文代號以下表轉換成數字 A=10 台北市 J=18 新竹縣 S=26 高雄縣 B=11 台中市 K=19 苗栗縣 T=27 屏東縣 C=12 基隆市 L=20 台中縣 U=28 花蓮縣 D=13 台南市 M=21 南投縣 V=29 台東縣 E=14 高雄市 N=22 彰化縣 W=32 金門縣 F=15 台北縣 O=35 新竹市 X=30 澎湖縣 G=16 宜蘭縣 P=23 雲林縣 Y=31 陽明山 H=17 桃園縣 Q=24 嘉義縣 Z=33 連江縣 I=34 嘉義市 R=25 台南縣 (2) 英文轉成的數字, 個位數乘 9 再加上十位數的數字 (3) 各數字從右到左依次乘 1 2 3 4...8 (4) 求出 (2),(3) 及最後一碼的和 (5) (4) 除 10 若整除, 則為 real, 否則為 fake 例 : T112663836 2 + 7*9 + 1*8 + 1*7 + 2*6 + 6*5 + 6*4 + 3*3 + 8*2 + 3*1 + 6 = 180 除以 10 整除, 因此為通過驗證的身分證字號 一組身分證號碼 true ( 通過 ) 或 false( 不通過 ) 1 T112663836 2 S154287863 3 K121406861 1 true 2 false 3 false 29

程式範例 28. 名稱 : 平面上的極大點 題目難度 [***] 在平面上如果有兩個點 ( x, y ) 與 ( a, b ), 我們說 ( x, y ) 支配 (Dominate) 了 ( a, b ) 這就是指 x a 而且 y b; 用圖來看就是 ( a, b ) 座落在以 ( x, y ) 為右上角的一點無的區域中 對於平面上的任意一個有限點集合而言, 一定存在有若干個點, 它們不會被集合中的內一點所支配, 這些個數就構成一個所謂的極大集合 請寫一個程式, 讀入一個新的集合, 找出這個集合中的極大值 若找不到一點在 ( x, y ) 的右上方, 則 ( x, y ) 就要輸出 輸入一個數字 N ( 1 N 50,0000 ), 代表接下來有 N 組點坐標, 每行上有兩個數字 x, y ( 0 X,Y 100000 ) 分別代表一點的 X 軸座標, 與 Y 軸座標 請依照 X 軸的大小, 由小輸出至大 1 11 0 8 1 10 3 4 4 6 4 9 5 8 6 9 7 5 8 7 9 8 10 6 2 4 1 8 2 9 2 2 4 6 3 5 30

8 9 2 9 3 6 7 8 2 11 1 Dominate Point: 4 // 點的個數 (1,10) (6,9) (9,8) (10,6) 2 Dominate Point: 2 // 點的個數 (2, 9) (4, 6) 3 Dominate Point: 2 // 點的個數 (8,9) (2,11) 31

程式範例 29. 名稱 : 邏輯運算 題目難度 [**] 對二進位的數字每一個位元進行 and (&&) 和 or ( ) 運算, 運算規則如下 : 1 and 1 = 1,1 and 0 = 0,0 and 1 = 0,0 and 0 = 0 1 or 1 = 1, 1 or 0 = 1, 0 or 1 = 1, 0 or 0 = 0 每一輸入行是二進位字串加上運算子 and 或 or 所組成的運算式, 其中的二進位字串長度都是 5 bit 每一行的最後會有一個空白, 例如 : 10001 or 10000 and 11101 and 01001 依序是一個運算元 + 空白 + 運算子 + 空白 + 運算元 +... 最後是運算元 + 一個空白 把運算式中的運算子 and 和 or 分別以 && 和 取代之, 然後輸出運算後的答案 ( 行末 無空白 ) 10001 or 10000 and 11101 and 01001 10111 or 10111 or 10010 or 00101 10001 10000&&11101&&01001 = 00001 10111 10111 10010 00101 = 10111 32

程式範例 30. 名稱 : 字串讀取 題目難度 [*] 練習字串的分析與處理 一個字串, 內部包含數組資料, 每組資料有一個序號, 及一個實數 格式如下 : 序號 : 實數請注意, 序號有可能跳號 令 M 為序號為奇數的實數總和,N 為序號為偶數的實數總和, 請印出差值 M - N 1 1:12.5 2:12 3:13.1 4:13.0 2 1:1.2 3:2.3 1 0.6 2 3.5 33

程式範例 31. 名稱 : 三角形的最小路徑 題目難度 [**] 數字三角形的構圖如下 : 44 25 2 7 18 3 4 6 5 24 19 34 8 31 19 請找出一條由頂端到底部的路徑, 其經過的數字總和是最小值 首先輸入三角形的點數 N ( N<50), 此處三角形一定是完整三角形, 所以 N=1,3,6,10,15,... 再輸入 N 個正整數, 代表該三角形由上而下 由左而右的數字 輸出該最小路徑及路徑和 1 15 44 25 2 7 18 3 4 6 5 24 19 34 8 31 19 2 3 5 2 9 1 44+2+3+5+8=62 2 5+2=7 34

程式範例 32. 名稱 : 圓括號對應 Parenthesis Matching 題目難度 [**] 找出給定的運算式中適當的左圓括號與右圓括號的對應配對, 並輸出找到的配對的索引值 若輸入的運算式無法找到對應的配對, 無配對部份索引值以 -1 填入 輸入一個包含圓括號的運算式, 將運算式儲存到陣列中 假設輸入的運算式的長度小於等於 40 輸出找到的最接近的左圓括號與右圓括號配對的索引值 每輸出一個配對, 就需換行 1 (a+(b*c)/(d-e)+f) 2 ((a+b)-c*e)+(e*(f-g) 1 3,7 9,13 0,16 2 1,5 0,10 15,19 12,-1 35

程式範例 33. 名稱 : 二元樹的拜訪 Binary Tree Traversal 題目難度 [**] 輸入以陣列表示法記錄的一棵二元樹 在陣列表示法中, 索引值 0 的元素未用到, 並被設定為 0 實際上二元樹的樹根儲存在索引值 1 的位置 我們假設給定的二元樹的元素數值皆為正整數, 而空節點的數值為 0 將這棵二元樹進行前序式 (preorder) 中序式(inorder) 後序式(postorder) 拜訪的結果輸出 輸入一個正整數 n, 紀錄這這棵二元樹在陣列表示法所需的空間 再輸入 n 個整數 分行依序輸出這棵二元樹的前序式 中序式 後序式拜訪的結果 個別元素之間以空白隔開 1 4 0 1 2 3 2 8 0 1 2 3 4 5 6 7 1 1 2 3 2 1 3 2 3 1 2 1 2 4 5 3 6 7 4 2 5 1 6 3 7 4 5 2 6 7 3 1 36

程式範例 34. 名稱 : 二元樹的節點分析 Binary Tree Node Analysis 題目難度 [*] 輸入以陣列表示法記錄的一棵二元樹 在陣列表示法中, 索引值 0 的元素未用到, 並被設定為 0 實際上二元樹的樹根儲存在索引值 1 的位置 我們假設給定的二元樹的元素數值皆為正整數, 而空節點的數值為 0 將這棵二元樹的內部節點的個數與樹葉節點的個數輸出 輸入一個正整數 n, 紀錄這這棵二元樹在陣列表示法所需的空間 再輸入 n 個整數 分行依序輸出這棵二元樹的內部節點的個數與樹葉節點的個數 1 4 0 1 2 3 2 8 0 5 4 2 0 6 1 0 1 1 2 2 3 2 37

程式範例 35. 名稱 :Max Heap Construction 題目難度 [**] 輸入 n 個正整數, 將個別正整數依序加入到 Max Heap 中 Max Heap 是一棵 complete binary tree, 祖先節點的數值會比子孫節點的數值來的大 輸入一個正整數 n, 假設 n < 16 再輸入 n 個正整數來建立一棵 Max Heap 輸出 Max Heap 的高度輸出 Max Heap 的陣列表示法 索引值 0 的元素未用到, 並被設定為 0 高度是 2 則輸出 4 筆資料 ; 高度是 3 則輸出 8 筆資料 ; 高度是 4 則輸出 16 筆資料 1 5 1 2 3 4 5 2 8 2 6 3 7 8 4 5 9 1 3 0 5 4 2 1 3 0 0 2 4 0 9 8 5 7 6 3 4 2 0 0 0 0 0 0 0 38

程式範例 36. 名稱 : 建立二元搜尋樹 Binary Search Tree Construction 題目難度 [**] 輸入 n 個正整數, 將個別正整數依序加入到二元搜尋樹中 在二元搜尋樹中左子樹節點 的數值會比樹根來的小 ; 右子樹節點的數值會比樹根來的大 輸入一個正整數 n, 假設 n <=10 再輸入 n 個正整數來建立一棵二元搜尋樹 輸出二元搜尋樹的高度輸出二元搜尋樹的陣列表示法 索引值 0 的元素未用到, 並被設定為 0 高度是 2 則輸出 4 筆資料 ; 高度是 3 則輸出 8 筆資料 ; 高度是 4 則輸出 16 筆資料 1 4 1 2 3 4 2 7 3 5 4 6 8 9 2 1 4 0 1 0 2 0 0 0 3 0 0 0 0 0 0 0 4 2 5 0 3 2 5 0 0 4 6 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 39

程式範例 37. 名稱 : 迴文質數 題目難度 [*] 從鍵盤輸入一正整數, 判斷其是否為迴文且為質數, 若是, 則輸出 "YES", 若否, 則輸出 "NO" 迴文係指從左至右與從右至左讀取此整數皆為同一數值 整數 N,0 < N 若 N 是迴文且為質數, 輸出 "Yes.", 否則輸出 "No." 1 121 2 191 1 NO 2 YES 40

程式範例 38. 名稱 : 前置計算器 題目難度 [**] 假設有一前置運算式由任意數字與 $, % 所組成, 運算式長度不能超過 30 個字元 $ 與 % 所代表的是運算子, 其中 $ 代表 x $ y = (x + y)/2, % 代表 x % y = (x - y)/2,x, y 是任意整數或浮點數 前置運算式包含任意整數與 $, %, 輸入以空白鍵隔開且長度不可超過 30 個字元 運算式結果 ( 到小數點六位 ) 1 $ 3 9 2 % 5 7 1 6.000000 2-1.000000 41

程式範例 39. 名稱 : 三個整數的最大公因數及最小公倍數 題目難度 [**] 計算三個正整數的最大公因數及最小公倍數 三個正整數, 數與數之間用 space 隔開 最大公因數 :S, 最小公倍數 :T (S 及 T 為正整數 ) 1 54 90 36 2 75 180 300 1 18 540 2 15 900 42

程式範例 40. 名稱 :3n+1 基本題 題目難度 [*] 輸入一整數值 n, 若 n 為奇數, 則令 n = 3*n + 1; 否則, 令 n = n/2, 以迴圈方式執行上述判斷, 直到 n = 1 才停止, 過程中需將 n 的值印出 [ 補充 : 此題之學問在於是否能找到某個數字 n, 使得程式無法收斂至 1? 截至目前為止, 尚未找到這樣的數字 n] 正整數 n,n<1000000 輸出計算過程 n 的值 5 22 60 5 16 8 4 2 1 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 60 30 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1 43

程式範例 41. 名稱 :3n+1 進階題 題目難度 [**] 3n+1 問題為 : 輸入一整數值 n, 若 n 為奇數, 則令 n = 3*n + 1; 否則, 令 n = n/2, 以迴圈方式執行上述判斷, 直到 n = 1 才停止 我們將數字收斂的次數稱為 n 的 cycle length 例如 : 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 表示數字 22 的 cycle length 為 16 今輸入兩個任意整數 i 和 j ( i < j 且 i, j < 1000000), 請輸出 i, j 之間 ( 包含 i, j) 的數值中, 最大的 cycle length 值為何 任意 2 個整數 i, j (i <j 且 i, j < 1000000) i, j 及最大的 cycle length 值 1 10 100 200 201 210 1 10 20 100 200 125 201 210 89 44

程式範例 42. 名稱 : 態度最重要 的人生密碼 題目難度 [*] 如果我們將英文字母依序編號 A = 1, B = 2,, Z = 26, 將某個單字的各別字母轉換為前述的數字後相加便得到一個分數 例如 : Knowledge 96 Attitude 100 由以上可推得 態度 最重要的人生密碼 小明為了驗證此事, 請你寫支程式替他解惑 [ 提示 :A-Z 的 ASCII 十進位數字 = 65-90, a-z 的 ASCII 十進位數字 = 97-122] 輸入英文單字, 大小寫不限 輸出轉換數字後的相加結果, 若字串中包含非 A~Z(a~z) 之字元, 則輸出 Fail hardwork knowledge attitude ~True 98 96 100 Fail 45

程式範例 43. 名稱 :Ugly Numbers 題目難度 [**] 已知 Ugly Number 的定義為 : 該數之質因數必須為 2, 3 或 5 依照慣例,1 也算是 Ugly Number 故前 11 個 Ugly Numbers 列舉如下 : 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15 請寫一個程式求出第 n 個 Ugly Number 任意整數 n, 表示求第 n 個 Ugly Number 輸出 n 的值與第 n 個 Ugly Number 11 20 1500 11 15 20 36 1500 859963392 46

程式範例 44. 名稱 : 阿姆斯壯數 題目難度 [**] 所謂阿姆斯壯數 (Armstrong number) 指的是一個 n 位數的整數, 它的所有位數的 n 次方和恰好等於自己 例如 :1634 = 1 4 + 6 4 + 3 4 + 4 4 請依題目需求在一定範圍內找出該範圍內的所有阿姆斯壯數 輸入包含兩個數字 n, m(n<m, n>0, m<=1000000), 代表尋找的範圍 由小到大依序印出範圍內的阿姆斯壯數, 若沒有則印出 none 100 999 10 99 153 370 371 407 none 47

程式範例 45. 名稱 :RGB 三色顯示調整 題目難度 [*] 用一個整數來表示一個畫素的三原色資料, 其紅 (r) 綠(g) 藍(b) 各用 8 個 bit 表示, 各有 0~255 共 256 種強度, 假設三原色的編碼是由右到左 1-8 bit 為紅,9-16 bit 為綠,17-24 bit 為藍 如果我們輸入一個 10 進位整數 ( 小於 2 24 ), 其表示一個畫素的三原色數值, 請將這個畫素的三個顏色數值都增加 5( 超過 255 則以 255 計 ), 然後輸出這個畫素的整數值 例如 : 輸入 258 ( 相當於 0x000102, r=2,g=1,b=0) 則調整後的整數值為 329223 ( 相當於 0x050607, r=7, g=6, b=5) 輸入一個整數 ( 小於 2 24= 16777216), 請將這個畫素的三個顏色數值都增加 5( 超過 255 則以 255 計 ), 然後輸出這個畫素的整數值 1 258 2 123456 3 654321 1 329223 2 452421 3 983030 48

程式範例 46. 名稱 : 旋轉字串 題目難度 [**] 輸入一個字串, 將字串中的非空白及標點字元往右挪移一個位置, 形成一個新的字串, 原來字串的大小寫位置需保留不變 例如 : 輸入 : How about Mary? 輸出 : Yho Wabou Tmar? 輸入一個英文字串 將英文字母字元往右挪移一個位置後輸出 1 Try to study hard. 2 Yesterday, I listened to the radio. 3 Old friend, why are you so shy? 1 Dtr yt ostud yhar. 2 Oyesterda, Y ilistene dt oth eradi. 3 Yol dfrien, dwh yar eyo us osh? 49

程式範例 47. 名稱 : 分式加法 題目難度 [*] 輸入兩個分數, 把兩個分數相加, 變成一個約分過的最簡分數 ( 如果分數的值大於 1, 用假分數表示, 不要轉成帶分數 ) 例如: 輸入 : 1/4 1/2 輸出 : 3/4 輸入兩個分數, 分子分母都是 1 到 9 的整數 輸出這兩個分數和的最簡分數 1 1/4 1/2 2 2/3 3/4 3 1/8 3/8 1 3/4 2 17/12 3 1/2 50

程式範例 48. 名稱 : 整數位元組對調 題目難度 [*] 輸入一個整數 (4 個 byte), 將其第 1 個 byte ( 最低位元組 ) 和第 3 個 byte 對調之後的整數值印出 例如 : 整數 65540 (2 16 +2 2 ) 經過第 1 和第 3 byte 對調之後, 會變成數字 262145 (2 18 +2 0 ) 輸入一個整數 將其第 1 個 byte ( 最低位元組 ) 和第 3 個 byte 對調之後的整數值印出. 1 1 2 65536 3 65538 1 65536 2 1 3 131073 51

程式範例 49. 名稱 : 單字長度排序 題目難度 [*] 輸入 n 個英文單字, 請依照每個單字的字母個數由小到大列運出來 例如, 輸入 : see you tomorrow 輸出 : 3:see you 8:tomorrow 輸入一個數字 n (n <10), 然後輸入 n 個英文單字 依照每個單字的字母個數由小到大列運出來 1 3 see you tomorrow 2 10 Now it looks as though they are here to stay 3 4 Oh yesterday came suddenly 1 3:see you 8:tomorrow 2 2:it as to 3:Now are 4:they here stay 5:looks 6:though 3 2:Oh 4:came 8:suddenly 9:yesterday 52

程式範例 50. 名稱 : 反轉句中的單字 題目難度 [*] 輸入一個句子, 將句子中以空格 標點隔開的單字反過來列印 例如 : 輸入 : Good morning! 輸出 : doog gninrom! 輸入一個英文句子 將句子中的每個單字反過來列印 1 Try to study hard. 2 Yesterday, I listened to the radio. 3 Gagaoolala! Want your bad romance. 1 yrt ot yduts drah. 2 yadretsey, I denetsil ot eht oidar. 3 alalooagag! tnaw ruoy dab ecnamor. 53