二、跑長編碼與資料壓縮 ( 10分 )
跑長編碼(Run-Length Coding)是一種常見的資料壓縮技術,特別適用於字串樣式重複頻率高的情況。其編碼格式為(重複樣式,重複次數),例如一個二元字串 0000001111111001111可編碼為(0,6) (1,7) (0,2) (1,4),因為樣式0 重複了 6 次,而之後的樣式1則重複了 7 次。
寫一個程式來壓縮一個長位元串,並輸出壓縮比率(壓縮後位元個數除以原位元個數,四捨五入到整數百分比)。重複位元的長度用3個位元來表示(最大連續長度為7),放在重複位元的後面,形成一個4位元的碼字(code word)。輸入是一長串連續的位元(長度小於500),不可有0、1之外的字元、數字、或空格。輸出則是編碼後的4位元碼字,可能是(0,連續0的長度)或(1,連續1的長度),兩個碼字之間用一個空格分開,最後是四捨五入的壓縮率。如果輸入不是一個2進制位元串,直接輸出-1。
* 測資均為官方測資
* 為模擬正式競賽,WA 時 不公開正確答案!
* 加油~ !
輸入資料中第一列為一整數n,代表接下來有n組測試資料。
第二列開始共有n列,每列有一個二元字串。
輸出跑長編碼後的數個4位元碼字以及壓縮率,各碼字與壓縮率皆用空格分開。
4 00010000000111111101111111 11111100000000000000111111111111110000 0011 1111100000101010 HINET0800000123
0011 1001 0111 1111 0001 1111 92% 1110 0111 0111 1111 1111 0100 63% -1 -1
編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
37553 | alen24816@gm ... (AlenLU(軟工一014呂宥...) | e522 | 279 | 2023-09-16 21:10 | |
40344 | channoliu@gm ... (channo liu) | e522 | 115 | 2024-05-12 12:26 | |
22792 | joeliao (RRRrrrr!!!) | e522 | 989 | 2020-10-02 16:53 |