生成所有 n 位格雷码

n 位元的格雷码，那么格雷码的个数为 2^n

#include <iostream> #include <vector> #include <cmath> using namespace std; /* 利用递归的如下规则来构造： * 1 位格雷码有两个码字 * n 位格雷码中的前 2^(n-1) 个码字等于 (n-1) 位格雷码的码字，按顺序书写，加前缀 0 * n 位格雷码中的后 2^(n-1) 个码字等于 (n-1) 位格雷码的码字，按逆序书写，加前缀 1 * n 位格雷码的集合 = (n-1) 位格雷码集合(顺序)加前缀 0 + (n-1) 位格雷码集合(逆序)加前缀 1 */ class GrayCode { public: vector<string> getGray(int n) { vector<string> grayCodes(pow(2, n)); if(n == 1) { grayCodes[0] = "0"; grayCodes[1] = "1"; } else { vector<string> _grayCodes = getGray(n - 1);// 要计算 n 位的格雷码，就得先得到 n-1 位的格雷码 for(vector<string>::size_type i=0; i < _grayCodes.size(); i++) { grayCodes[i] = "0" + _grayCodes[i]; grayCodes[grayCodes.size()-i-1] = "1" + _grayCodes[i]; } } return grayCodes; } }; int main() { GrayCode gray; int n; cin >> n; vector<string> grayCodes = gray.getGray(n); for(vector<string>::iterator it=grayCodes.begin(); it != grayCodes.end(); it++) { cout << *it << endl; } return 0; }