Gray Code (CSES 2205)

發表於 更新於 分類於 ， 閱讀次數： 文章字數： 448 所需閱讀時間 ≈ 2 分鐘

題目網址

A Gray code is a list of all \(2^n\) bit strings of length \(n\), where any two successive strings differ in exactly one bit (i.e., their Hamming distance is one). Your task is to create a Gray code for a given length \(n\).

解題思路： 這題實作上非常簡單，但就是在想解題的過程很有趣，我想到一種一定是解的作法，有遞迴的感覺，底下舉個例子：
\(n=1\):
0
1

\(n=2\):
00
01
11
10

\(n=3\):
000
001
011
010
110
111
101
100

會發現 \(n\) 的 Gray Code 就是在 \(n-1\) 的 Gray Code 前面加上 0，再把 \(n-1\) 的 Gray Code 反過來加上 1，這樣就能保證相鄰的兩個字串只有一個 bit 不同，而且也能保證所有的字串都會出現，所以就是一定是解，但只知道這樣其實在實作上會有點麻煩，會需要紀錄之前的 Gray Code，其實可以發現每一位之間是有規律的，以最右邊的一位為例，必定會是 011001100110…，第二位就是 0011110000111100…，第 \(i\) 為的間格會是 \(2^i\)，那就可以一位位分析應該擺 0 或 1，但再仔細觀察一下，這樣的關係，恰好會是兩位之間 XOR=1 的間格，以第一位為例：
無論數字多大，位元的第一和第二位都會是如下規律：
00
01
10
11
00
01
10
11
00
…
兩位間 XOR 關係後恰巧會是：011001100110…

而若是第二位： 無論數字多大，位元的前三位都會是如下規律： 000
001
011
010
110
111
101
100
000
…
第二三位間 XOR 關係後恰巧會是：0011110000111100…
以此類推，最後一位就看目前有沒有過半，過半前是 0，過半後是 1，就能輕鬆秒殺這題了。

Gray Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
#define pii pair<int, int>
#define int long long
#define rep(i, a, b) for(int i = a; i<=b; i++ )
#define rev(i, a, b) for(int i = a; i>=b; i-- )
#define tomax(a, b) (a)=max((a), (b))
#define tomin(a, b) (a)=min((a), (b))
#define pb push_back
#define eb emplace_back
using namespace std;

signed main(){
    ios
    int n;
    cin >> n;
    rep(i, 0, (1<<n)-1){
        cout << (i>>(n-1));
        rev(j, n-2, 0)
            cout << (((i>>j)&1) ^ ((i>>(j+1))&1));
        cout << '\n';
    }
    return 0;
}