31. 葛雷碼

反射二進位編碼-葛雷碼 (Gray code),是編碼成兩個連續的位元不同。
輸入 n ,編碼範圍 0<=i<=2^n-1。
n = 3,編碼 0~7 為 000, 001, 011, 010, 110, 111, 101, 100。
其編碼方式如下
G_1 = {0, 1}

G_1_r = {1, 0}
G_n = {0G_(n-1), 1G_(n-1)_r }
if G_n = {g1, g2, g3, ..., gn}
G_n_r = {g_n, g_(n-1), g_(n-2), ..., g_1}
[G_n_r 是 G_n 的逆向順序]
G_(n+1) = {0G_n, 1G_n_r}
例如
G_2 = {0G_1, 1G_1_r} = {00, 01, 11, 10}
G_2_r = {10, 11, 01, 00}
G_3 = {0G_2, 1G_2_r} = {000, 001, 011, 010, 110, 111, 101, 100}
G_3_r = {100, 101, 111, 110, 010, 011, 001, 000}
G_4 = {0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110,
1010, 1011, 1001, 1000}
G_4_r = {1000, 1001, 1011, 1010, 1110, 1111, 1101, 1100, 0100, 0101, 0111, 0110,
0010, 0011, 0001, 0000}

其遞迴公式為
G(n, k) = k if n=1
G(n, k) = 0G(n-1, k) if k<2^(n-1)
G(n, k) = 1G(n-1, 2^n-1-k) if k>=2^(n-1)
當 G(4, 7) = 0G(4-1, 7) = 0G(3, 7) = 01G(3-1, 2^3-1-7) = 01G(2, 0) = 010G(2-1,
0) = 010G(1, 0) = 0100

依此撰寫遞迴程式,輸入 n, k,輸出 Gray code。

【輸入說明】
第一行是輸入資料,整數n(1<=n<=8)、整數k(1<=k<=8)
接下來重複第一行，直到輸入 -1 結束

範例輸入說明:
Sample Input:
1 1 (第一筆資料，n=1、k=1)
2 3 (第二筆資料，n=2、k=3)
3 6 (第三筆資料，n=3、k=6)
4 12 (第四筆資料，n=4、k=12)
-1 (結束讀取)

【輸出說明】
每一行輸出一個測試資料的結果

範例輸入說明:
1 (n=1、k=1的執行結果)
10 (n=2、k=3的執行結果)
101 (n=3、k=6的執行結果)
1010 (n=4、k=12的執行結果)

【測試資料一】
輸入：
3 7
4 15
5 30
1 0
6 50
-1

輸出：
100
1000
10001
0
101011

【測試資料二】
輸入：
3 4
3 5
3 6
4 10
4 11
4 12
5 16
-1

輸出：
110
111
101
1111
1110
1010
11000

【測試資料三】
輸入：
5 1
6 16
7 4
4 4
-1

輸出：
00001
011000
0000110
0110

【隱藏測試資料一】
輸入：
2 2
3 5
4 13
5 22
-1

輸出：
11
111
1011
11101

【隱藏測試資料二】
輸入：
5 16
5 17
5 18
5 19
5 20
-1

輸出：
11000
11001
11011
11010
11110

【隱藏測試資料三】
輸入：
6 0
6 2
6 4
6 8
9 15
-1

輸出：
000000
000011
000110
001100
000001000