題目一：加密解密 題目說明：有一台簡易的二位元加密解密機，其功能如下：選擇加密或是解密功能。機 器會將你輸入的數字轉換成二進位數值，之後依照你所設定的位移碼將此段二進位數值 向右位移，並把超過的位數再從尾端放入，如此一來便形成一項新的二進位數值碼，最 後再將此段二進位數值轉換成十進位數字，得到一個新的數字，則加密完成。同樣地， 當選擇解密時，也是先將數字轉換成二進位之後，依照輸入的位移量，向左位移，並把 超出的位數由前端補入，最後將此一新的二進位數值轉為十進位後，解碼完成。請寫一 個程式，完成此加密解密的功能。 輸入檔說明：輸入檔中第一行為一個正整數N，代表共有N 測試資料。每組資料有兩行， 第一行有兩個數字，第一個數字為0 代表是加密，1 代表是解密，第二個數字 K( 0 昼 K 昼100000 )，代表位移幾位。第二行為一連串以空格格開的數字，每個數字介 於 0 到255 之間。 輸出說明：將每組測試資料結果輸出於一行，共N 行。 Sample Run: Input file: Output: 2 1 1 12 15 17 0 3 50 18 19 255 24 30 34 70 66 98 255 解題方法說明：這是一個非常簡單的題目，首先，我們讀入總共有的資料數量N，表示 接下來有N 筆資料要處理，所以用一個迴圈跑N 次。 接下來，讀入資料a 和b，a 表示加密或解密，b 則表示加解密時輪轉的位數。 知道a 和b 之後，我們開始一個一個的讀入數字。 把數字讀進來以後，用一個陣列把這些數字轉換成2 進位，方法就是一直對這數字除二 取餘數。 做完以後我們可以得到八個數字，分別表示八個bit。 在有了這八個數字以後，我們只要依照先前讀進來的a 和b，就可以知道我們該從哪個 bit 當作新的數字的第一個bit，之後只要把數字還原回十進位，本題就可以輕鬆解決。 需要注意的是，因為沒有告訴你每組資料有幾筆數字，所以你必須要會判斷是否讀到換 行，否則萬事休矣。 祝你考試順利。 3 題目二：求最大公因數 題目說明：以輾轉相除法，求兩正整數之最大公因數。例如，60 與96 的最大公因數為 12，其計算過程如下： 96=60×1 + 36 60=36×1 + 24 36=24×1 + 12 24=12×2 + 0 總共經過4 次運算，得到最後結果。 輸入檔說明：輸入檔中第一行為一個正整數N，代表共有N 測試資料。每組資料有兩個 正整數，自行判斷前後哪個數字較大。 輸出說明：將每組測試資料所需之運算次數及最大公因數輸出於一行，以空格分隔，共 N 行。 Sample Run: Input file: Output: 4 60 96 12 15 50 18 36 36 4 12 2 3 4 2 1 36 4 題目三：將資料逐一加入max heap 題目說明：Max heap 是一個complete binary tree 且其中任一節點的鍵值都不小於其子 節 點的鍵值。將一筆資料加入一個現有的max heap 時，先加入一個節點在樹的最後面（保 持complete binary tree 的特性），然後採用bubbling up 的方式調整鍵值。如果節點 的鍵 值大於其父節點的鍵值，就將兩個鍵值交換，直到無法往上交換為止。以圖1 為例，若 要加入一筆鍵值為9 的資料，第一步就是將新節點加在原來heap 的最後面，如圖2 所 示。接著就是將新的鍵值逐步調整到適當的位置，如圖3 及圖4 所示。本題需要將輸入 檔內的鍵值資料以一次一筆的方式加入一個max heap，完成後將max heap 中的所有鍵 值以breadth-first search 的順序全部列出。 輸入檔說明：輸入檔內有一行N 個正整數（N <= 100）代表要逐一加入的鍵值資料，各 個數字中間有一個空格隔開，最後還有一個0 代表結束。 輸出說明：輸出一行結果，依breadth-first search 的順序顯示max heap 中的所有鍵值 ， 各個鍵值間以一個空格隔開。 11 6 7 4 5 5 6 2 圖1 11 6 7 4 5 5 6 2 9 圖2 11 6 7 9 5 5 6 2 4 圖3 11 9 7 6 5 5 6 2 4 圖4 5 Sample Run: Input file: Output: 6 4 5 11 5 7 6 2 9 0 11 9 7 6 5 5 6 2 4 6 題目四： Pachinko 題目說明：假設Pachinko 鋼珠往下跑，碰到釘柱時，往左與往右跑的機率不一定相同， 又假 設釘柱的排列最高處只有一個，每往下一排增加一個釘柱。若共有N 排釘柱，則最底下一 排 有N 個釘柱，最底下則有N+1 個口袋。以下圖為例，各有2 排釘柱，假設鋼珠碰到每個釘 柱 時，往左與往右跑的機率比例依序(由上而下、由左至右)為 1:2、2:3、3:1，則鋼珠進到 每個 口袋的機率依序為2/15(=1/3*2/5)、7/10(=1/3*3/5+2/3*3/4)、1/6(=2/3*1/4)。 輸入檔說明：輸入檔內第一行為一個正整數N (N <= 10)，代表共有N 排的釘柱，之後各 行為 依由上而下、由左至右之釘柱順序，鋼珠往左與往右跑的機率比例。 輸出說明：依由左至右順序，輸出鋼珠落到每一口袋的機率(至小數點以下2 位)，各個機 率 值間以一個空格隔開。 解題方法說明：把原來的圖轉一下，一排一排考慮，當讀取一釘柱的左右機率後，往左的 機 率乘上碰到這根釘柱的機率，加給下一排同一位置的釘柱(或口袋)；往右的機率乘上碰到 這 根釘柱的機率，加給下一排下一個位置的釘柱(或口袋)。 儲存鋼珠碰到釘柱(及口袋)機率的資料結構，可以用一個二維矩陣，或用兩個一維陣列。 記得要初始化為零，但碰到最高處那個釘柱的機率是1。 2/3 * 1/4 2/3 * 3/4 1/3 * 3/5 1 1/3 2/3 1/3 * 2/5 1 1/3 2/3 7 Sample Run: Input file: Output: 3 1 3 2 1 3 5 2 5 6 5 3 4 0.05 0.32 0.37 0.27 8 題目五：算術運算式計算 題目說明：有數筆資料，每筆資料有n 個欄位，欄位值為1 至99 間之整數，欄位編號0 至 n-1，n 小於10。欲對每筆資料做算術運算，假設算術運算只有加(+)、減(-)、乘(*)等三 種， 又假設算術運算式不考慮運算子之優先順序，例如：某算術運算式 1 + 3 * 0 表示 (欄 位1 + 欄位3) * 欄位0，若某一筆資料各欄位值依序為 2, 5, 1, 6, 3，則依此算術運算式針對 此筆資 料之計算結果為 (5 + 6) * 2 = 22。請依各算術運算式計算所有資料之計算結果總合。 算術運算式中不會出現不存在之欄位編號，但是欄位編號在算術運算式中可以重複出 現，算術運算式之運算元個數不超過10 個，計算結果可能為負數，也可能是較大整數， 須使 用long int。 輸入檔說明：輸入檔第一行為兩個整數M N，表示共有M 筆資料，每筆資料有N 個欄位， 數據間以空格隔開。第二行起為每筆資料。資料之後一行是一個整數K，表示有K 個算術 運 算式。每一算術運算式最後以q 表示該算術運算式結束。 輸出說明：每一算術運算式輸出一個結果。 Sample Run: Input file: Output: 6 5 9 8 4 7 2 6 8 5 3 3 6 6 3 3 2 15 8 4 7 2 11 5 1 7 2 8 6 5 5 3 3 1 + 3 * 0 q 2 * 2 - 1 + 3 q 4 - 2 * 0 + 0 - 1 - 3 * 2 q --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.130.189.43