主題

ZeroJudge - f384: 次承的痘痘 解題心得

Not In My Back Yard | 2020-11-11 00:00:01

題目連結:


題目大意:
給定以下數字 0 ~ 15 對應的編碼(只由 0 、 1 組成):
請觀察上圖得到規律。

每列給定一個編碼,請解碼出原本的數字。



範例輸入:
範例輸入 #1
0
1
11
10

範例輸入 #2
1000
1001
1010
1011



範例輸出:
範例輸出 #1
0
1
2
3

範例輸出 #2
15
14
12
13


解題思維:
經過一番通靈,可以發現題目給定的編碼為格雷碼(Gray Code,參見維基)。

因此所求即是將格雷碼轉成對應的數字。方式如下:
設長度為 n 的格雷碼為 Gn Gn-1 …… G1 、所求數字為 n 位元二進位數字 Bn Bn-1 …… B1,並定義一變數 L = 0 (L 只會是 0 或是 1)。
將 L 設為 L XOR Gn 之值,此時 L 的值即為 Bn
將 L 設為 L XOR Gn-1 之值,此時 L 的值即為 Bn-1
……
將 L 設為 L XOR G1 之值,此時 L 的值即為 B1

然後將二進位數字 Bn Bn-1 …… B1 輸出成十進位數字即可。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。
61 巴幣: 0

更多創作